public class FlowNetwork extends Object
FlowNetwork
class represents a capacitated network
with vertices named 0 through V - 1, where each directed
edge is of type FlowEdge
and has a real-valued capacity
and flow.
It supports the following two primary operations: add an edge to the network,
iterate over all of the edges incident to or from a vertex. It also provides
methods for returning the number of vertices V and the number
of edges E. Parallel edges and self-loops are permitted.
This implementation uses an adjacency-lists representation, which
is a vertex-indexed array of Bag
objects.
All operations take constant time (in the worst case) except
iterating over the edges incident to a given vertex, which takes
time proportional to the number of such edges.
For additional documentation, see Section 6.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
FlowNetwork(In in)
Initializes a flow network from an input stream.
|
FlowNetwork(int V)
Initializes an empty flow network with
V vertices and 0 edges. |
FlowNetwork(int V,
int E)
Initializes a random flow network with
V vertices and E edges. |
Modifier and Type | Method and Description |
---|---|
void |
addEdge(FlowEdge e)
Adds the edge
e to the network. |
Iterable<FlowEdge> |
adj(int v)
Returns the edges incident on vertex
v (includes both edges pointing to
and from v ). |
int |
E()
Returns the number of edges in the edge-weighted graph.
|
Iterable<FlowEdge> |
edges() |
static void |
main(String[] args)
Unit tests the
FlowNetwork data type. |
String |
toString()
Returns a string representation of the flow network.
|
int |
V()
Returns the number of vertices in the edge-weighted graph.
|
public FlowNetwork(int V)
V
vertices and 0 edges.V
- the number of verticesIllegalArgumentException
- if V < 0
public FlowNetwork(int V, int E)
V
vertices and E edges.
The capacities are integers between 0 and 99 and the flow values are zero.V
- the number of verticesE
- the number of edgesIllegalArgumentException
- if V < 0
IllegalArgumentException
- if E < 0
public FlowNetwork(In in)
in
- the input streamIllegalArgumentException
- if the endpoints of any edge are not in prescribed rangeIllegalArgumentException
- if the number of vertices or edges is negativepublic int V()
public int E()
public void addEdge(FlowEdge e)
e
to the network.e
- the edgeIllegalArgumentException
- unless endpoints of edge are between
0
and V-1
public Iterable<FlowEdge> adj(int v)
v
(includes both edges pointing to
and from v
).v
- the vertexv
as an IterableIllegalArgumentException
- unless 0 <= v < V
public String toString()
public static void main(String[] args)
FlowNetwork
data type.args
- the command-line arguments