edu.stanford.math.plex4.bottleneck

Class WeightedBipartiteGraph

java.lang.Object

edu.stanford.math.plex4.bottleneck.WeightedBipartiteGraph

public class WeightedBipartiteGraph
extends java.lang.Object

Constructor Summary

Constructors

Constructor and Description
WeightedBipartiteGraph(int partitionSize)

Method Summary

Methods

Modifier and Type	Method and Description
void	addEdge(int source, int destination, double weight)
int	computeMaximumCardinalityMatching()
double	computePerfectMatchingThreshold() This function computes the smallest value, v, that when the current bipartite graph is filtered by v, a perfect matching exists.
WeightedBipartiteGraph	filterByMaximum(double maximumWeight)
boolean	hasPerfectMatching()

Methods inherited from class java.lang.Object

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

Constructor Detail

WeightedBipartiteGraph

public WeightedBipartiteGraph(int partitionSize)

Method Detail

addEdge

public void addEdge(int source,
           int destination,
           double weight)

filterByMaximum

public WeightedBipartiteGraph filterByMaximum(double maximumWeight)

computeMaximumCardinalityMatching

public int computeMaximumCardinalityMatching()

hasPerfectMatching

public boolean hasPerfectMatching()

computePerfectMatchingThreshold

public double computePerfectMatchingThreshold()

This function computes the smallest value, v, that when the current bipartite graph is filtered by v, a perfect matching exists. If no perfect matching exists for all filtration values, it returns -1.

Returns: