MinCut {rlemon}

Solver for MinCut

Description

Finds the minimum cut on graphs. NagamochiIbaraki calculates the min cut value and edges in undirected graphs,while HaoOrlin calculates the min cut value and edges in directed graphs.

Usage

MinCut(
  arcSources,
  arcTargets,
  arcWeights,
  numNodes,
  algorithm = "NagamochiIbaraki"
)

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 "NagamochiIbaraki" and "HaoOrlin". "NagamochiIbaraki" 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/a00613.html.

Value

A named list containing three entries: 1) "mincut": the value of the minimum cut in the graph, 2) "first_partition": a vector of nodes in the first partition, and 3) "second_partition": a vector of nodes in the second partition. GomoryHu calculates a Gomory-Hu Tree and returns a list containing three entries: 1) A vector of predecessor nodes of each node in the graph, and 2) A vector of weights of the predecessor edge of each node, and 3) A vector of distances from the root node to each node.