Unweighted perfect matching
An algorithm for Graph matching;
Modifies the Hungarian algorithm. So no cases result in an infinite loop.
Rules of the game
Start from an unpaired node (seed)
s
..---o---.. ..---●---..
| |
: :
Neighbor unpaired?
s s
..---●---o.. ..---●xxx●..
| |
: :
Walk back to seed and invert edges.
Neighbor already paired?
Add and mate to tree.
s s
..---●---●.. ..---●---●xxx●
| |
: :
Then look at the next neighbor.
current node has no more neighbors?
s s l
..●---●---●.. ..●---●---●xxx●..
| |
● ●
: :
Start from the leaf that was first added to the tree
Exercise: augment
. . . . . .
. . . . . .
s
. ◯--------◯--------◯--------◯ .
. . . . . .
. . . . . .
Exercise: grow leaf
. . . . . .
. . . . . .
s
. ◯--------◯--------◯--------◯ .
. . . . . .
. . . . . .
Exercise: even cycle
. . . . . .
. ◯--------.--------◯ . .
| |
| |
| |
. ◯--------.--------◯ . .
|
|
|
. ◯ . . . .
|
|
|
. ◯ . . . .
Exercise: odd cycle
. . . . . .
. ◯--------.--------◯ . .
| |
| |
| |
. .--------◯--------. . .
|
|
|
. . ◯ . . .
. . . . . .
❀ | :
Neighbor already in a path?
:
/
s ....... /
●-------● :
| x :
---●xxxx :
| .....
|
:
Neighbor already in a path?
: :
/ /
s ....... / . s ...... /
●-------● : : ●-------● :
| x : : | x :
---●xxxx : : ---●xxxx :
| ..... ..... | .....
| |
: :
Neighbor already in a path?
: : :
/ / /
s ....... / . s ...... / /
●-------● : : ●-------● : /
| x : : | x : ❀
---●xxxx : : ---●xxxx : |
| ..... ..... | ..... |
| | |
: : :
Blossom
Exercise
. . . . . .
. ◯--------.--------◯ . .
| |
| |
| |
. ◯--------.--------◯ . .
| |
| |
| |
. .--------◯--------. . .
|
|
|
. . ◯ . . .
walking back ● | ❀ | ● ● | O---O \ x O | ●
Complexity: …
class Edge:
def __init__(self, node1, node2):
self.matched = False
self.node1 = node1
self.node2 = node2
node1.edges.append(self)
node2.edges.append(self)
def invert(self):
self.matched = False if self.matched else True
# if now matched, set endpoints as mates
# nodes use this method to see their neighbors.
# A neigbor inside a blossom is not visible from the outside.
def get_other(self, node):
if node == self.node1:
return self.node2 if self.node2.parent_blossom == False
else self.node2.parent_blossom
else:
return self.node1 if self.node1.parent_blossom == False
else self.node1.parent_blossom
class Node:
def __init__(self):
self.edges = []
self.tree = False
self.level = 0
self.is_blossom = False
self.parent_blossom = False
self.parent = False
self.children = []
# self.mate = False
def unpaired(self):
return not any([e.matched for e in self.edges])
# return self.mate == False
def mate(self):
for e in self.edges:
if e.matched:
return e.get_other(self)
def neighbors(self):
return [e.get_other(self) for e in self.edges]
def get_edge_to(self, node):
for e in self.edges:
if e.get_other(self) == node:
return e
def add_child(self, node):
self.children.append(node)
node.parent = self
node.tree = self.tree
# reset children
# when adding node to tree for the first time
node.children = []
def Blossom(Node):
def __init__(self, inner_nodes):
super(self, Blossom).__init__()
self.is_blossom = True
self.tree = inner_nodes[0].tree
# self.level = inner_nodes[0].level
self.inner_nodes = inner_nodes
# blossom edges go from inside to outside
for n in inner_nodes:
for e in n.edges:
self.edges.append(e) if e.get_other(n) not in inner_nodes
for n in inner_nodes:
# set parent blossom of inner nodes
n.parent_blossom = self
# set blossom as parent of inner nodes' children
for c in n.children: c.parent = self
# def open(self):
# for n in self.inner_nodes:
# n.parent_blossom = False
# del(self)
def open(self, child):
edge_state = blossom.get_edge_to(child).matched
for n in self.inner_nodes:
n.parent_blossom = False
A = child.parent
if e in A.edges:
if e.matched != edge_state:
B = e.get_other(A)
if B.tree == A.tree:
A.parent = B
del(self)
class Tree:
def __init__(self, seed):
self.seed = seed
self.seed.tree = self
self.leaves = []
self.active_node = self.seed
def grow(self):
found_unpaired_node = False
while not found_unpaired_node:
for neighbor in self.active_node.neighbors():
if neighbor.unpaired():
found_unpaired_neighbor = True
self.handle_unpaired(neighbor)
return neighbor
else:
if neighbor.tree == self:
cycle = self.handle_cycle(neighbor)
if len(cycle) % 2 == 1:
self.active_node = Blossom(cycle)
else:
self.handle_paired(neighbor)
self.active_node = self.leaves.pop(0)
def handle_unpaired(self, node):
self.active_node.add_child(node)
self.walk_back(node)
def handle_paired(self, node):
self.active_node.add_child(node)
mate = node.mate()
node.add_child(mate)
self.leaves.append(mate)
def handle_cycle(self, neighbor):
# branch from common node to neighbor
path1 = [neighbor]
# branch from common node to active_node
path2 = [active_node]
while path1[-1] != path2[-1]:
while len(path1[-1].children) == 1:
path1.append(path1[-1].parent)
while len(path2[-1].children) == 1:
path2.append(path2[-1].parent)
# common starting point found
cycle = path1 + path2[:-2]
return cycle
# walk back to the seed and invert edges
def walk_back(self, node):
pos = node
edge_state = False
# open blossoms in the neighborhood
while pos.parent.is_blossom:
pos.parent.open()
while pos != self.seed:
pos.get_edge_to(pos.parent).invert()
pos = pos.parent
while len(nodes) > 0:
t = Tree(seed=nodes.pop())
nodes.remove(t.grow())
for e in edges:
if e.matched:
print("paired nodes", e.node1, e.node2)
Variant of the algorithm if the edges have weights: Minimum-weight perfect matching;