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.
MinCut(
arcSources,
arcTargets,
arcWeights,
numNodes,
algorithm = "NagamochiIbaraki"
)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.
Vector corresponding to the source nodes of a graph's edges
Vector corresponding to the destination nodes of a graph's edges
Vector corresponding to the weights of a graph's arcs
The number of nodes in the graph
Choices of algorithm include "NagamochiIbaraki" and "HaoOrlin". "NagamochiIbaraki" is the default.
For details on LEMON's implementation, including differences between the algorithms, see https://lemon.cs.elte.hu/pub/doc/1.3.1/a00613.html.