|
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
algs.model.network.Optimized
public class Optimized
Optimized implementation of Ford-Fulkerson that uses arrays for all storage. Ignore typed parameterizations of FlowNetwork since they aren't used in this implementation.
Field Summary |
---|
Fields inherited from class algs.model.network.FlowNetwork |
---|
numVertices, sinkIndex, sourceIndex |
Constructor Summary | |
---|---|
Optimized(int n,
int s,
int t,
java.util.Iterator<EdgeInfo> edges)
Load up information for this network problem. |
Method Summary | |
---|---|
int |
compute(int source,
int sink)
|
EdgeInfo |
edge(int start,
int end)
Subclasses provide this implementation, based upon their data structures. |
int |
getCost()
The optimized Ford-Fulkerson is not able to process costs. |
java.lang.Object |
getEdgeStructure()
Expect this to be unused. |
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 int |
processPath(int source,
int sink)
|
boolean |
search(int source,
int sink)
|
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 Optimized(int n, int s, int t, java.util.Iterator<EdgeInfo> edges)
Method Detail |
---|
public int compute(int source, int sink)
protected int processPath(int source, int sink)
public boolean search(int source, int sink)
public EdgeInfo edge(int start, int end)
FlowNetwork
If the forward edge doesn't exist, then null is returned.
edge
in class FlowNetwork
start
- the start index of desired edge.end
- the end index of desired edge.public java.lang.Object getEdgeStructure()
getEdgeStructure
in class FlowNetwork
public int getFlow()
FlowNetwork
getFlow
in class FlowNetwork
public int getCost()
getCost
in class FlowNetwork
public DoubleLinkedList<EdgeInfo> getMinCut()
FlowNetwork
getMinCut
in class FlowNetwork
public void validate() throws java.lang.IllegalStateException
FlowNetwork
A valid flow network satisfies three criteria:
validate
in class FlowNetwork
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 |