Class HopcroftKarpMaximumCardinalityBipartiteMatching<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
MatchingAlgorithm<V,
E>
SparseEdmondsMaximumCardinalityMatching
instead.
The Hopcroft Karp matching algorithm computes augmenting paths of increasing length, until no augmenting path exists in the graph. At each iteration, the algorithm runs a Breadth First Search from the exposed (free) vertices, until an augmenting path is found. Next, a Depth First Search is performed to find all (vertex disjoint) augmenting paths of the same length. The matching is augmented along all discovered augmenting paths simultaneously.
The original algorithm is described in: Hopcroft, John E.; Karp, Richard M. (1973), "An n5/2 algorithm for maximum matchings in bipartite graphs", SIAM Journal on Computing 2 (4): 225–231, doi:10.1137/0202019 A coarse overview of the algorithm is given in: http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm
-
Nested Class Summary
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
MatchingAlgorithm.Matching<V,
E>, MatchingAlgorithm.MatchingImpl<V, E> -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate int[]
private static final int
private static final int
private int
private int[]
private FixedSizeIntegerQueue
Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
DEFAULT_EPSILON
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate boolean
bfs()
BFS function which finds the shortest augmenting path.private boolean
dfs
(int u) Find all vertex disjoint augmenting paths of length dist[DUMMY].Compute a matching for a given graph.private void
init()
Initialize data structuresprivate void
Greedily compute an initial feasible matching
-
Field Details
-
graph
-
partition1
-
partition2
-
vertices
-
vertexIndexMap
-
matchedVertices
private int matchedVertices -
DUMMY
private static final int DUMMY- See Also:
-
INF
private static final int INF- See Also:
-
matching
private int[] matching -
dist
private int[] dist -
queue
-
-
Constructor Details
-
HopcroftKarpMaximumCardinalityBipartiteMatching
public HopcroftKarpMaximumCardinalityBipartiteMatching(Graph<V, E> graph, Set<V> partition1, Set<V> partition2) Constructs a new instance of the Hopcroft Karp bipartite matching algorithm. The input graph must be bipartite. For efficiency reasons, this class does not check whether the input graph is bipartite. Invoking this class on a non-bipartite graph results in undefined behavior. To test whether a graph is bipartite, useGraphTests.isBipartite(Graph)
.- Parameters:
graph
- bipartite graphpartition1
- the first partition of vertices in the bipartite graphpartition2
- the second partition of vertices in the bipartite graph
-
-
Method Details
-
init
private void init()Initialize data structures -
warmStart
private void warmStart()Greedily compute an initial feasible matching -
bfs
private boolean bfs()BFS function which finds the shortest augmenting path. The length of the shortest augmenting path is stored in dist[DUMMY].- Returns:
- true if an augmenting path was found, false otherwise
-
dfs
private boolean dfs(int u) Find all vertex disjoint augmenting paths of length dist[DUMMY]. To find paths of dist[DUMMY] length, we simply follow nodes that are 1 distance increments away from each other.- Parameters:
u
- vertex from which the DFS is started- Returns:
- true if an augmenting path from vertex u was found, false otherwise
-
getMatching
Description copied from interface:MatchingAlgorithm
Compute a matching for a given graph.- Specified by:
getMatching
in interfaceMatchingAlgorithm<V,
E> - Returns:
- a matching
-