Package org.jgrapht.alg
Class MaximumWeightBipartiteMatching<V,E>
- java.lang.Object
-
- org.jgrapht.alg.MaximumWeightBipartiteMatching<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
MatchingAlgorithm<V,E>
,WeightedMatchingAlgorithm<V,E>
@Deprecated public class MaximumWeightBipartiteMatching<V,E> extends java.lang.Object implements WeightedMatchingAlgorithm<V,E>
Deprecated.UseMaximumWeightBipartiteMatching
instead.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
Deprecated.private WeightedGraph<V,E>
graph
Deprecated.private java.util.Map<V,java.lang.Boolean>
hasVertexBeenProcessed
Deprecated.private java.util.Map<E,java.lang.Boolean>
isEdgeMatched
Deprecated.private java.util.Set<V>
partition1
Deprecated.private java.util.Set<V>
partition2
Deprecated.private java.util.Map<V,java.lang.Long>
vertexWeights
Deprecated.-
Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
DEFAULT_EPSILON
-
-
Constructor Summary
Constructors Constructor Description MaximumWeightBipartiteMatching(WeightedGraph<V,E> graph, java.util.Set<V> vertexPartition1, java.util.Set<V> vertexPartition2)
Deprecated.Creates a new MaximumWeightBipartiteMatching algorithm instance.
-
Method Summary
All Methods Instance Methods Concrete Methods Deprecated Methods Modifier and Type Method Description private void
addPathToMatchings(java.util.List<E> path, java.util.Set<E> matchings)
Deprecated.private void
adjustVertexWeights(java.util.Map<V,java.util.List<E>> reachableVertices)
Deprecated.MatchingAlgorithm.Matching<E>
computeMatching()
Deprecated.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)
Deprecated.java.util.Set<E>
getMatching()
Deprecated.Returns set of edges making up the matchingdouble
getMatchingWeight()
Deprecated.Returns weight of a matching foundprivate void
initializeVerticesAndEdges()
Deprecated.private boolean
isSourceVertex(V vertex)
Deprecated.private boolean
isTargetVertex(V vertex)
Deprecated.private boolean
isVertexMatched(V vertex, java.util.Set<E> matchings)
Deprecated.private java.util.Set<E>
maximumWeightBipartiteMatching()
Deprecated.private long
maximumWeightOfEdgeIncidentToVertex(V vertex)
Deprecated.private long
reducedWeight(E edge)
Deprecated.private void
setVertexWeight(V vertex, java.lang.Long weight)
Deprecated.private long
vertexWeight(V vertex)
Deprecated.private java.util.Map<V,java.util.List<E>>
verticesReachableByTightAlternatingEdgesFromVertex(V vertex)
Deprecated.
-
-
-
Field Detail
-
graph
private final WeightedGraph<V,E> graph
Deprecated.
-
partition1
private final java.util.Set<V> partition1
Deprecated.
-
partition2
private final java.util.Set<V> partition2
Deprecated.
-
vertexWeights
private java.util.Map<V,java.lang.Long> vertexWeights
Deprecated.
-
hasVertexBeenProcessed
private java.util.Map<V,java.lang.Boolean> hasVertexBeenProcessed
Deprecated.
-
isEdgeMatched
private java.util.Map<E,java.lang.Boolean> isEdgeMatched
Deprecated.
-
bipartiteMatching
private java.util.Set<E> bipartiteMatching
Deprecated.
-
-
Constructor Detail
-
MaximumWeightBipartiteMatching
public MaximumWeightBipartiteMatching(WeightedGraph<V,E> graph, java.util.Set<V> vertexPartition1, java.util.Set<V> vertexPartition2)
Deprecated.Creates a new MaximumWeightBipartiteMatching algorithm instance. The union of vertexPartition1 and vertexParition2 should be equal to the vertex set of the graph Every edge in the graph must connect a vertex in vertexPartition1 with a vertex in vertexPartition2- Parameters:
graph
- simple undirected weighted bipartite graph to find matching in, with positive integer edge weightsvertexPartition1
- first vertex partition of the bipartite graph, disjoint from vertexPartition2vertexPartition2
- second vertex partition of the bipartite graph, disjoint from vertexPartition1
-
-
Method Detail
-
getMatching
public java.util.Set<E> getMatching()
Deprecated.Description copied from interface:MatchingAlgorithm
Returns set of edges making up the matching- Specified by:
getMatching
in interfaceMatchingAlgorithm<V,E>
- Returns:
- a matching
-
getMatchingWeight
public double getMatchingWeight()
Deprecated.Description copied from interface:WeightedMatchingAlgorithm
Returns weight of a matching found- Specified by:
getMatchingWeight
in interfaceWeightedMatchingAlgorithm<V,E>
- Returns:
- weight of a matching found
-
computeMatching
public MatchingAlgorithm.Matching<E> computeMatching()
Deprecated.Compute a matching for a given graph.- Specified by:
computeMatching
in interfaceMatchingAlgorithm<V,E>
- Returns:
- a matching
-
initializeVerticesAndEdges
private void initializeVerticesAndEdges()
Deprecated.
-
maximumWeightOfEdgeIncidentToVertex
private long maximumWeightOfEdgeIncidentToVertex(V vertex)
Deprecated.
-
isSourceVertex
private boolean isSourceVertex(V vertex)
Deprecated.
-
isTargetVertex
private boolean isTargetVertex(V vertex)
Deprecated.
-
vertexWeight
private long vertexWeight(V vertex)
Deprecated.
-
setVertexWeight
private void setVertexWeight(V vertex, java.lang.Long weight)
Deprecated.
-
reducedWeight
private long reducedWeight(E edge)
Deprecated.
-
addPathToMatchings
private void addPathToMatchings(java.util.List<E> path, java.util.Set<E> matchings)
Deprecated.
-
adjustVertexWeights
private void adjustVertexWeights(java.util.Map<V,java.util.List<E>> reachableVertices)
Deprecated.
-
verticesReachableByTightAlternatingEdgesFromVertex
private java.util.Map<V,java.util.List<E>> verticesReachableByTightAlternatingEdgesFromVertex(V vertex)
Deprecated.
-
findPathsToVerticesFromVertices
private void findPathsToVerticesFromVertices(java.util.List<V> verticesToProcess, boolean needMatchedEdge, java.util.Map<V,java.util.List<E>> pathsToVertices)
Deprecated.
-
maximumWeightBipartiteMatching
private java.util.Set<E> maximumWeightBipartiteMatching()
Deprecated.
-
-