edu.princeton.cs.algorithms

Class FlowEdge

java.lang.Object

edu.princeton.cs.algorithms.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 and Description
FlowEdge(FlowEdge e) Initializes a flow edge from another flow edge.
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.

Method Summary

Methods

Modifier and Type	Method and 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.

Methods inherited from class java.lang.Object

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

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:

IndexOutOfBoundsException - if either v or w is a negative integer

IllegalArgumentException - if capacity is negative

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:

IndexOutOfBoundsException - 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

Throws:

IllegalArgumentException - if vertex is not one of the endpoints of the edge

IllegalArgumentException - if delta makes the flow on 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.