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)