Package org.jgrapht.alg.matching
Class HopcroftKarpBipartiteMatching<V,E>
- java.lang.Object
-
- org.jgrapht.alg.matching.HopcroftKarpBipartiteMatching<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
MatchingAlgorithm<V,E>
public class HopcroftKarpBipartiteMatching<V,E> extends java.lang.Object implements MatchingAlgorithm<V,E>
This class is an implementation of the Hopcroft-Karp algorithm which finds a maximum matching in an undirected simple bipartite graph. The algorithm runs in O(|E|*√|V|) time. 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 Note: the behavior of this class is undefined when the input isn't a bipartite graph, i.e. when there are edges within a single partition!
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
MatchingAlgorithm.Matching<E>, MatchingAlgorithm.MatchingImpl<E>
-
-
Field Summary
Fields Modifier and Type Field Description private UndirectedGraph<V,E>
graph
private java.util.Set<E>
matching
private java.util.Set<? extends V>
partition1
private java.util.Set<? extends V>
partition2
private java.util.Set<V>
unmatchedVertices1
private java.util.Set<V>
unmatchedVertices2
-
Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
DEFAULT_EPSILON
-
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private boolean
checkInputData()
Checks whether the input data meets the requirements: simple undirected graph and bipartite partitions.MatchingAlgorithm.Matching<E>
computeMatching()
Compute a matching for a given graph.private java.util.LinkedList<V>
dfs(V startVertex, java.util.Map<V,java.util.Set<V>> layeredMap)
private java.util.List<java.util.LinkedList<V>>
getAugmentingPaths()
private void
greedyMatch()
Greedily match the vertices in partition1 to the vertices in partition2.private boolean
interSectionNotEmpty(java.util.Set<V> vertexSet1, java.util.Set<V> vertexSet2)
Helper method which checks whether the intersection of 2 sets is empty.private void
maxMatching()
This method is the main method of the class.private void
symmetricDifference(java.util.LinkedList<V> augmentingPath)
Given are the current matching and a new augmenting path p.-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
getMatching
-
-
-
-
Field Detail
-
graph
private final UndirectedGraph<V,E> graph
-
partition1
private java.util.Set<? extends V> partition1
-
partition2
private java.util.Set<? extends V> partition2
-
matching
private java.util.Set<E> matching
-
unmatchedVertices1
private java.util.Set<V> unmatchedVertices1
-
unmatchedVertices2
private java.util.Set<V> unmatchedVertices2
-
-
Constructor Detail
-
HopcroftKarpBipartiteMatching
public HopcroftKarpBipartiteMatching(Graph<V,E> graph, java.util.Set<V> partition1, java.util.Set<V> partition2)
Construct a new instance of the Hopcroft-Karp algorithm for the computation of maximum matchings in bipartite graphs.- Parameters:
graph
- the input graphpartition1
- the first partition of the vertex setpartition2
- the second partition of the vertex set
-
-
Method Detail
-
computeMatching
public MatchingAlgorithm.Matching<E> computeMatching()
Compute a matching for a given graph.- Specified by:
computeMatching
in interfaceMatchingAlgorithm<V,E>
- Returns:
- a matching
-
checkInputData
private boolean checkInputData()
Checks whether the input data meets the requirements: simple undirected graph and bipartite partitions.
-
greedyMatch
private void greedyMatch()
Greedily match the vertices in partition1 to the vertices in partition2. For each vertex in partition 1, check whether there is an edge to an unmatched vertex in partition 2. If so, add the edge to the matching.
-
maxMatching
private void maxMatching()
This method is the main method of the class. First it finds a greedy matching. Next it tries to improve the matching by finding all the augmenting paths. This leads to a maximum matching.
-
symmetricDifference
private void symmetricDifference(java.util.LinkedList<V> augmentingPath)
Given are the current matching and a new augmenting path p. p.getFirst() and p.getLast() are newly matched vertices. This method updates the edges which are part of the existing matching with the new augmenting path. As a result, the size of the matching increases with 1.- Parameters:
augmentingPath
-
-
getAugmentingPaths
private java.util.List<java.util.LinkedList<V>> getAugmentingPaths()
-
dfs
private java.util.LinkedList<V> dfs(V startVertex, java.util.Map<V,java.util.Set<V>> layeredMap)
-
-