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