EVOLUTION-MANAGER
Edit File: st_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 (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_cuts {igraph}"><tr><td>st_cuts {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table> <h2>List all (s,t)-cuts of a graph</h2> <h3>Description</h3> <p>List all (s,t)-cuts in a directed graph. </p> <h3>Usage</h3> <pre> st_cuts(graph, source, target) </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 source vertex.</p> </td></tr> <tr valign="top"><td><code>target</code></td> <td> <p>The target vertex.</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> <h3>Value</h3> <p>A list with entries: </p> <table summary="R valueblock"> <tr valign="top"><td><code>cuts</code></td> <td> <p>A list of numeric vectors containing edge ids. Each vector is an <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_min_cuts.html">st_min_cuts</a></code> to list all minimum cuts. </p> <h3>Examples</h3> <pre> # A very simple graph g <- graph_from_literal(a -+ b -+ c -+ d -+ e) st_cuts(g, source="a", target="e") # A somewhat more difficult graph g2 <- graph_from_literal(s --+ a:b, a:b --+ t, a --+ 1:2:3, 1:2:3 --+ b) st_cuts(g2, 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>