Package org.jgrapht.alg.matching
Class MaximumWeightBipartiteMatching<V,E>
- java.lang.Object
-
- org.jgrapht.alg.matching.MaximumWeightBipartiteMatching<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
MatchingAlgorithm<V,E>
public class MaximumWeightBipartiteMatching<V,E> extends java.lang.Object implements MatchingAlgorithm<V,E>
This class finds a maximum weight matching of a simple undirected weighted bipartite graph. The algorithm runs in O(V|E|^2). The algorithm is described in The LEDA Platform of Combinatorial and Geometric Computing, Cambridge University Press, 1999. https://people.mpi-inf.mpg.de/~mehlhorn/LEDAbook.html Note: the input graph must be bipartite with positive integer edge weights
-
-
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 java.util.Set<E>
bipartiteMatching
private UndirectedGraph<V,E>
graph
private java.util.Map<V,java.lang.Boolean>
hasVertexBeenProcessed
private java.util.Map<E,java.lang.Boolean>
isEdgeMatched
private java.util.Set<V>
partition1
private java.util.Set<V>
partition2
private java.util.Map<V,java.lang.Long>
vertexWeights
-
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 void
addPathToMatchings(java.util.List<E> path, java.util.Set<E> matchings)
private void
adjustVertexWeights(java.util.Map<V,java.util.List<E>> reachableVertices)
MatchingAlgorithm.Matching<E>
computeMatching()
Compute a matching for a given graph.private void
findPathsToVerticesFromVertices(java.util.List<V> verticesToProcess, boolean needMatchedEdge, java.util.Map<V,java.util.List<E>> pathsToVertices)
private void
initializeVerticesAndEdges()
private boolean
isSourceVertex(V vertex)
private boolean
isTargetVertex(V vertex)
private boolean
isVertexMatched(V vertex, java.util.Set<E> matchings)
private java.util.Set<E>
maximumWeightBipartiteMatching()
private long
maximumWeightOfEdgeIncidentToVertex(V vertex)
private long
reducedWeight(E edge)
private void
setVertexWeight(V vertex, java.lang.Long weight)
private long
vertexWeight(V vertex)
private java.util.Map<V,java.util.List<E>>
verticesReachableByTightAlternatingEdgesFromVertex(V vertex)
-
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<V> partition1
-
partition2
private java.util.Set<V> partition2
-
vertexWeights
private java.util.Map<V,java.lang.Long> vertexWeights
-
hasVertexBeenProcessed
private java.util.Map<V,java.lang.Boolean> hasVertexBeenProcessed
-
isEdgeMatched
private java.util.Map<E,java.lang.Boolean> isEdgeMatched
-
bipartiteMatching
private java.util.Set<E> bipartiteMatching
-
-
Constructor Detail
-
MaximumWeightBipartiteMatching
public MaximumWeightBipartiteMatching(Graph<V,E> graph, java.util.Set<V> partition1, java.util.Set<V> partition2)
Construct a new instance of the algorithm. Supported graphs are simple undirected weighted bipartite with positive integer edge weights.- Parameters:
graph
- the input graphpartition1
- the first partition of the vertex setpartition2
- the second partition of the vertex set- Throws:
java.lang.IllegalArgumentException
- if the graph is not undirected
-
-
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
-
initializeVerticesAndEdges
private void initializeVerticesAndEdges()
-
maximumWeightOfEdgeIncidentToVertex
private long maximumWeightOfEdgeIncidentToVertex(V vertex)
-
isSourceVertex
private boolean isSourceVertex(V vertex)
-
isTargetVertex
private boolean isTargetVertex(V vertex)
-
vertexWeight
private long vertexWeight(V vertex)
-
setVertexWeight
private void setVertexWeight(V vertex, java.lang.Long weight)
-
reducedWeight
private long reducedWeight(E edge)
-
addPathToMatchings
private void addPathToMatchings(java.util.List<E> path, java.util.Set<E> matchings)
-
adjustVertexWeights
private void adjustVertexWeights(java.util.Map<V,java.util.List<E>> reachableVertices)
-
verticesReachableByTightAlternatingEdgesFromVertex
private java.util.Map<V,java.util.List<E>> verticesReachableByTightAlternatingEdgesFromVertex(V vertex)
-
findPathsToVerticesFromVertices
private void findPathsToVerticesFromVertices(java.util.List<V> verticesToProcess, boolean needMatchedEdge, java.util.Map<V,java.util.List<E>> pathsToVertices)
-
maximumWeightBipartiteMatching
private java.util.Set<E> maximumWeightBipartiteMatching()
-
-