com.raphtory.algorithms.generic.MaxFlow

MaxFlow

MaxFlow[T](source: String, target: String, capacityLabel: String = "weight", maxIterations: Int = Int.MaxValue)

Finds the maximum flow (equivalently, the minimum cut) between a source and a target vertex

Implements the parallel push-relabel max-flow algorithm of Goldberg and Tarjan. 1

Parameters

T: Numeric

Type of edge weight attribute (needs to be specified as not possible to infer automatically)

source: String

name of source vertex

target: String

name of target vertex

capacityLabel: String = "weight"

Edge attribute key to use for computing capacities. Capacities are computed as the sum of weights over occurrences of the edge. If the edge property does not exist, weight is computed as the edge count.

maxIterations: Int = Int.MaxValue

terminate the algorithm if it has not converged after maxIterations pulses (note that the flow will be incorrect if this happens)

States

flow: mutable.Map[Long, T]

Map of targetID -> flow for outflow at vertex (negative values are backflow used by the algorithm)

excess: T

excess flow at vertex (should be 0 except for source and target after algorithm converged)

distanceLabel: Int

vertex label used by the algorithm to decide where to push flow

neighbourLabels: mutable.Map[Long, Int]

Map of targetID -> label containing the distance labels for the vertexes neighbours

Returns

Maximum Flow

flow: T

Note

The algorithm returns a single line with the value of the maximum flow between the source and target.


1

A new approach to the Maximum-Flow Problem