com.mhhe.clrs2e
Class FlowNetwork

java.lang.Object
  |
  +--com.mhhe.clrs2e.AdjacencyListGraph
        |
        +--com.mhhe.clrs2e.FlowNetwork

All Implemented Interfaces:

Graph

public class FlowNetwork

extends AdjacencyListGraph

Implementation of a flow network, using adjacency lists. The representation is based on the superclass AdjacencyListGraph, but with some significant differences. The inner class FlowNetwork.FlowNetworkEdge is a subclass of AdjacencyListGraph.Edge, with additional instance variables for the edge's capacity, net flow, and residual capacity. Whenever edge (u,v) is present in the flow network, the reverse edge (v,u) must also be present; the reason is that, in order to maintain skew symmetry, when updating the flow on edge (u,v), we must also update the flow on the reverse edge (v,u). The reverse edge must be present in order to do so. Moreover, each FlowNetworkEdge object also includes a reference to its reverse edge. If edge (u,v) should be in the flow network but the reverse edge (v,u) should not, then set the capacity of (v,u) to 0. The FlowNetworkEdge class includes methods to access an edge's net flow and capacity.

The iterator for flow network edges, FlowNetwork.EdgeIterator, implements the FlowNetworkEdgeIterator interface. When creating this type of iterator, we specify whether the iterator should return only edges in the residual network (i.e., those with positive residual capacity), or all edges.

Finally, the FlowNetwork class contains a method, getFlowValue(com.mhhe.clrs2e.Vertex), which returns the value of the current flow, given the net flows on the edges.

Nested Class Summary

class	FlowNetwork.EdgeIterator Inner class that overrides AdjacencyListGraph.EdgeIterator to implement FlowNetworkEdgeIterator.
protected static class	FlowNetwork.FlowNetworkEdge Inner class for flow network edges in adjacency lists.

Nested classes inherited from class com.mhhe.clrs2e.AdjacencyListGraph

AdjacencyListGraph.AdjListInfo, AdjacencyListGraph.VertexIterator

Field Summary

Fields inherited from class com.mhhe.clrs2e.AdjacencyListGraph

adj, directed, e, lastAdded

Constructor Summary

FlowNetwork(int cardV)
Creates an empty FlowNetwork.

Method Summary

void	addEdge(int u, int v) Unsupported, since edges in a flow network must have capacities.
void	addEdge(int u, int v, double cuv, double cvu) Adds an edge (u,v) and its reverse edge (v,u) to this graph.
void	addEdge(com.mhhe.clrs2e.Vertex u, com.mhhe.clrs2e.Vertex v) Unsupported, since edges in a flow network must have capacities.
void	addEdge(com.mhhe.clrs2e.Vertex u, com.mhhe.clrs2e.Vertex v, double cuv, double cvu) Adds an edge (u,v) and its reverse edge (v,u) to this graph.
java.util.Iterator	edgeIterator(int u) Returns an iterator that iterates through all the edges (regardless of residual capacity) incident on a given vertex in a flow network.
java.util.Iterator	edgeIterator(com.mhhe.clrs2e.Vertex u) Returns an iterator that iterates through all the edges (regardless of residual capacity) incident on a given vertex in a flow network.
com.mhhe.clrs2e.FlowNetworkEdgeIterator	flowNetworkEdgeIterator(int u, boolean residual) Returns an iterator, of type FlowNetworkEdgeIterator (so that the caller does not need to cast the result), that iterates through the edges incident on a given vertex in a flow network.
com.mhhe.clrs2e.FlowNetworkEdgeIterator	flowNetworkEdgeIterator(com.mhhe.clrs2e.Vertex u, boolean residual) Returns an iterator, of type FlowNetworkEdgeIterator (so that the caller does not need to cast the result), that iterates through the edges incident on a given vertex in a flow network.
double	getFlowValue(com.mhhe.clrs2e.Vertex s) Returns the value of the flow, which is the sum of the net flows out of the source.
java.lang.String	toString() Returns the String representation of this flow network.

Methods inherited from class com.mhhe.clrs2e.AdjacencyListGraph

addVertex, addVertex, addVertex, getCardE, getCardV, getVertex, isDirected, makeEmptyGraph, useSameVertices, vertexIterator

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

