|
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.FlowNetwork<E>
E - type parameter to describe Edge Structure used by each algorithm
variation.public abstract class FlowNetwork<E>
Parent abstract class for representing a flow network problem to be solved.
Subclasses included an array-based implementation and one using adjacency lists.
| Field Summary | |
|---|---|
int |
numVertices
Number of vertices in the graph. |
int |
sinkIndex
Index of the sink vertex. |
int |
sourceIndex
Index of the source vertex. |
| Constructor Summary | |
|---|---|
FlowNetwork(int numVertices,
int srcIndex,
int sinkindex)
Store relevant information about the FlowNetwork graph. |
|
| Method Summary | |
|---|---|
abstract EdgeInfo |
edge(int start,
int end)
Subclasses provide this implementation, based upon their data structures. |
abstract int |
getCost()
Return the cost of the network solution. |
abstract E |
getEdgeStructure()
Subclasses are responsible for interpreting the info in the appropriate data structure. |
abstract int |
getFlow()
After the termination of the network flow algorithm, this method returns the final flow pushed out of the source. |
abstract DoubleLinkedList<EdgeInfo> |
getMinCut()
After the termination of the network flow algorithms, the last round of labeled vertices (including the source) can be grouped into a set X while the unlabeled vertices are grouped into X'. |
abstract void |
validate()
Validate the FlowNetwork. |
| Methods inherited from class java.lang.Object |
|---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Field Detail |
|---|
public final int sourceIndex
public final int sinkIndex
public final int numVertices
| Constructor Detail |
|---|
public FlowNetwork(int numVertices,
int srcIndex,
int sinkindex)
numVertices - the number of vertices in the Flow NetworksrcIndex - the index of the vertex designated to be the sourcesinkindex - the index of the vertex designated to be the sink| Method Detail |
|---|
public abstract E getEdgeStructure()
public abstract EdgeInfo edge(int start,
int end)
If the forward edge doesn't exist, then null is returned.
start - the start index of desired edge.end - the end index of desired edge.
public abstract void validate()
throws java.lang.IllegalStateException
A valid flow network satisfies three criteria:
java.lang.IllegalStateException - if any of these criteria is violated.public abstract DoubleLinkedList<EdgeInfo> getMinCut()
public abstract int getFlow()
public abstract int getCost()
Subclasses are free to override with more efficient implementations, so long as they are correct :)
|
Algorithm Development Kit 1.0 | ||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||