<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>min_cut — NetworkX 1.8.1 documentation</title>
<link rel="stylesheet" href="../../_static/networkx.css" type="text/css" />
<link rel="stylesheet" href="../../_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: '../../',
VERSION: '1.8.1',
COLLAPSE_INDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: false
};
</script>
<script type="text/javascript" src="../../_static/jquery.js"></script>
<script type="text/javascript" src="../../_static/underscore.js"></script>
<script type="text/javascript" src="../../_static/doctools.js"></script>
<link rel="search" type="application/opensearchdescription+xml"
title="Search within NetworkX 1.8.1 documentation"
href="../../_static/opensearch.xml"/>
<link rel="top" title="NetworkX 1.8.1 documentation" href="../../index.html" />
<link rel="up" title="Flows" href="../algorithms.flow.html" />
<link rel="next" title="ford_fulkerson" href="networkx.algorithms.flow.ford_fulkerson.html" />
<link rel="prev" title="max_flow" href="networkx.algorithms.flow.max_flow.html" />
</head>
<body>
<div style="color: black;background-color: white; font-size: 3.2em; text-align: left; padding: 15px 10px 10px 15px">
NetworkX
</div>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../../genindex.html" title="General Index"
accesskey="I">index</a></li>
<li class="right" >
<a href="../../py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li class="right" >
<a href="networkx.algorithms.flow.ford_fulkerson.html" title="ford_fulkerson"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="networkx.algorithms.flow.max_flow.html" title="max_flow"
accesskey="P">previous</a> |</li>
<li><a href="http://networkx.github.com/">NetworkX Home </a> | </li>
<li><a href="http://networkx.github.com/documentation.html">Documentation </a>| </li>
<li><a href="http://networkx.github.com/download.html">Download </a> | </li>
<li><a href="http://github.com/networkx">Developer (Github)</a></li>
<li><a href="../index.html" >Reference</a> »</li>
<li><a href="../pdf_reference.html" >Reference</a> »</li>
<li><a href="../algorithms.html" >Algorithms</a> »</li>
<li><a href="../algorithms.flow.html" accesskey="U">Flows</a> »</li>
</ul>
</div>
<div class="sphinxsidebar">
<div class="sphinxsidebarwrapper">
<h4>Previous topic</h4>
<p class="topless"><a href="networkx.algorithms.flow.max_flow.html"
title="previous chapter">max_flow</a></p>
<h4>Next topic</h4>
<p class="topless"><a href="networkx.algorithms.flow.ford_fulkerson.html"
title="next chapter">ford_fulkerson</a></p>
<div id="searchbox" style="display: none">
<h3>Quick search</h3>
<form class="search" action="../../search.html" method="get">
<input type="text" name="q" />
<input type="submit" value="Go" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
<p class="searchtip" style="font-size: 90%">
Enter search terms or a module, class or function name.
</p>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
</div>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body">
<div class="section" id="min-cut">
<h1>min_cut<a class="headerlink" href="#min-cut" title="Permalink to this headline">¶</a></h1>
<dl class="function">
<dt id="networkx.algorithms.flow.min_cut">
<tt class="descname">min_cut</tt><big>(</big><em>G</em>, <em>s</em>, <em>t</em>, <em>capacity='capacity'</em><big>)</big><a class="headerlink" href="#networkx.algorithms.flow.min_cut" title="Permalink to this definition">¶</a></dt>
<dd><p>Compute the value of a minimum (s, t)-cut.</p>
<p>Use the max-flow min-cut theorem, i.e., the capacity of a minimum
capacity cut is equal to the flow value of a maximum flow.</p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field-odd field"><th class="field-name">Parameters :</th><td class="field-body"><p class="first"><strong>G</strong> : NetworkX graph</p>
<blockquote>
<div><p>Edges of the graph are expected to have an attribute called
‘capacity’. If this attribute is not present, the edge is
considered to have infinite capacity.</p>
</div></blockquote>
<p><strong>s</strong> : node</p>
<blockquote>
<div><p>Source node for the flow.</p>
</div></blockquote>
<p><strong>t</strong> : node</p>
<blockquote>
<div><p>Sink node for the flow.</p>
</div></blockquote>
<p><strong>capacity: string</strong> :</p>
<blockquote>
<div><p>Edges of the graph G are expected to have an attribute capacity
that indicates how much flow the edge can support. If this
attribute is not present, the edge is considered to have
infinite capacity. Default value: ‘capacity’.</p>
</div></blockquote>
</td>
</tr>
<tr class="field-even field"><th class="field-name">Returns :</th><td class="field-body"><p class="first"><strong>cutValue</strong> : integer, float</p>
<blockquote>
<div><p>Value of the minimum cut.</p>
</div></blockquote>
</td>
</tr>
<tr class="field-odd field"><th class="field-name">Raises :</th><td class="field-body"><p class="first"><strong>NetworkXUnbounded</strong> :</p>
<blockquote class="last">
<div><p>If the graph has a path of infinite capacity, all cuts have
infinite capacity and the function raises a NetworkXError.</p>
</div></blockquote>
</td>
</tr>
</tbody>
</table>
<p class="rubric">Examples</p>
<div class="highlight-python"><div class="highlight"><pre><span class="gp">>>> </span><span class="kn">import</span> <span class="nn">networkx</span> <span class="kn">as</span> <span class="nn">nx</span>
<span class="gp">>>> </span><span class="n">G</span> <span class="o">=</span> <span class="n">nx</span><span class="o">.</span><span class="n">DiGraph</span><span class="p">()</span>
<span class="gp">>>> </span><span class="n">G</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="s">'x'</span><span class="p">,</span><span class="s">'a'</span><span class="p">,</span> <span class="n">capacity</span> <span class="o">=</span> <span class="mf">3.0</span><span class="p">)</span>
<span class="gp">>>> </span><span class="n">G</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="s">'x'</span><span class="p">,</span><span class="s">'b'</span><span class="p">,</span> <span class="n">capacity</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">)</span>
<span class="gp">>>> </span><span class="n">G</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="s">'a'</span><span class="p">,</span><span class="s">'c'</span><span class="p">,</span> <span class="n">capacity</span> <span class="o">=</span> <span class="mf">3.0</span><span class="p">)</span>
<span class="gp">>>> </span><span class="n">G</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="s">'b'</span><span class="p">,</span><span class="s">'c'</span><span class="p">,</span> <span class="n">capacity</span> <span class="o">=</span> <span class="mf">5.0</span><span class="p">)</span>
<span class="gp">>>> </span><span class="n">G</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="s">'b'</span><span class="p">,</span><span class="s">'d'</span><span class="p">,</span> <span class="n">capacity</span> <span class="o">=</span> <span class="mf">4.0</span><span class="p">)</span>
<span class="gp">>>> </span><span class="n">G</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="s">'d'</span><span class="p">,</span><span class="s">'e'</span><span class="p">,</span> <span class="n">capacity</span> <span class="o">=</span> <span class="mf">2.0</span><span class="p">)</span>
<span class="gp">>>> </span><span class="n">G</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="s">'c'</span><span class="p">,</span><span class="s">'y'</span><span class="p">,</span> <span class="n">capacity</span> <span class="o">=</span> <span class="mf">2.0</span><span class="p">)</span>
<span class="gp">>>> </span><span class="n">G</span><span class="o">.</span><span class="n">add_edge</span><span class="p">(</span><span class="s">'e'</span><span class="p">,</span><span class="s">'y'</span><span class="p">,</span> <span class="n">capacity</span> <span class="o">=</span> <span class="mf">3.0</span><span class="p">)</span>
<span class="gp">>>> </span><span class="n">nx</span><span class="o">.</span><span class="n">min_cut</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="s">'x'</span><span class="p">,</span> <span class="s">'y'</span><span class="p">)</span>
<span class="go">3.0</span>
</pre></div>
</div>
</dd></dl>
</div>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../../genindex.html" title="General Index"
>index</a></li>
<li class="right" >
<a href="../../py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li class="right" >
<a href="networkx.algorithms.flow.ford_fulkerson.html" title="ford_fulkerson"
>next</a> |</li>
<li class="right" >
<a href="networkx.algorithms.flow.max_flow.html" title="max_flow"
>previous</a> |</li>
<li><a href="http://networkx.github.com/">NetworkX Home </a> | </li>
<li><a href="http://networkx.github.com/documentation.html">Documentation </a>| </li>
<li><a href="http://networkx.github.com/download.html">Download </a> | </li>
<li><a href="http://github.com/networkx">Developer (Github)</a></li>
<li><a href="../index.html" >Reference</a> »</li>
<li><a href="../pdf_reference.html" >Reference</a> »</li>
<li><a href="../algorithms.html" >Algorithms</a> »</li>
<li><a href="../algorithms.flow.html" >Flows</a> »</li>
</ul>
</div>
<div class="footer">
© Copyright 2013, NetworkX Developers.
Last updated on Oct 23, 2013.
Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.1.3.
</div>
</body>
</html>
