fr.inria.opengve.bridge.algorithms.directed
Class EdmondsKarp<V,A extends Arc<V>,G extends Graph<V,A>>

java.lang.Object
  java.util.Observable
      fr.inria.opengve.bridge.algorithms.StepAlgo<V,A>
          fr.inria.opengve.bridge.algorithms.directed.EdmondsKarp<V,A,G>

Type Parameters:

V - the type of vertices

A - the type of arcs

G - the type of graph

All Implemented Interfaces:

java.lang.Runnable

public abstract class EdmondsKarp<V,A extends Arc<V>,G extends Graph<V,A>>
extends StepAlgo<V,A>

This algorithms is the implementation of the Edmonds-Karp version of the Ford-Fulkerson algorithms. This implementation is based on two books :

- Introduction a l'algortihmique par T. Cormen, C Leiserson et R. Rivest (edition Dunod)

- Graphs, Networks and Algorithms by D. Jungnickel (Algorithms and Computation in Mathematics Volume 5 edition Springer)

You must note that in demo mode EdmondsKarp(Graph, Map, boolean) call with true the Map given by user is modified to reflect the color change of Arc. New entry are created with "Color" as name and no context. The value associated is the String representation of the return of method Color.getRGB().

Author:

fabrice.peix@sophia.inria.fr

Nested Class Summary

Nested classes/interfaces inherited from class fr.inria.opengve.bridge.algorithms.StepAlgo

StepAlgo.StepAlgoMessage, StepAlgo.StepAlgoMessageType

Field Summary

static java.lang.String	flowName The name used during the execution of algorithms for storing flow.
static java.lang.String	residualCapacityName The name used during the execution of algorithms for storing residual capacity.

Constructor Summary

EdmondsKarp(G g, Map map)
Constructor.

EdmondsKarp(G g, Map map, boolean stepMode)

Method Summary

protected abstract A	createArc(V tail, V head) Create a new Arc.
protected abstract AugmentingPath<V,A,G>	createAugmentingPath(G g) Create a new AugmentingPath.
protected abstract G	createGraph(HierarchicalSet<V> vertexSet) Create a new empty graph based on a given vertex set.
protected abstract Flow<V,A>	createSTFlow(G g) Return a new empty flow.
HierarchicalSet<V>	getDestinationSet() Returns the subSet of vertices that are chunked with the destination
Flow<V,A>	getFlow() Return the flow that goes from source to destination.
HierarchicalSet<A>	getLinkSet() Compute and returns the subSet of links that are cutted by the subdivision of the vertices set in source set and destination set.
HierarchicalSet<V>	getSourceSet() Returns the subSet of vertices that are chunked with the source
void	run() Run the algorithm.
void	setCapacityContext(java.lang.Object context) Set the context used to load capacity of edges in the map.
void	setCapacityName(java.lang.String name) Set the name used to load capacity of edges in the map.
void	setDestination(V destination) Set the destination of the computed flow.
void	setSource(V source) Set the source of the computed flow.

Methods inherited from class fr.inria.opengve.bridge.algorithms.StepAlgo

ends, getDemoMode, getStepMode, isEnded, nextStep, notifyGraphDisplayRequest, notifyGraphDisplayRequest, notifyLabelEdgesRequest, notifyLabelVerticesRequest, pause, setPauseMode, setTime, start

Methods inherited from class java.util.Observable

addObserver, clearChanged, countObservers, deleteObserver, deleteObservers, hasChanged, notifyObservers, notifyObservers, setChanged

Methods inherited from class java.lang.Object

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

Field Detail

residualCapacityName

public static final java.lang.String residualCapacityName

The name used during the execution of algorithms for storing residual capacity.

See Also:

Constant Field Values

flowName

public static final java.lang.String flowName

The name used during the execution of algorithms for storing flow.

See Also:

Constant Field Values

Constructor Detail

EdmondsKarp

public EdmondsKarp(G g,
                   Map map)

Constructor.

Parameters:

g - The graph on which the algorithms is apply.

map - The map associating each arcs with his capacity.

EdmondsKarp

public EdmondsKarp(G g,
                   Map map,
                   boolean stepMode)

Parameters:

g - The graph on which the algorithms is apply.

map - The map associating each arcs with his capacity.

stepMode - Set the stepMode of the algorithms.

Method Detail

createGraph

protected abstract G createGraph(HierarchicalSet<V> vertexSet)

Create a new empty graph based on a given vertex set.

Parameters:

vertexSet - The vertexSet on which is based the new graph.

Returns:

A new empty graph.

createAugmentingPath

protected abstract AugmentingPath<V,A,G> createAugmentingPath(G g)

Create a new AugmentingPath.

Parameters:

g - The graph on wich is applied the new AugmentingPath.

Returns:

The new AugmentingPath.

createSTFlow

protected abstract Flow<V,A> createSTFlow(G g)

Return a new empty flow. Note that this flow can be a specific implementation where there is only one source and one destination.

Parameters:

g - The support graph.

Returns:

The new empty flow.

createArc

protected abstract A createArc(V tail,
                               V head)

Create a new Arc.

Parameters:

tail - The tail of the Arc.

head - The head of the Arc.

Returns:

The new created Arc.

setSource

public void setSource(V source)

Set the source of the computed flow.

Parameters:

source - The vertex used as source of the flow.

setDestination

public void setDestination(V destination)

Set the destination of the computed flow.

Parameters:

destination - The vertex used as destination of the flow.

setCapacityName

public void setCapacityName(java.lang.String name)

Set the name used to load capacity of edges in the map. By default this name is "Capacity".

Parameters:

name - The new name used to load capacity.

setCapacityContext

public void setCapacityContext(java.lang.Object context)

Set the context used to load capacity of edges in the map. By default this context is the graph on which maximun flow is computed. You can specify null for using default context.

Parameters:

context - The context used to load capcity of edges in the map.

getFlow

public Flow<V,A> getFlow()

Return the flow that goes from source to destination.

Returns:

The max flow from source to destination.

getDestinationSet

public HierarchicalSet<V> getDestinationSet()

Returns the subSet of vertices that are chunked with the destination

Returns:

the destinationSet

getSourceSet

public HierarchicalSet<V> getSourceSet()

Returns the subSet of vertices that are chunked with the source

Returns:

the sourceSet

getLinkSet

public HierarchicalSet<A> getLinkSet()

Compute and returns the subSet of links that are cutted by the subdivision of the vertices set in source set and destination set.

Returns:

The set of edges corresponding to the minimal cut.

run

public void run()

Description copied from class: StepAlgo

Run the algorithm.

Specified by:

run in interface java.lang.Runnable

Specified by:

run in class StepAlgo<V,A extends Arc<V>>