Skip to contents

Solver for All-Pairs MinCut

Source: R/mincut.R
AllPairsMinCut.Rd

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.

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.

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.