org.conqat.lib.commons.algo

Class MaxWeightMatching<N1,N2>

java.lang.Object

org.conqat.lib.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!

Author:

hummelb

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	MaxWeightMatching.IWeightProvider<N1,N2> A class providing the weight for a connection between two nodes.

Constructor Summary

Constructors

Constructor and Description
MaxWeightMatching()

Method Summary

Modifier and Type	Method and Description
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.