Hungarian module¶

The Hungarian algorithm for finding the maximum matching in a bipartite graph. We use a breadth first search to find augmenting paths, then flip the edges to create a matching with an additional edge.

Algorithm 9.2.1 on page 174

Hungarian.augment(match, prev_pt, y)¶

Take the augmenting path encoded in prev_pt and match and flip it so we increase the number of edges in the matching by one.

Parameters

matchdict

The current matching

prev_ptdict

The BFS path that houses an augmenting path

yint

The ending point on the path

Hungarian.hungarian(G, X)¶

Performs the hungarian algorithm to find a maximal matching in the bipartite graph

Parameters

Gnx.Graph

A bipartite graph to find the matching in

Xset

One of the partitions in the bipartite graph

Returns

dict

A dictionary so that each vertex is related to its matched vertex