FlowNetwork

public FlowNetwork(int cardV)

Creates an empty FlowNetwork. It is a directed graph.

Parameters:

cardV - How many vertices this graph will have.

Method Detail

addEdge

public void addEdge(com.mhhe.clrs2e.Vertex u,
                    com.mhhe.clrs2e.Vertex v)

Unsupported, since edges in a flow network must have capacities.

Specified by:

addEdge in interface Graph

Overrides:

addEdge in class AdjacencyListGraph

Parameters:

u - One vertex.

v - The other vertex.

Throws:

java.lang.UnsupportedOperationException - always.

addEdge

public void addEdge(int u,
                    int v)

Unsupported, since edges in a flow network must have capacities.

Specified by:

addEdge in interface Graph

Overrides:

addEdge in class AdjacencyListGraph

Parameters:

u - The index of one vertex.

v - The index of the other vertex.

Throws:

java.lang.UnsupportedOperationException - always.

addEdge

public void addEdge(com.mhhe.clrs2e.Vertex u,
                    com.mhhe.clrs2e.Vertex v,
                    double cuv,
                    double cvu)

Adds an edge (u,v) and its reverse edge (v,u) to this graph. The edge is specified by a pair of Vertex objects.

Parameters:

u - One vertex.

v - The other vertex.

cuv - The capacity of edge (u,v); 0 if (u,v) is not in this flow network.

cvu - The capacity of edge (v,u); 0 if (v,u) is not in this flow network.

addEdge

public void addEdge(int u,
                    int v,
                    double cuv,
                    double cvu)

Adds an edge (u,v) and its reverse edge (v,u) to this graph. The edge is specified by a pair of vertex indices.

Parameters:

u - One vertex.

v - The other vertex.

cuv - The capacity of edge (u,v); 0 if (u,v) is not in this flow network.

cvu - The capacity of edge (v,u); 0 if (v,u) is not in this flow network.

edgeIterator

public java.util.Iterator edgeIterator(com.mhhe.clrs2e.Vertex u)

Returns an iterator that iterates through all the edges (regardless of residual capacity) incident on a given vertex in a flow network. Each incident edge is indicated by the corresponding adjacent vertex.

Specified by:

edgeIterator in interface Graph

Overrides:

edgeIterator in class AdjacencyListGraph

Parameters:

u - The vertex whose incident edges are returned by the iterator.

edgeIterator

public java.util.Iterator edgeIterator(int u)

Returns an iterator that iterates through all the edges (regardless of residual capacity) incident on a given vertex in a flow network. Each incident edge is indicated by the corresponding adjacent vertex.

Specified by:

edgeIterator in interface Graph

Overrides:

edgeIterator in class AdjacencyListGraph

Parameters:

u - The index of the vertex whose incident edges are returned by the iterator.

flowNetworkEdgeIterator

public com.mhhe.clrs2e.FlowNetworkEdgeIterator flowNetworkEdgeIterator(com.mhhe.clrs2e.Vertex u,
                                                                       boolean residual)

Returns an iterator, of type FlowNetworkEdgeIterator (so that the caller does not need to cast the result), that iterates through the edges incident on a given vertex in a flow network. Each incident edge is indicated by the corresponding adjacent vertex.

Parameters:

u - The vertex whose incident edges are returned by the iterator.

residual - true if this iterator is to return only edges in the residual network, false if it is to return all edges.

flowNetworkEdgeIterator

public com.mhhe.clrs2e.FlowNetworkEdgeIterator flowNetworkEdgeIterator(int u,
                                                                       boolean residual)

Returns an iterator, of type FlowNetworkEdgeIterator (so that the caller does not need to cast the result), that iterates through the edges incident on a given vertex in a flow network. Each incident edge is indicated by the corresponding adjacent vertex.

Parameters:

u - The index of the vertex whose incident edges are returned by the iterator.

residual - true if this iterator is to return only edges in the residual network, false if it is to return all edges.

getFlowValue

public double getFlowValue(com.mhhe.clrs2e.Vertex s)

Returns the value of the flow, which is the sum of the net flows out of the source.

Parameters:

s - The source vertex.

toString

public java.lang.String toString()

Returns the String representation of this flow network.

Overrides:

toString in class AdjacencyListGraph