|
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 vertices| Method 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)
FlowNetworkIf 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()
FlowNetworkSubclasses 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
FlowNetworkA 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 | ||||||||