AllPairsMinCut {rlemon}

Solver for All-Pairs MinCut

Description

Finds the all-pairs minimum cut tree, using the Gomory-Hu algorithm.

Usage

AllPairsMinCut(
  arcSources,
  arcTargets,
  arcWeights,
  numNodes,
  algorithm = "GomoryHu"
)

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

arcWeights

Vector corresponding to the weights of a graph's arcs

numNodes

The number of nodes in the graph

algorithm

Choices of algorithm include "GomoryHu". "GomoryHu" 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/a00182.html.

Value

A namedlist containing three entries: 1) "predecessors": a vector of predecessor nodes of each node in the graph, and 2) "weights": a vector of weights of the predecessor edge of each node, and 3) "distances": vector of distances from the root node to each node.