MaxFlow {rlemon}

Solver for MaxFlow

Description

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.

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.

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.