edu.tum.cs.commons.algo
Class MaxWeightMatching<N1,N2>
java.lang.Object
edu.tum.cs.commons.algo.MaxWeightMatching<N1,N2>
- Type Parameters:
N1
- The first node typeN2
- The second node type
public class MaxWeightMatching<N1,N2>
- extends java.lang.Object
A class for calculating maximum weighted matching using an augmenting path
algorithm running in O(n^3*m), where n is the size of the smaller node set
and m the size of the larger one. In practice the running time is much less.
This class is not thread save!
- Version:
- $Rev: 26283 $
- Author:
- hummelb, $Author: juergens $
- Rating:
- GREEN Hash: 2069DC784F078E4503328061B520BBB1
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
MaxWeightMatching
public MaxWeightMatching()
calculateMatching
public double calculateMatching(java.util.List<N1> nodes1,
java.util.List<N2> nodes2,
MaxWeightMatching.IWeightProvider<N1,N2> weightProvider,
PairList<N1,N2> matching)
- Calculate the weighted bipartite matching.
- Parameters:
matching
- if this is non null
, the matching (i.e. the pairs of nodes
matched onto each other) will be put into it.
- Returns:
- the weight of the matching.
TUM CCSM Commons - 2.7