Finds the maximum flow of a directed graph, given a source and destination node.
Usage
MaxFlow(
arcSources,
arcTargets,
arcCapacities,
sourceNode,
destNode,
numNodes,
algorithm = "Preflow"
)Arguments
- arcSources
Vector corresponding to the source nodes of a graph's edges
- arcTargets
Vector corresponding to the destination nodes of a graph's edges
- arcCapacities
Vector corresponding to the capacities of nodes of a graph's edges
- sourceNode
The source node
- destNode
The destination node
- numNodes
The number of nodes in the graph
- algorithm
Choices of algorithm include "Preflow" and "EdmondsKarp". "Preflow" is the default.
Value
A named list containing three entries: 1) "flows": a vector corresponding to the flows of arcs in the graph, 2) "cut_values": a vector of cut-values of the graph's nodes, and 3) "cost": the total cost of the flows in the graph, i.e. the maxflow value.
Details
For details on LEMON's implementation, including differences between the algorithms, see https://lemon.cs.elte.hu/pub/doc/1.3.1/a00611.html.