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 pushrelabel maxflow 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 


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