Welcome, guest | Sign In | My Account | Store | Cart

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
 1
 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 ;-))