|
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 | ||||||||