|
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<EdgeInfo[][]>
algs.model.network.FlowNetworkArray
public class FlowNetworkArray
Store information regarding the graph in a two-dimensional matrix. The matrix may be either sparse or dense, depending upon the problem at hand.
Field Summary |
---|
Fields inherited from class algs.model.network.FlowNetwork |
---|
numVertices, sinkIndex, sourceIndex |
Constructor Summary | |
---|---|
protected |
FlowNetworkArray(int sourceIndex,
int sinkIndex,
int numVertices)
Minimal constructor for use by subclasses. |
|
FlowNetworkArray(int numVertices,
int srcIndex,
int sinkIndex,
java.util.Iterator<EdgeInfo> edges)
Construct an instance of the FlowNetwork problem using a two-dimensional array to store the edge information. |
Method Summary | |
---|---|
EdgeInfo |
edge(int start,
int end)
Subclasses provide this implementation, based upon their data structures. |
int |
getCost()
Return the cost of the network solution. |
EdgeInfo[][] |
getEdgeStructure()
Subclasses are responsible for interpreting the info in the appropriate data structure. |
int |
getFlow()
After the termination of the network flow algorithm, this method returns the final flow pushed out of the source. |
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'. |
protected void |
populate(java.util.Iterator<EdgeInfo> edges)
Helper method to populate edges. |
java.lang.String |
toString()
Useful for debugging. |
void |
validate()
Validate the FlowNetwork. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Constructor Detail |
---|
public FlowNetworkArray(int numVertices, int srcIndex, int sinkIndex, java.util.Iterator<EdgeInfo> edges)
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 sinkedges
- an iterator of EdgeInfo objects representing edge capacitiesFlowNetwork.FlowNetwork(int, int, int)
protected FlowNetworkArray(int sourceIndex, int sinkIndex, int numVertices)
sourceIndex
- the sourceIndex to use for network (typically 0)sinkIndex
- the sinkIndex to use for networknumVertices
- the number of verticesMethod Detail |
---|
protected void populate(java.util.Iterator<EdgeInfo> edges)
edges
- Iterator of all edges in the network.public EdgeInfo[][] getEdgeStructure()
FlowNetwork
getEdgeStructure
in class FlowNetwork<EdgeInfo[][]>
public EdgeInfo edge(int start, int end)
FlowNetwork
If the forward edge doesn't exist, then null is returned.
edge
in class FlowNetwork<EdgeInfo[][]>
start
- the start index of desired edge.end
- the end index of desired edge.public DoubleLinkedList<EdgeInfo> getMinCut()
FlowNetwork
getMinCut
in class FlowNetwork<EdgeInfo[][]>
public int getFlow()
FlowNetwork
getFlow
in class FlowNetwork<EdgeInfo[][]>
public int getCost()
FlowNetwork
Subclasses are free to override with more efficient implementations, so long as they are correct :)
getCost
in class FlowNetwork<EdgeInfo[][]>
public void validate() throws java.lang.IllegalStateException
FlowNetwork
A valid flow network satisfies three criteria:
validate
in class FlowNetwork<EdgeInfo[][]>
java.lang.IllegalStateException
- if any of these criteria is violated.public java.lang.String toString()
toString
in class java.lang.Object
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |