Package edu.princeton.cs.algs4

Class 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 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 Detail

      • FlowNetwork

        public FlowNetwork​(int V)
        Initializes an empty flow network with V vertices and 0 edges.
        Parameters:
        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.
        Parameters:
        V - the number of vertices
        E - the number of edges
        Throws:
        IllegalArgumentException - if V < 0
        IllegalArgumentException - if E < 0

      • FlowNetwork

        public FlowNetwork​(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:
        IllegalArgumentException - 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:
        IllegalArgumentException - 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:
        IllegalArgumentException - unless 0 <= v < V

      • 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.
        Parameters:
        args - the command-line arguments