com.mhhe.clrs2e
Class FlowNetwork.FlowNetworkEdge

java.lang.Object
  |
  +--com.mhhe.clrs2e.AdjacencyListGraph.Edge
        |
        +--com.mhhe.clrs2e.FlowNetwork.FlowNetworkEdge

Enclosing class:

FlowNetwork

protected static class FlowNetwork.FlowNetworkEdge

extends AdjacencyListGraph.Edge

Inner class for flow network edges in adjacency lists. Adjacency lists are singly linked.

Field Summary

private double	capacity The capacity c(u,v) of this edge (u,v).
private double	netFlow The net flow f(u,v) for edge (u,v).
private double	residualCapacity The residual capacity cHat(u,v) = c(u,v) - f(u,v) for edge (u,v).
private FlowNetwork.FlowNetworkEdge	reverseEdge A reference to the reverse edge (v,u) for edge (u,v).

Fields inherited from class com.mhhe.clrs2e.AdjacencyListGraph.Edge

next, vertex

Constructor Summary

FlowNetwork.FlowNetworkEdge(com.mhhe.clrs2e.Vertex v, AdjacencyListGraph.Edge successor, double cap)
Creates a new edge.

Method Summary

double	getCapacity() Returns the capacity of this edge.
double	getNetFlow() Returns the net flow for this edge.
double	getResidualCapacity() Returns the residual capacity of this edge.
void	increaseNetFlow(double amount) Increases the net flow on this edge by the given amount, decreases the net flow on the reverse edge by the same amount, and updates the residual capacities of this edge and the reverse edge.
void	setReverseEdge(FlowNetwork.FlowNetworkEdge e) Sets the reference to the reverse edge.
void	zeroNetFlow() Zeros out the net flow on this edge and its reverse and updates residual capacities on both edges.

Methods inherited from class java.lang.Object

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

Field Detail

capacity

private final double capacity

The capacity c(u,v) of this edge (u,v).

netFlow

private double netFlow

The net flow f(u,v) for edge (u,v).

residualCapacity

private double residualCapacity

The residual capacity cHat(u,v) = c(u,v) - f(u,v) for edge (u,v).

reverseEdge

private FlowNetwork.FlowNetworkEdge reverseEdge

A reference to the reverse edge (v,u) for edge (u,v).

Constructor Detail

FlowNetwork.FlowNetworkEdge

public FlowNetwork.FlowNetworkEdge(com.mhhe.clrs2e.Vertex v,
                                   AdjacencyListGraph.Edge successor,
                                   double cap)

Creates a new edge. Leaves the reverseEdge instance variable alone.

Parameters:

v - The adjacent vertex.

successor - Successor edge to this one.

cap - The capacity of the new edge.

Method Detail

getCapacity

public double getCapacity()

Returns the capacity of this edge.

getNetFlow

public double getNetFlow()

Returns the net flow for this edge.

getResidualCapacity

public double getResidualCapacity()

Returns the residual capacity of this edge.

setReverseEdge

public void setReverseEdge(FlowNetwork.FlowNetworkEdge e)

Sets the reference to the reverse edge.

Parameters:

e - The reverse edge.

zeroNetFlow

public void zeroNetFlow()

Zeros out the net flow on this edge and its reverse and updates residual capacities on both edges.

increaseNetFlow

public void increaseNetFlow(double amount)

Increases the net flow on this edge by the given amount, decreases the net flow on the reverse edge by the same amount, and updates the residual capacities of this edge and the reverse edge. This method does not check that the residual capacity remains nonnegative.

Parameters:

amount - The amount by which this edge's flow is increased and the reverse edge's flow is decreased.