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:

FlowAlgorithm<V,E>, 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!).

Nested Class Summary

Nested Classes

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

Nested classes/interfaces inherited from class MaximumFlowAlgorithmBase

MaximumFlowAlgorithmBase.AnnotatedFlowEdge, MaximumFlowAlgorithmBase.VertexExtensionBase

Nested classes/interfaces inherited from interface FlowAlgorithm

FlowAlgorithm.Flow<E>, FlowAlgorithm.FlowImpl<E>

Nested classes/interfaces inherited from interface MaximumFlowAlgorithm

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

Field Summary

Fields

Modifier and Type	Field	Description
private Queue<PushRelabelMFImpl<V,E>.VertexExtension>	activeVertices
private static ToleranceDoubleComparator	comparator
private int[]	countHeight
private PushRelabelMFImpl<V,E>.PushRelabelDiagnostic	diagnostic
private static final boolean	DIAGNOSTIC_ENABLED
private final ExtensionFactory<MaximumFlowAlgorithmBase<V,E>.AnnotatedFlowEdge>	edgeExtensionsFactory
private final int	n
private int	relabelCounter
static boolean	USE_GAP_RELABELING_HEURISTIC	Deprecated, for removal: This API element is subject to removal in a future version. use setUseGapRelabelingHeuristic(boolean) instead
static boolean	USE_GLOBAL_RELABELING_HEURISTIC	Deprecated, for removal: This API element is subject to removal in a future version. use setUseGlobalRelabelingHeuristic(boolean) instead
private final PushRelabelMFImpl<V,E>.VertexExtension[]	vertexExtension
private final ExtensionFactory<PushRelabelMFImpl<V,E>.VertexExtension>	vertexExtensionsFactory

Fields inherited from class MaximumFlowAlgorithmBase

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

Constructor Summary

Constructors

Constructor	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	Description
private void	bfs(Queue<Integer> queue, boolean[] visited)
double	calculateMaximumFlow(V source, V sink)	Sets current source to source, current sink to sink, then calculates maximum flow from source to sink.
private void	discharge(PushRelabelMFImpl<V,E>.VertexExtension ux)
private void	enqueue(PushRelabelMFImpl<V,E>.VertexExtension vx)
private void	gapHeuristic(int l)
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.
private PushRelabelMFImpl<V,E>.VertexExtension	getVertexExtension(V v)
(package private) void	init(V source, V sink)	Prepares all data structures to start a new invocation of the Maximum Flow or Minimum Cut algorithms
void	initialize(PushRelabelMFImpl<V,E>.VertexExtension source, PushRelabelMFImpl<V,E>.VertexExtension sink, Queue<PushRelabelMFImpl<V,E>.VertexExtension> active)	Initialization
private boolean	isAdmissible(MaximumFlowAlgorithmBase<V,E>.AnnotatedFlowEdge e)
private void	push(MaximumFlowAlgorithmBase<V,E>.AnnotatedFlowEdge ex)
protected void	pushFlowThrough(MaximumFlowAlgorithmBase<V,E>.AnnotatedFlowEdge ex, double f)	Push flow through an edge.
private void	recomputeHeightsHeuristic()
private void	relabel(PushRelabelMFImpl<V,E>.VertexExtension ux)
static void	setUseGapRelabelingHeuristic(boolean useGapRelabelingHeuristic)
static void	setUseGlobalRelabelingHeuristic(boolean useGlobalRelabelingHeuristic)

Methods inherited from class MaximumFlowAlgorithmBase

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

Methods inherited from class Object

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

Methods inherited from interface FlowAlgorithm

getFlow

Methods inherited from interface MaximumFlowAlgorithm

getMaximumFlowValue

Field Details

DIAGNOSTIC_ENABLED

private static final boolean DIAGNOSTIC_ENABLED

See Also:

• Constant Field Values

USE_GLOBAL_RELABELING_HEURISTIC

@Deprecated(since="1.5.2",
            forRemoval=true)
public static boolean USE_GLOBAL_RELABELING_HEURISTIC

Deprecated, for removal: This API element is subject to removal in a future version.

use setUseGlobalRelabelingHeuristic(boolean) instead

USE_GAP_RELABELING_HEURISTIC

@Deprecated(since="1.5.2",
            forRemoval=true)
public static boolean USE_GAP_RELABELING_HEURISTIC

Deprecated, for removal: This API element is subject to removal in a future version.

use setUseGapRelabelingHeuristic(boolean) instead

vertexExtensionsFactory

private final ExtensionFactory<PushRelabelMFImpl<V,E>.VertexExtension> vertexExtensionsFactory

edgeExtensionsFactory

private final ExtensionFactory<MaximumFlowAlgorithmBase<V,E>.AnnotatedFlowEdge> edgeExtensionsFactory

countHeight

private int[] countHeight

activeVertices

private Queue<PushRelabelMFImpl<V,E>.VertexExtension> activeVertices

diagnostic

private PushRelabelMFImpl<V,E>.PushRelabelDiagnostic diagnostic

n

private final int n

vertexExtension

private final PushRelabelMFImpl<V,E>.VertexExtension[] vertexExtension

relabelCounter

private int relabelCounter

comparator

private static ToleranceDoubleComparator comparator

Constructor Details

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 Details

setUseGlobalRelabelingHeuristic

public static void setUseGlobalRelabelingHeuristic(boolean useGlobalRelabelingHeuristic)

setUseGapRelabelingHeuristic

public static void setUseGapRelabelingHeuristic(boolean useGapRelabelingHeuristic)

enqueue

private void enqueue(PushRelabelMFImpl<V,E>.VertexExtension vx)

init

void init(V source,
 V sink)

Prepares all data structures to start a new invocation of the Maximum Flow or Minimum Cut algorithms

Parameters:

source - source

sink - sink

initialize

public void initialize(PushRelabelMFImpl<V,E>.VertexExtension source,
 PushRelabelMFImpl<V,E>.VertexExtension sink,
 Queue<PushRelabelMFImpl<V,E>.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(MaximumFlowAlgorithmBase<V,E>.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

push

private void push(MaximumFlowAlgorithmBase<V,E>.AnnotatedFlowEdge ex)

gapHeuristic

private void gapHeuristic(int l)

relabel

private void relabel(PushRelabelMFImpl<V,E>.VertexExtension ux)

bfs

private void bfs(Queue<Integer> queue,
 boolean[] visited)

recomputeHeightsHeuristic

private void recomputeHeightsHeuristic()

discharge

private void discharge(PushRelabelMFImpl<V,E>.VertexExtension ux)

isAdmissible

private boolean isAdmissible(MaximumFlowAlgorithmBase<V,E>.AnnotatedFlowEdge e)

getVertexExtension

private PushRelabelMFImpl<V,E>.VertexExtension getVertexExtension(V v)