Package org.graph4j.flow

Class PushRelabelMaximumFlow

java.lang.Object

org.graph4j.flow.MaximumFlowBase

org.graph4j.flow.PushRelabelMaximumFlow

All Implemented Interfaces:

MaximumFlowAlgorithm

public class PushRelabelMaximumFlow
extends MaximumFlowBase

The Push-Relabel algorithm maintains a preflow (where flow into a node can exceed flow out of it) and repeatedly pushes excess flow from overflowing vertices to neighboring vertices or relabels the height of the overflowing vertices to find new paths. The algorithm has a time complexity of O(n²m), where n is the number of vertices and m the number of edges in the graph.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.flow.MaximumFlowBase

computed, cutEdges, ekAlg, graph, initialFlow, numVertices, sink, sinkIndex, sinkPart, source, sourceIndex, sourcePart

Constructor Summary

Constructors

Constructor	Description
PushRelabelMaximumFlow(Network graph)
PushRelabelMaximumFlow(Network graph, FlowData flow)

Method Summary

Modifier and Type	Method	Description
void	computeMaximumFlow()

Methods inherited from class org.graph4j.flow.MaximumFlowBase

getFlowValue, getMaximumFlowData, getMaximumFlowValue, getMinimumCutEdges, getSinkPart, getSourcePart, initFlow

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.graph4j.flow.MaximumFlowAlgorithm

getFlowValue

Constructor Details

PushRelabelMaximumFlow

public PushRelabelMaximumFlow(Network graph)

PushRelabelMaximumFlow

public PushRelabelMaximumFlow(Network graph,
 FlowData flow)

Method Details

computeMaximumFlow

public void computeMaximumFlow()

Specified by:

computeMaximumFlow in class MaximumFlowBase