Algorithm: Bipartite Graph Matching

二部グラフの最大マッチング

 

	#!/usr/bin/env python
	# -*- coding: utf-8 -*-
	""""
	Bipartite graph matching algorithm
	"""
	import collections
	class Graph(object):
	"""
	Simple graph model.
	"""
	def __init__(self, num_nodes):
	self.edges = collections.defaultdict(dict)
	self.num_nodes = num_nodes
	def make_edge(self, from_, to, value):
	self.edges[from_][to] = value
	class BipartiteGraph(object):
	"""
	Bipartite undirected graph model.
	"""
	def __init__(self):
	self.edges = set()
	self.num_u = 0
	self.num_v = 0
	def make_edge(self, u, v):
	self.edges.add((u, v))
	self.num_u = max(self.num_u, u + 1)
	self.num_v = max(self.num_v, v + 1)
	def to_graph(self):
	g = Graph(self.num_u + self.num_v)
	edges = [(u, v + self.num_u) for u, v in self.edges]
	for from_, to in edges:
	g.make_edge(from_, to, 1)
	return g
	def bipartite_matching(bipartite_graph):
	"""
	Returns one of the combinations for the maximum bipartite matching
	"""
	# Convert to normal graph.
	g = bipartite_graph.to_graph()
	def dfs(v):
	used.add(v)
	for u in g.edges[v]:
	w = match.get(u)
	if w is None or w not in used and dfs(w):
	match[v] = u
	match[u] = v
	return True
	return False
	ret = 0 # maximum number of matching
	match = {} # result of matching
	for v in xrange(g.num_nodes):
	if not v in match:
	used = set()
	if dfs(v):
	ret += 1
	# Put back to bipartite graph's index.
	return [(u, v - bipartite_graph.num_u) for u, v in match.items() if u < bipartite_graph.num_u]
	if __name__ == '__main__':
	a = BipartiteGraph()
	for p, q in [(0, 1), (1, 0), (1, 1), (1, 2), (2, 1)]:
	a.make_edge(p, q)
	#
	# 0 0
	# X
	# 1 - 1
	# X
	# 2 2
	#
	b = BipartiteGraph()
	for p, q in [(0, 1), (1, 0), (1, 1), (1, 2), (2, 1), (2, 2)]:
	b.make_edge(p, q)
	#
	# 0 0
	# X
	# 1 - 1
	# X
	# 2 - 2
	#
	c = BipartiteGraph()
	for p, q in [(1, 0), (1, 2)]:
	c.make_edge(p, q)
	#
	# 0 0
	# /
	# 1 1
	# \
	# 2
	#
	d = BipartiteGraph()
	for p, q in [(0, 1), (1, 0), (1, 1), (2, 1), (2, 2), (2, 3), (3, 2), (3, 4), (4, 3)]:
	d.make_edge(p, q)
	#
	# 0 0
	# X
	# 1 - 1
	# /
	# 2 - 2
	# X
	# 3 3
	# X
	# 4 4
	#
	for g in a, b, c, d:
	print bipartite_matching(g)

view raw a10_a_bipartite_matching.py hosted with ❤ by GitHub

output

[(0, 1), (1, 0)] [(0, 1), (1, 0), (2, 2)] [(1, 0)] [(0, 1), (1, 0), (2, 2), (3, 4), (4, 3)]