|
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.OptimizedFlowNetwork
public class OptimizedFlowNetwork
Store information regarding the graph in a two-dimensional matrix.
FordFulkerson
implementation.
Field Summary | |
---|---|
static boolean |
BACKWARD
Declares a path in the augmenting path follows a backward edge. |
static boolean |
FORWARD
Declares a path in the augmenting path follows a forward edge. |
Constructor Summary | |
---|---|
OptimizedFlowNetwork(int numVertices,
int srcIndex,
int sinkIndex,
java.util.Iterator<EdgeInfo> edges)
Construct an instance of the FlowNetwork problem using optimized array structure to solve problem. |
Method Summary | |
---|---|
int |
compute(int source,
int sink)
Compute the Maximal flow for the given flow network. |
boolean |
findAugmentingPath(int source,
int sink)
Locate an augmenting path in the Flow Network from the source vertex to the sink. |
DoubleLinkedList<EdgeInfo> |
getMinCut()
|
int |
getSink()
|
int |
getSource()
|
protected int |
processPath(int source,
int sink)
Augments the flows within the network along the path found from source to sink. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
public static final boolean FORWARD
public static final boolean BACKWARD
Constructor Detail |
---|
public OptimizedFlowNetwork(int numVertices, int srcIndex, int sinkIndex, java.util.Iterator<EdgeInfo> edges)
We use the same input representation so we can properly compare the performance of this implementation.
numVertices
- the number of vertices in the Flow NetworksrcIndex
- the index of the source vertexsinkIndex
- the index of the sink vertexedges
- an iterator of EdgeInfo objects representing edge capacitiesFlowNetwork.FlowNetwork(int, int, int)
Method Detail |
---|
public int compute(int source, int sink)
The results of the computation are stored within the network object. Specifically, the final labeling of vertices computes the set S of nodes which is disjoint from the unlabeled vertices which form the set T. Together, S and T represent the disjoint split of the graph into two sets whose connecting edges for the min-cut, in other words, the forward edges from S to T all have flow values which equal their capacity. Thus no additional augmentations are possible.
source
- the index of the source vertexsink
- the index of the sink vertex
java.lang.Exception
- if the graph structure is not a flow network.protected int processPath(int source, int sink)
Walking backwards from the sink vertex to the source vertex, this updates the flow values for the edges in the augmenting path.
Note that the available units in the sinkIndex are used as the additive value (for forward edges) and the subtractive value (for backward edges).
source
- source index of the augmenting pathsink
- sink index of the augmenting pathpublic DoubleLinkedList<EdgeInfo> getMinCut()
public boolean findAugmentingPath(int source, int sink)
Path is stored within the vertices[] array by traversing in reverse order from the sinkIndex.
Assume path always fits within queue size of length QUEUE_SIZE
source
- index of source vertexsink
- index of sink vertex
public int getSink()
public int getSource()
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |