net.sourceforge.combean.graph.alg.flow
Class AbstractAugmentingPathAlg

java.lang.Object
  net.sourceforge.combean.graph.alg.AbstractGraphAlg
      net.sourceforge.combean.graph.alg.flow.AbstractAugmentingPathAlg

All Implemented Interfaces:

AbstractFlowAlg, MaxFlowAlg, GraphAlgorithm

Direct Known Subclasses:

AugmentingPathBySimpleTraversalAlg

public abstract class AbstractAugmentingPathAlg
extends AbstractGraphAlg
implements MaxFlowAlg

Maximum flow algorithms which uses the augmenting path approach, i.e. which repeatedly augments the flow on an augmenting path until no such path can be found any more.

Field Summary

static double

TOTAL_FLOW_UNDEFINED

Constructor Summary

AbstractAugmentingPathAlg()
constructor

Method Summary

protected abstract FixedPath	findAugmentingPath(DirectedEdgeNeighborhoodGraphProp resG)
FixedDoubleEdgeMap	getFlowMap() Return the calculated flow.
Node	getSource()
Node	getTarget()
double	getTotalFlow() Get the value of the maximum flow.
protected void	init()
void	run() Execute the algorithm.
void	setEdgeCapacityMap(FixedDoubleEdgeMap edgeCapacities) Set the edge capacities.
void	setFlowEdgeMap(DoubleEdgeMap flowMap) Set the DoubleEdgeMap which is used to store the calculated flow.
void	setSource(Node s) Set the source node of the flow.
void	setTarget(Node t) Set the target node of the flow.

Methods inherited from class net.sourceforge.combean.graph.alg.AbstractGraphAlg

getGraph, setGraph

Methods inherited from class java.lang.Object

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

Methods inherited from interface net.sourceforge.combean.interfaces.graph.alg.GraphAlgorithm

getGraph, setGraph

Field Detail

TOTAL_FLOW_UNDEFINED

public static final double TOTAL_FLOW_UNDEFINED

See Also:

Constant Field Values

Constructor Detail

AbstractAugmentingPathAlg

public AbstractAugmentingPathAlg()

constructor

Method Detail

setEdgeCapacityMap

public void setEdgeCapacityMap(FixedDoubleEdgeMap edgeCapacities)

Description copied from interface: AbstractFlowAlg

Set the edge capacities.

Specified by:

setEdgeCapacityMap in interface AbstractFlowAlg

Parameters:

edgeCapacities - a map containing the edge capacities.

setFlowEdgeMap

public final void setFlowEdgeMap(DoubleEdgeMap flowMap)

Set the DoubleEdgeMap which is used to store the calculated flow. If not set, the corresponding advisor for this datastructure will be consulted.

Parameters:

flowMap - The flowMap to set.

getFlowMap

public FixedDoubleEdgeMap getFlowMap()

Description copied from interface: AbstractFlowAlg

Return the calculated flow. May only be called after the algorithm has been executed.

Specified by:

getFlowMap in interface AbstractFlowAlg

Returns:

the calculated flow.

getTotalFlow

public double getTotalFlow()

Description copied from interface: MaxFlowAlg

Get the value of the maximum flow. May only be called after the algorithm has been run.

Specified by:

getTotalFlow in interface MaxFlowAlg

Returns:

the value of the maximum flow.

setSource

public void setSource(Node s)

Description copied from interface: MaxFlowAlg

Set the source node of the flow.

Specified by:

setSource in interface MaxFlowAlg

Parameters:

s - the source node

setTarget

public void setTarget(Node t)

Description copied from interface: MaxFlowAlg

Set the target node of the flow.

Specified by:

setTarget in interface MaxFlowAlg

Parameters:

t - the target node.

run

public void run()

Description copied from interface: GraphAlgorithm

Execute the algorithm.

Specified by:

run in interface GraphAlgorithm

findAugmentingPath

protected abstract FixedPath findAugmentingPath(DirectedEdgeNeighborhoodGraphProp resG)

init

protected void init()

getSource

public final Node getSource()

Returns:

Returns the s.

getTarget

public final Node getTarget()

Returns:

Returns the t.