R/findMinCut.R In optrees: Optimal Trees in Weighted Graphs

Documented in findMinCut

```#-----------------------------------------------------------------------------#
# optrees Package                                                             #
# Minimum Cut Tree Problems                                                   #
#-----------------------------------------------------------------------------#

# findMinCut ------------------------------------------------------------------
#' Finds the minimum cut of a given graph
#'
#' The \code{findMinCut} function can find the minimum cut of a given graph.
#' For that, this function computes the maximum flow of the network and applies
#' the max-flow min-cut theorem to determine the cut with minimum weight
#' between the source and the sink nodes.
#'
#' @details The max-flow min-cut theorem proves that, in a flow network, the
#' maximum flow between the source node and the sink node and the weight of any
#' minimum cut between them is equal.
#'
#' @param nodes vector containing the nodes of the graph, identified by a
#' number that goes from \eqn{1} to the order of the graph.
#' @param arcs matrix with the list of arcs of the graph. Each row represents
#' one arc. The first two columns contain the two endpoints of each arc and the
#' third column contains their weights.
#' @param algorithm denotes the algorithm used to compute the maximum flow:
#' "Ford-Fulkerson".
#' @param source.node number pointing to the source node of the graph. It's node
#' \eqn{1} by default.
#' @param sink.node number pointing to the sink node of the graph. It's the
#' last node by default.
#' @param directed logical value indicating whether the graph is directed
#' (\code{TRUE}) or not (\code{FALSE}).
#'
#' @return \code{findMinCut} returns a list with:
#' s.cut vector with the nodes of the \code{s} cut.
#' t.cut vector with the nodes of the \code{t} cut.
#' maxFlow value with the maximum flow in the flow network.
#' cut.set list of arcs of the cut set founded.
#'
#' @seealso This function is an auxiliar function used in
#'
#' @examples
#' # 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)
#' # Find minimum cut
#' findMinCut(nodes, arcs, source.node = 2, sink.node = 6)
#'
#' @export

findMinCut <- function(nodes, arcs, algorithm = "Ford-Fulkerson",
source.node = 1, sink.node = nodes[length(nodes)],
directed = FALSE) {

# In case of a undirected graph duplicate and order arcs
if (!directed) {
arcs <- rbind(arcs, matrix(c(arcs[, 2], arcs[, 1], arcs[, 3]), ncol = 3))
arcs <- arcs[order(arcs[, 1], arcs[, 2]), ]
}

# Add a column with flow equal to the capacity of each arc
arcs <- cbind(arcs, arcs[, 3])
colnames(arcs) <- NULL

# Get minimum cut with selected algorithm
if (algorithm == "Ford-Fulkerson") {
min.cut <- maxFlowFordFulkerson(nodes, arcs, TRUE, source.node, sink.node)
} else {
stop("Unknown algorithm")
}

# Get cut set
cut.arcs <- which(arcs[, 1] %in% min.cut\$s.cut & arcs[, 2] %in% min.cut\$t.cut)
cut.set <- matrix(arcs[cut.arcs, -4], ncol = 3)
colnames(cut.set) <- c("ept1", "ept2", "weight")
min.cut <- append(min.cut, list("cut.set" = cut.set))

# Return minimum cut
return(min.cut)

}
#-----------------------------------------------------------------------------#
```

Try the optrees package in your browser

Any scripts or data that you put into this service are public.

optrees documentation built on May 29, 2017, 9:40 p.m.