org.jgrapht.alg.flow

Class PushRelabelMFImpl<V,E>

java.lang.Object

org.jgrapht.alg.flow.MaximumFlowAlgorithmBase<V,E>

org.jgrapht.alg.flow.PushRelabelMFImpl<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MaximumFlowAlgorithm<V,E>, MinimumSTCutAlgorithm<V,E>

public class PushRelabelMFImpl<V,E>
extends MaximumFlowAlgorithmBase<V,E>

Push-relabel maximum flow algorithm designed by Andrew V. Goldberg and Robert Tarjan. Current implementation complexity upper-bound is $O(V^3)$. For more details see: "A new approach to the maximum flow problem" by Andrew V. Goldberg and Robert Tarjan STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing

This implementation is based on On Implementing the Push—Relabel Method for the Maximum Flow Problem by B. V. Cherkassky and A.V. Goldberg (Cherkassky, B. & Goldberg, A. Algorithmica (1997) 19: 390. https://doi.org/10.1007/PL00009180) and Introduction to Algorithms (3rd Edition).

This class can also computes minimum $s-t$ cuts. Effectively, to compute a minimum $s-t$ cut, the implementation first computes a minimum $s-t$ flow, after which a BFS is run on the residual graph.

Note: even though the algorithm accepts any kind of graph, currently only Simple directed and undirected graphs are supported (and tested!).

Author:

Alexandru Valeanu, Alexey Kudinkin

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	PushRelabelMFImpl.VertexExtension Vertex extension for the push-relabel algorithm, which contains an additional height.

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MaximumFlowAlgorithm

MaximumFlowAlgorithm.MaximumFlow<E>, MaximumFlowAlgorithm.MaximumFlowImpl<E>

Field Summary

Fields

Modifier and Type	Field and Description
static boolean	USE_GAP_RELABELING_HEURISTIC
static boolean	USE_GLOBAL_RELABELING_HEURISTIC

Fields inherited from class org.jgrapht.alg.flow.MaximumFlowAlgorithmBase

comparator, cutEdges, DEFAULT_EPSILON, directedGraph, edgeExtensionManager, maxFlow, maxFlowValue, network, sink, sinkPartition, source, sourcePartition, vertexExtensionManager

Constructor Summary

Constructors

Constructor and Description
PushRelabelMFImpl(Graph<V,E> network) Construct a new push-relabel algorithm.
PushRelabelMFImpl(Graph<V,E> network, double epsilon) Construct a new push-relabel algorithm.

Method Summary

Modifier and Type	Method and Description
double	calculateMaximumFlow(V source, V sink) Sets current source to source, current sink to sink, then calculates maximum flow from source to sink.
MaximumFlowAlgorithm.MaximumFlow<E>	getMaximumFlow(V source, V sink) Sets current source to source, current sink to sink, then calculates maximum flow from source to sink.
void	initialize(PushRelabelMFImpl.VertexExtension source, PushRelabelMFImpl.VertexExtension sink, Queue<PushRelabelMFImpl.VertexExtension> active) Initialization
protected void	pushFlowThrough(org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.AnnotatedFlowEdge ex, double f) Push flow through an edge.

Methods inherited from class org.jgrapht.alg.flow.MaximumFlowAlgorithmBase

calculateMinCut, calculateSourcePartition, composeFlow, getCurrentSink, getCurrentSource, getCutCapacity, getCutEdges, getFlowDirection, getFlowMap, getMaximumFlowValue, getSinkPartition, getSourcePartition, init

Methods inherited from class java.lang.Object

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

Field Detail

USE_GLOBAL_RELABELING_HEURISTIC

public static boolean USE_GLOBAL_RELABELING_HEURISTIC

USE_GAP_RELABELING_HEURISTIC

public static boolean USE_GAP_RELABELING_HEURISTIC

Constructor Detail

PushRelabelMFImpl

public PushRelabelMFImpl(Graph<V,E> network)

Construct a new push-relabel algorithm.

Parameters:

network - the network

PushRelabelMFImpl

public PushRelabelMFImpl(Graph<V,E> network,
                         double epsilon)

Construct a new push-relabel algorithm.

Parameters:

network - the network

epsilon - tolerance used when comparing floating-point values

Method Detail

initialize

public void initialize(PushRelabelMFImpl.VertexExtension source,
                       PushRelabelMFImpl.VertexExtension sink,
                       Queue<PushRelabelMFImpl.VertexExtension> active)

Initialization

Parameters:

source - the source

sink - the sink

active - resulting queue with all active vertices

getMaximumFlow

public MaximumFlowAlgorithm.MaximumFlow<E> getMaximumFlow(V source,
                                                          V sink)

Description copied from interface: MaximumFlowAlgorithm

Sets current source to source, current sink to sink, then calculates maximum flow from source to sink. Returns an object containing detailed information about the flow.

Parameters:

source - source of the flow inside the network

sink - sink of the flow inside the network

Returns:

maximum flow

calculateMaximumFlow

public double calculateMaximumFlow(V source,
                                   V sink)

Sets current source to source, current sink to sink, then calculates maximum flow from source to sink. Note, that source and sink must be vertices of the network passed to the constructor, and they must be different.

Parameters:

source - source vertex

sink - sink vertex

Returns:

the value of the maximum flow

pushFlowThrough

protected void pushFlowThrough(org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.AnnotatedFlowEdge ex,
                               double f)

Push flow through an edge.

Overrides:

pushFlowThrough in class MaximumFlowAlgorithmBase<V,E>

Parameters:

ex - the edge

f - the amount of flow to push through