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.
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.
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.
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.