Konig's theorem tells us that every bipartite graph with maximum vertex-degree d can be edge-colored with just d colors. This recipe relies on a previous recipe by D.Eppstein (123641) : "Hopcroft-Karp bipartite matching".
Python, 30 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | 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)
|
The algorithm presented here simply does the following two steps d times: 1-find the maximum cardinality matching using Hopcroft-Karp algorithm. All edges found get the same color assigned 2-delete the edges found above and goto 1
This algorithm is not optimal in terms of number of operations but it has the merit to exist in less than 20 lines (other algorithms are a real pain to implement ;-))
Tags: algorithms
