Description Usage Arguments Details Value See Also Examples
The 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.
1 2 | findMinCut(nodes, arcs, algorithm = "Ford-Fulkerson", source.node = 1,
sink.node = nodes[length(nodes)], directed = FALSE)
|
nodes |
vector containing the nodes of the graph, identified by a number that goes from 1 to the order of the graph. |
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. |
algorithm |
denotes the algorithm used to compute the maximum flow: "Ford-Fulkerson". |
source.node |
number pointing to the source node of the graph. It's node 1 by default. |
sink.node |
number pointing to the sink node of the graph. It's the last node by default. |
directed |
logical value indicating whether the
graph is directed ( |
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.
findMinCut
returns a list with:
s.cut |
vector with the nodes of the |
t.cut |
vector with the nodes of the |
max.flow |
value with the maximum flow in the flow network. |
cut.set |
list of arcs of the cut set founded. |
This function is an auxiliar function used in ghTreeGusfield and getMinimumCutTree.
1 2 3 4 5 6 | # 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)
|
Loading required package: igraph
Attaching package: 'igraph'
The following objects are masked from 'package:stats':
decompose, spectrum
The following object is masked from 'package:base':
union
$s.cut
[1] 2 3 1 5
$t.cut
[1] 4 6
$max.flow
[1] 6
$cut.set
ept1 ept2 weight
[1,] 2 4 3
[2,] 5 4 1
[3,] 5 6 2
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.