|
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<VertexStructure[]>
algs.model.network.FlowNetworkAdjacencyList
public class FlowNetworkAdjacencyList
Store information regarding the graph as an adjacency list.
Several key steps in this algorithm depend on identifying both the forward edges leaving a vertex Vi as well as the incoming edges into a vertex. If we only stored the forward directed edges, we would have to scan all remaining vertices to locate any that have outgoing edges into Vi.
For this reason, we maintain two separate forward and backward edge lists.
This means we have twice as many edges as are needed. The structure used to
maintain both lists is VertexStructure
.
Field Summary |
---|
Fields inherited from class algs.model.network.FlowNetwork |
---|
numVertices, sinkIndex, sourceIndex |
Constructor Summary | |
---|---|
FlowNetworkAdjacencyList(int numVertices,
int srcIndex,
int tgtIndex,
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)
Given an adjacency list for vertex 'n', find the edge (if it exists) from start to end. |
int |
getCost()
Return the cost of the network solution. |
VertexStructure[] |
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'. |
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 FlowNetworkAdjacencyList(int numVertices, int srcIndex, int tgtIndex, java.util.Iterator<EdgeInfo> edges)
numVertices
- the number of vertices in the Flow NetworksrcIndex
- the index of the vertex designated to be the sourcetgtIndex
- the index of the vertex designated to be the sinkedges
- an iterator of EdgeInfo objects representing edge capacitiesFlowNetwork.FlowNetwork(int, int, int)
Method Detail |
---|
public VertexStructure[] getEdgeStructure()
FlowNetwork
getEdgeStructure
in class FlowNetwork<VertexStructure[]>
FlowNetwork.getEdgeStructure()
public EdgeInfo edge(int start, int end)
edge
in class FlowNetwork<VertexStructure[]>
start
- index of start vertexend
- index of end vertex.
null
otherwise.public DoubleLinkedList<EdgeInfo> getMinCut()
FlowNetwork
getMinCut
in class FlowNetwork<VertexStructure[]>
public int getFlow()
FlowNetwork
getFlow
in class FlowNetwork<VertexStructure[]>
public int getCost()
FlowNetwork
Subclasses are free to override with more efficient implementations, so long as they are correct :)
getCost
in class FlowNetwork<VertexStructure[]>
public void validate() throws java.lang.IllegalStateException
A valid flow network satisfies three criteria:
validate
in class FlowNetwork<VertexStructure[]>
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 |