Package edu.princeton.cs.algs4

Class FlowEdge

  • public class FlowEdge
extends Object
    The FlowEdge class represents a capacitated edge with a flow in a FlowNetwork. Each edge consists of two integers (naming the two vertices), a real-valued capacity, and a real-valued flow. The data type provides methods for accessing the two endpoints of the directed edge and the weight. It also provides methods for changing the amount of flow on the edge and determining the residual capacity of the edge.

    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 Description
      FlowEdge​(int v, int w, double capacity)
      Initializes an edge from vertex v to vertex w with the given capacity and zero flow.
      FlowEdge​(int v, int w, double capacity, double flow)
      Initializes an edge from vertex v to vertex w with the given capacity and flow.
      FlowEdge​(FlowEdge e)
      Initializes a flow edge from another flow edge.

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void addResidualFlowTo​(int vertex, double delta)
      Increases the flow on the edge in the direction to the given vertex.
      double capacity()
      Returns the capacity of the edge.
      double flow()
      Returns the flow on the edge.
      int from()
      Returns the tail vertex of the edge.
      static void main​(String[] args)
      Unit tests the FlowEdge data type.
      int other​(int vertex)
      Returns the endpoint of the edge that is different from the given vertex (unless the edge represents a self-loop in which case it returns the same vertex).
      double residualCapacityTo​(int vertex)
      Returns the residual capacity of the edge in the direction to the given vertex.
      int to()
      Returns the head vertex of the edge.
      String toString()
      Returns a string representation of the edge.

    • Constructor Detail

      • FlowEdge

        public FlowEdge​(int v,
                int w,
                double capacity)
        Initializes an edge from vertex v to vertex w with the given capacity and zero flow.
        Parameters:
        v - the tail vertex
        w - the head vertex
        capacity - the capacity of the edge
        Throws:
        IllegalArgumentException - if either v or w is a negative integer
        IllegalArgumentException - if capacity < 0.0

      • FlowEdge

        public FlowEdge​(int v,
                int w,
                double capacity,
                double flow)
        Initializes an edge from vertex v to vertex w with the given capacity and flow.
        Parameters:
        v - the tail vertex
        w - the head vertex
        capacity - the capacity of the edge
        flow - the flow on the edge
        Throws:
        IllegalArgumentException - if either v or w is a negative integer
        IllegalArgumentException - if capacity is negative
        IllegalArgumentException - unless flow is between 0.0 and capacity.

      • FlowEdge

        public FlowEdge​(FlowEdge e)
        Initializes a flow edge from another flow edge.
        Parameters:
        e - the edge to copy

    • Method Detail

      • from

        public int from()
        Returns the tail vertex of the edge.
        Returns:
        the tail vertex of the edge

      • to

        public int to()
        Returns the head vertex of the edge.
        Returns:
        the head vertex of the edge

      • capacity

        public double capacity()
        Returns the capacity of the edge.
        Returns:
        the capacity of the edge

      • flow

        public double flow()
        Returns the flow on the edge.
        Returns:
        the flow on the edge

      • other

        public int other​(int vertex)
        Returns the endpoint of the edge that is different from the given vertex (unless the edge represents a self-loop in which case it returns the same vertex).
        Parameters:
        vertex - one endpoint of the edge
        Returns:
        the endpoint of the edge that is different from the given vertex (unless the edge represents a self-loop in which case it returns the same vertex)
        Throws:
        IllegalArgumentException - if vertex is not one of the endpoints of the edge

      • residualCapacityTo

        public double residualCapacityTo​(int vertex)
        Returns the residual capacity of the edge in the direction to the given vertex.
        Parameters:
        vertex - one endpoint of the edge
        Returns:
        the residual capacity of the edge in the direction to the given vertex If vertex is the tail vertex, the residual capacity equals capacity() - flow(); if vertex is the head vertex, the residual capacity equals flow().
        Throws:
        IllegalArgumentException - if vertex is not one of the endpoints of the edge

      • addResidualFlowTo

        public void addResidualFlowTo​(int vertex,
                              double delta)
        Increases the flow on the edge in the direction to the given vertex. If vertex is the tail vertex, this increases the flow on the edge by delta; if vertex is the head vertex, this decreases the flow on the edge by delta.
        Parameters:
        vertex - one endpoint of the edge
        delta - amount by which to increase flow
        Throws:
        IllegalArgumentException - if vertex is not one of the endpoints of the edge
        IllegalArgumentException - if delta makes the flow on the edge either negative or larger than its capacity
        IllegalArgumentException - if delta is NaN

      • toString

        public String toString()
        Returns a string representation of the edge.
        Overrides:
        toString in class Object
        Returns:
        a string representation of the edge

      • main

        public static void main​(String[] args)
        Unit tests the FlowEdge data type.
        Parameters:
        args - the command-line arguments