getMinimumArborescence
computes a minimum cost
arborescence. This function provides a method to find the
minimum cost arborescence with Edmonds' algorithm.
getMinimumArborescence(nodes, arcs, source.node = 1, algorithm = "Edmonds", stages.data = FALSE, 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
.FALSE
.getMinimumArborescence
returns a list with:Edmonds' algorithm was developed by the mathematician and computer scientist Jack R. Edmonds in 1967. Although, it was previously proposed in 1965 by Yoeng-jin Chu and Tseng-hong Liu. This algorithm decreases the weights of the arcs in a graph and compacts cycles of zero weight until it can find an arborescence. This arborescence has to be a minimum cost arborescence of the graph.
Edmonds, J., "Optimum Branchings", Journal of Research of the National Bureau of Standards, vol. 71B, No. 4, October-December 1967, pp. 233-240.
# Graph
nodes <- 1:4
arcs <- matrix(c(1,2,2, 1,3,3, 1,4,4, 2,3,3, 2,4,4, 3,2,3,
3,4,1, 4,2,1, 4,3,2),byrow = TRUE, ncol = 3)
# Minimum cost arborescence
getMinimumArborescence(nodes, arcs)
Run the code above in your browser using DataLab