EVOLUTION-MANAGER
Edit File: st_min_cuts.html
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><title>R: List all minimum (s,t)-cuts of a graph</title> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <link rel="stylesheet" type="text/css" href="R.css" /> </head><body> <table width="100%" summary="page for st_min_cuts {igraph}"><tr><td>st_min_cuts {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table> <h2>List all minimum <i>(s,t)</i>-cuts of a graph</h2> <h3>Description</h3> <p>Listing all minimum <i>(s,t)</i>-cuts of a directed graph, for given <i>s</i> and <i>t</i>. </p> <h3>Usage</h3> <pre> st_min_cuts(graph, source, target, capacity = NULL) </pre> <h3>Arguments</h3> <table summary="R argblock"> <tr valign="top"><td><code>graph</code></td> <td> <p>The input graph. It must be directed.</p> </td></tr> <tr valign="top"><td><code>source</code></td> <td> <p>The id of the source vertex.</p> </td></tr> <tr valign="top"><td><code>target</code></td> <td> <p>The id of the target vertex.</p> </td></tr> <tr valign="top"><td><code>capacity</code></td> <td> <p>Numeric vector giving the edge capacities. If this is <code>NULL</code> and the graph has a <code>weight</code> edge attribute, then this attribute defines the edge capacities. For forcing unit edge capacities, even for graphs that have a <code>weight</code> edge attribute, supply <code>NA</code> here.</p> </td></tr> </table> <h3>Details</h3> <p>Given a <i>G</i> directed graph and two, different and non-ajacent vertices, <i>s</i> and <i>t</i>, an <i>(s,t)</i>-cut is a set of edges, such that after removing these edges from <i>G</i> there is no directed path from <i>s</i> to <i>t</i>. </p> <p>The size of an <i>(s,t)</i>-cut is defined as the sum of the capacities (or weights) in the cut. For unweighted (=equally weighted) graphs, this is simply the number of edges. </p> <p>An <i>(s,t)</i>-cut is minimum if it is of the smallest possible size. </p> <h3>Value</h3> <p>A list with entries: </p> <table summary="R valueblock"> <tr valign="top"><td><code>value</code></td> <td> <p>Numeric scalar, the size of the minimum cut(s).</p> </td></tr> <tr valign="top"><td><code>cuts</code></td> <td> <p>A list of numeric vectors containing edge ids. Each vector is a minimum <i>(s,t)</i>-cut.</p> </td></tr> <tr valign="top"><td><code>partition1s</code></td> <td> <p>A list of numeric vectors containing vertex ids, they correspond to the edge cuts. Each vertex set is a generator of the corresponding cut, i.e. in the graph <i>G=(V,E)</i>, the vertex set <i>X</i> and its complementer <i>V-X</i>, generates the cut that contains exactly the edges that go from <i>X</i> to <i>V-X</i>.</p> </td></tr> </table> <h3>Author(s)</h3> <p>Gabor Csardi <a href="mailto:csardi.gabor@gmail.com">csardi.gabor@gmail.com</a> </p> <h3>References</h3> <p>JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in graphs, <em>Algorithmica</em> 15, 351–372, 1996. </p> <h3>See Also</h3> <p><code><a href="st_cuts.html">st_cuts</a></code>, <code><a href="min_separators.html">min_separators</a></code> </p> <h3>Examples</h3> <pre> # A difficult graph, from the Provan-Shier paper g <- graph_from_literal(s --+ a:b, a:b --+ t, a --+ 1:2:3:4:5, 1:2:3:4:5 --+ b) st_min_cuts(g, source="s", target="t") </pre> <hr /><div style="text-align: center;">[Package <em>igraph</em> version 1.3.5 <a href="00Index.html">Index</a>]</div> </body></html>