Class PushRelabel

java.lang.Object
  |
  +--PushRelabel

All Implemented Interfaces:

AnimatedAlgorithm, Runnable

public class PushRelabel

extends Object

implements AnimatedAlgorithm, Runnable

Constructor Summary

PushRelabel(Digraph g, EdgeRProperty capacity, Vertex s, Vertex t, PushRelabelVisitor visitor)           Prepares an instance for the MAX-FLOW-PROBLEM.

 

Method Summary
EdgeRProperty	getFlow()
void	init()           Prepares this instance to execute the Preflow-Push-Relabel algorithm once.
static void	main(String[] argv)           Reads file argv[0] which should contain properties capacity and label, constructs new PushRelabel instance, calls run and getFlow on it.
void	run()           Executes the Preflow-Push-Relabel algorithm to construct a maximal flow for the network encoded by this instance.
static boolean	targetReachableFromSource(Digraph g, Vertex source, Vertex target)           Just performs a recursive depth-first-search to decide whether there exists a directed source->target path in the digraph g.

 

Methods inherited from class java.lang.Object

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

 

Constructor Detail

PushRelabel

public PushRelabel(Digraph g,
                   EdgeRProperty capacity,
                   Vertex s,
                   Vertex t,
                   PushRelabelVisitor visitor)
            throws IllegalArgumentException

Prepares an instance for the MAX-FLOW-PROBLEM. The Preflow-Push-Relabel algorithm itself is executed by a call to run(), the result is available through getFlow().

• Each of the arguments must not be null.
• The capacity-property must be defined for the given digraph g, as well as s and t must belong to g.
• The given capacity-property must be convertable to an integer edge property.
• The capacities must not be negative.
• The target t must be reachable from the source s

Parameters:

g - the digraph in which you want to construct a MAX-FLOW

capacity - the upper capacities of the edges, where we assume the lower capacities to be always zero

s - the source of the MAX-FLOW to be constructed

t - the target of the MAX-FLOW to be constructed

visitor - a visitor for logging important steps of the algorithm

Throws:

IllegalArgumentException - iff one of the above preconditions mentioned above is not fulfilled by the parameters

See Also:

run(), getFlow(), targetReachableFromSource(Digraph, Vertex, Vertex), GraphPropertyFactory#convert2IntEdgeProperty(gabl.hier.EdgeListGraph, EdgeRProperty)

targetReachableFromSource

public static boolean targetReachableFromSource(Digraph g,
                                                Vertex source,
                                                Vertex target)

Just performs a recursive depth-first-search to decide whether there exists a directed source->target path in the digraph g.

init

public void init()

Prepares this instance to execute the Preflow-Push-Relabel algorithm once.

Specified by:

init in interface AnimatedAlgorithm

run

public void run()

Executes the Preflow-Push-Relabel algorithm to construct a maximal flow for the network encoded by this instance. The flow itself will be available through getFlow(). As this is an intelligent run, it calls init(), if necessary.

Specified by:

run in interface AnimatedAlgorithm

See Also:

getFlow(), init()

getFlow

public EdgeRProperty getFlow()
                      throws IllegalStateException

Throws:

IllegalStateException - if either there is no flow available because run() has not yet been invoked, or an internal error prevented PushRelabel to construct a flow

main

public static void main(String[] argv)

Reads file argv[0] which should contain properties capacity and label, constructs new PushRelabel instance, calls run and getFlow on it.