edu.princeton.cs.algorithms

Class FlowNetwork

java.lang.Object

edu.princeton.cs.algorithms.FlowNetwork

public class FlowNetwork
extends Object

The 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 @link{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.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors

Constructor and Description
FlowNetwork(edu.princeton.cs.introcs.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.

Method Summary

Methods

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.

Methods inherited from class java.lang.Object

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

Constructor Detail

FlowNetwork

public FlowNetwork(int V)

Initializes an empty flow network with V vertices and 0 edges. param V the number of vertices

Throws:

IllegalArgumentException - if V < 0

FlowNetwork

public FlowNetwork(int V,
           int E)

Initializes a random flow network with V vertices and E edges. The capacities are integers between 0 and 99 and the flow values are zero. param V the number of vertices param E the number of edges

Throws:

IllegalArgumentException - if V < 0

IllegalArgumentException - if E < 0

FlowNetwork

public FlowNetwork(edu.princeton.cs.introcs.In in)

Initializes a flow network from an input stream. The format is the number of vertices V, followed by the number of edges E, followed by E pairs of vertices and edge capacities, with each entry separated by whitespace.

Parameters:

in - the input stream

Throws:

IndexOutOfBoundsException - if the endpoints of any edge are not in prescribed range

IllegalArgumentException - if the number of vertices or edges is negative

Method Detail

V

public int V()

Returns the number of vertices in the edge-weighted graph.

Returns:

the number of vertices in the edge-weighted graph

E

public int E()

Returns the number of edges in the edge-weighted graph.

Returns:

the number of edges in the edge-weighted graph

addEdge

public void addEdge(FlowEdge e)

Adds the edge e to the network.

Parameters:

e - the edge

Throws:

IndexOutOfBoundsException - unless endpoints of edge are between 0 and V-1

adj

public Iterable<FlowEdge> adj(int v)

Returns the edges incident on vertex v (includes both edges pointing to and from v).

Parameters:

v - the vertex

Returns:

the edges incident on vertex v as an Iterable

Throws:

IndexOutOfBoundsException - unless 0 <= v < V

edges

public Iterable<FlowEdge> edges()

toString

public String toString()

Returns a string representation of the flow network. This method takes time proportional to E + V.

Overrides:

toString in class Object

Returns:

the number of vertices V, followed by the number of edges E, followed by the V adjacency lists

main

public static void main(String[] args)

Unit tests the FlowNetwork data type.