bcds.phison.alg
Class MaxFlowEK<V,E>

java.lang.Object
  bcds.phison.ra.RoutingAlgBase<V,E>
      bcds.phison.alg.MaxFlowEK<V,E>

public class MaxFlowEK<V,E>
extends RoutingAlgBase<V,E>

Implements the Edmonds-Karp algorithm to find the max-flow between a source-destination pair. This is loosely based on the Perl code for Graph::MaxFlow. The running time of Edmonds-Karp algorithm is in O(V E^2). Upon calling run(V, V), the following information can be retrieved:

• the maximum flow that can be sent from the source to the destination. The flow can be sent over a series of paths, not just one. These paths are not guaranteed to be disjoint.
• The list of paths found, with their respective flow capacities.

Note that MaxFlowEK does not implement the RoutingAlg interface.

The paths are found taking into account the residual capacity of each link, as reported by the TED object. Thus, links with zero residual capacity are (logically) removed from the topology.

Author:

Juan Segovia S.

Constructor Summary

MaxFlowEK(TED<V,E> ted)
Creates a new instance and saves the ted parameter for future use.

Method Summary

void	dumpState() Prints to stdout some internal information.
Path<V,E>	getPath(int n) Returns the n-th path (or subflow) that supports the previously computed max-flow, or null if n is out of range (there are not that many paths).
int	getPathCap(int n) Returns the capacity with which the n-th path contributes to the total max-flow, or 0 (zero) if n is out of range (there are not that many paths).
int	run(V src, V dest) Returns the (total) max-flow between src and dest.

Methods inherited from class bcds.phison.ra.RoutingAlgBase

buildPathFromParentNodes, commitBackupPath, commitWorkingPath, getBackupPath, getCost, getEnviron, getEnvParams, getName, getTED, getWorkingPath, offersProtection, setBackupPath, setRequest, setup, setWorkingPath, topologyHasChanged, uncommitBackupPath, uncommitWorkingPath

Methods inherited from class java.lang.Object

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

Constructor Detail

MaxFlowEK

public MaxFlowEK(TED<V,E> ted)

Creates a new instance and saves the ted parameter for future use.

Method Detail

getPath

public Path<V,E> getPath(int n)

Returns the n-th path (or subflow) that supports the previously computed max-flow, or null if n is out of range (there are not that many paths). Since a breadth-first search is used by run, the length of the path returned by getPath(k) is always <= getPath(k+1), where the length is measured in number of hops.

getPathCap

public int getPathCap(int n)

Returns the capacity with which the n-th path contributes to the total max-flow, or 0 (zero) if n is out of range (there are not that many paths).

run

public int run(V src,
               V dest)

Returns the (total) max-flow between src and dest. The result is zero if src and dest are the same or if they are disconnected.

dumpState

public void dumpState()

Prints to stdout some internal information.

Overrides:

dumpState in class RoutingAlgBase<V,E>