buaa benchmarking

import networkx as nx
import os
import numpy as np
import time
import random

def mvc(graph):
    cost = {u:1 for u in range(graph.number_of_nodes())}
    for u,v in graph.edges:
        min_cost = min(cost[u], cost[v])
        cost[u] -= min_cost
        cost[v] -= min_cost
    return {u for u,v in cost.iteritems() if v ==0}
    
# or use this 
def my_mvc(graph):
    # We are going to modify the graph
    graph = graph.copy()
    vc = set()
    while graph.number_of_edges() > 0:
        sorted_edges = sorted(graph.edges, key = lambda (x,y): - graph.degree(x) - graph.degree(y))
        u,v = sorted_edges[0]
        vc.add(u)
        vc.add(v)
        graph.remove_node(u)
        graph.remove_node(v)
    return vc

vc = []
data_dir = "/data/qpbo/buaa/mc/data/"
for _,subdirs,_ in os.walk(data_dir):
    for subdir in subdirs:
        for _,_,filenames in os.walk(os.path.join(data_dir, subdir)):
            for file in filenames:
                filepath = os.path.join(data_dir, subdir, file)
                content = open(filepath)
                n,e = map(int, content.readline().split()[2:])
                edges = []
                for line in content:
                    edges.append(map(lambda x:int(x)-1, line.split()[1:]))
                graph = nx.Graph()
                graph.add_edges_from(edges)

                print filepath, x
                x = len(mvc(graph))
                vc.append(x)
                
 print "mean vc size:{}".format(np.mean(vc))