Algorithm
Development Kit 1.0

algs.model.network.matching
Class BipartiteMatching

java.lang.Object
  extended by algs.model.network.matching.BipartiteMatching

public class BipartiteMatching
extends java.lang.Object

Computes a matching in a bipartite graph whose vertices are divided into two distinct sets S and T and whose edges only exist between vertices in S and vertices in T.

Computes the matching by converting the problem into a FlowNetwork problem.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Constructor Summary
BipartiteMatching(java.lang.Object[] setS, java.lang.Object[] setT, java.lang.Object[][] pairs)
          Construct matching instance from information.
 
Method Summary
 java.util.Iterator<Pair> compute()
          Compute a solution to the FlowNetwork problem and find all edges in the solution whose flow is 1, since these are valid solutions to the matching problem.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

BipartiteMatching

public BipartiteMatching(java.lang.Object[] setS,
                         java.lang.Object[] setT,
                         java.lang.Object[][] pairs)
Construct matching instance from information.

Note that the objects which make up the vertex sets must have properly implements Object.hashCode() and Object.equals(Object) methods.

Parameters:
setS - Set S being matched to T
setT - Set T being matched to S
pairs - edges crossing from S to T
Throws:
java.lang.RuntimeException - if an error in input occurs.
Method Detail

compute

public java.util.Iterator<Pair> compute()
Compute a solution to the FlowNetwork problem and find all edges in the solution whose flow is 1, since these are valid solutions to the matching problem.

Return an Iterator of Pair objects that reflect the discovered matching.


Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.