from bipartite_recipe import bipartite_match
def max_degree(graph):
max_degree_u=max(len(v) for v in graph.values() )
count={}
for vlist in graph.values():
for v in vlist:
try:
count[v]+=1
except KeyError:
count[v]=1
max_degree_v=max(count.values())
return max(max_degree_v,max_degree_u)
def best_match(graph):
b_m=bipartiteMatch(graph)[0]
return dict((value,key) for (key,value) in b_m.items())
def edge_coloring(graph):
g=graph.copy()
number_colors=max_degree(g)
for color in range(number_colors):
print 'NEXT COLOR'
bm=best_match(g)
print bm
for k in g.copy():
try:
g[k].remove(bm[k])
except KeyError:
pass
graph={ 'p1':['c1','c3'], 'p2':['c1','c2'], 'p3':['c2','c3'], 'p4':['c2'] }
edge_coloring(graph)
