Package org.graph4j.matching

Class HopcroftKarpMaximumMatching

java.lang.Object

org.graph4j.SimpleGraphAlgorithm

org.graph4j.matching.HopcroftKarpMaximumMatching

All Implemented Interfaces:

MatchingAlgorithm

public class HopcroftKarpMaximumMatching
extends SimpleGraphAlgorithm
implements MatchingAlgorithm

Computes the maximum cardinality matching in a bipartite graph. It also determines the maximum stable set and the minimum vertex cover in a bipartite graph.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.SimpleGraphAlgorithm

graph

Constructor Summary

Constructors

Constructor	Description
HopcroftKarpMaximumMatching(Graph graph)	Creates an algorithm for determining a maximum matching in a bipartite graph.
HopcroftKarpMaximumMatching(Graph graph, StableSet leftSide, StableSet rightSide)	Creates an algorithm for determining a maximum matching in a bipartite graph.

Method Summary

Modifier and Type	Method	Description
Matching	getMatching()
StableSet	getMaximumStableSet()	niu(G) + alpha(G) = n.
VertexSet	getMinimumVertexCover()	The minimum vertex cover set and the maximum matching set have the same size.

Methods inherited from class org.graph4j.SimpleGraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.graph4j.matching.MatchingAlgorithm

getGraph

Constructor Details

HopcroftKarpMaximumMatching

public HopcroftKarpMaximumMatching(Graph graph)

Creates an algorithm for determining a maximum matching in a bipartite graph. If the graph is not bipartite, an exception is thrown.

Parameters:

graph - the input graph.

Throws:

NotBipartiteException - if the graph is not bipartite.

HopcroftKarpMaximumMatching

public HopcroftKarpMaximumMatching(Graph graph,
 StableSet leftSide,
 StableSet rightSide)

Creates an algorithm for determining a maximum matching in a bipartite graph. The bipartition is assumed to be valid.

Parameters:

graph - the input bipartite graph.

leftSide - the left side of the bipartite graph.

rightSide - the right side of the bipartite graph.

Method Details

getMatching

public Matching getMatching()

Specified by:

getMatching in interface MatchingAlgorithm

Returns:

the maximum cardinality matching.

getMaximumStableSet

public StableSet getMaximumStableSet()

niu(G) + alpha(G) = n.

Returns:

the maximum stable set.

getMinimumVertexCover

public VertexSet getMinimumVertexCover()

The minimum vertex cover set and the maximum matching set have the same size.

Returns:

the minimum vertex cover.