|
Algorithm Development Kit 1.0 |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectalgs.model.network.matching.BipartiteMatching
public class BipartiteMatching
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.
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 |
---|
public BipartiteMatching(java.lang.Object[] setS, java.lang.Object[] setT, java.lang.Object[][] pairs)
Note that the objects which make up the vertex sets must have properly
implements Object.hashCode()
and Object.equals(Object)
methods.
setS
- Set S being matched to TsetT
- Set T being matched to Spairs
- edges crossing from S to T
java.lang.RuntimeException
- if an error in input occurs.Method Detail |
---|
public java.util.Iterator<Pair> compute()
Return an Iterator of Pair objects that reflect the discovered matching.
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |