getMinimumCutTree
computes a minimum cut tree, also
called Gomory-Hu tree. This function uses the Gusfield's
algorithm to find it.
getMinimumCutTree(nodes, arcs, algorithm = "Gusfield", show.data = TRUE, show.graph = TRUE, check.graph = FALSE)
FALSE
by default.TRUE
) or not
(FALSE
). The default is TRUE
.TRUE
) or not
(FALSE
). The default is TRUE
.getMinimumCutTree
returns a list with:In 1990, Dan Gusfield proposed a new algorithm that can be used to find the Gomory-Hu tree without any nodes contraction and simplifies the implementation.
Dan Gusfield (1990). "Very Simple Methods for All Pairs Network Flow Analysis". SIAM J. Comput. 19 (1): 143-155.
# Graph
nodes <- 1:6
arcs <- matrix(c(1,2,1, 1,3,7, 2,3,1, 2,4,3, 2,5,2, 3,5,4, 4,5,1, 4,6,6,
5,6,2), byrow = TRUE, ncol = 3)
# Minimum cut tree
getMinimumCutTree(nodes, arcs)
Run the code above in your browser using DataLab