org.jgrapht.alg

Class MaximumWeightBipartiteMatching<V,E>

java.lang.Object

org.jgrapht.alg.MaximumWeightBipartiteMatching<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MatchingAlgorithm<V,E>, WeightedMatchingAlgorithm<V,E>

public class MaximumWeightBipartiteMatching<V,E>
extends Object
implements WeightedMatchingAlgorithm<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

Author:

Graeme Ahokas

Constructor Summary

Constructors

Constructor and Description
MaximumWeightBipartiteMatching(WeightedGraph<V,E> graph, Set<V> vertexPartition1, Set<V> vertexPartition2) Creates a new MaximumWeightBipartiteMatching algorithm instance.

Method Summary

Modifier and Type	Method and Description
Set<E>	getMatching() Returns set of edges making up the matching
double	getMatchingWeight() Returns weight of a matching found

Methods inherited from class java.lang.Object

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

Constructor Detail

MaximumWeightBipartiteMatching

public MaximumWeightBipartiteMatching(WeightedGraph<V,E> graph,
                                      Set<V> vertexPartition1,
                                      Set<V> vertexPartition2)

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 weights

vertexPartition1 - first vertex partition of the bipartite graph, disjoint from vertexPartition2

vertexPartition2 - second vertex partition of the bipartite graph, disjoint from vertexPartition1

Method Detail

getMatching

public Set<E> getMatching()

Description copied from interface: MatchingAlgorithm

Returns set of edges making up the matching

Specified by:

getMatching in interface MatchingAlgorithm<V,E>

Returns:

a matching

getMatchingWeight

public double getMatchingWeight()

Description copied from interface: WeightedMatchingAlgorithm

Returns weight of a matching found

Specified by:

getMatchingWeight in interface WeightedMatchingAlgorithm<V,E>

Returns:

weight of a matching found