TUM CCSM Commons

edu.tum.cs.commons.algo
Class MaxWeightMatching<N1,N2>

java.lang.Object
  extended by edu.tum.cs.commons.algo.MaxWeightMatching<N1,N2>
Type Parameters:
N1 - The first node type
N2 - 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

Nested Class Summary
static interface MaxWeightMatching.IWeightProvider<N1,N2>
          A class providing the weight for a connection between two nodes.
 
Constructor Summary
MaxWeightMatching()
           
 
Method Summary
 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.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

MaxWeightMatching

public MaxWeightMatching()
Method Detail

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

TUM CCSM Commons - 2.7