<!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>simple_cycles — 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="Cycles" href="../algorithms.cycles.html" />
<link rel="next" title="Directed Acyclic Graphs" href="../algorithms.dag.html" />
<link rel="prev" title="cycle_basis" href="networkx.algorithms.cycles.cycle_basis.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="../algorithms.dag.html" title="Directed Acyclic Graphs"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="networkx.algorithms.cycles.cycle_basis.html" title="cycle_basis"
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.cycles.html" accesskey="U">Cycles</a> »</li>
</ul>
</div>
<div class="sphinxsidebar">
<div class="sphinxsidebarwrapper">
<h4>Previous topic</h4>
<p class="topless"><a href="networkx.algorithms.cycles.cycle_basis.html"
title="previous chapter">cycle_basis</a></p>
<h4>Next topic</h4>
<p class="topless"><a href="../algorithms.dag.html"
title="next chapter">Directed Acyclic Graphs</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="simple-cycles">
<h1>simple_cycles<a class="headerlink" href="#simple-cycles" title="Permalink to this headline">¶</a></h1>
<dl class="function">
<dt id="networkx.algorithms.cycles.simple_cycles">
<tt class="descname">simple_cycles</tt><big>(</big><em>G</em><big>)</big><a class="reference internal" href="../../_modules/networkx/algorithms/cycles.html#simple_cycles"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#networkx.algorithms.cycles.simple_cycles" title="Permalink to this definition">¶</a></dt>
<dd><p>Find simple cycles (elementary circuits) of a directed graph.</p>
<p>An simple cycle, or elementary circuit, is a closed path where no
node appears twice, except that the first and last node are the same.
Two elementary circuits are distinct if they are not cyclic permutations
of each other.</p>
<p>This is a nonrecursive, iterator/generator version of Johnson’s
algorithm <a class="reference internal" href="#r211">[R211]</a>. There may be better algorithms for some cases <a class="reference internal" href="#r212">[R212]</a> <a class="reference internal" href="#r213">[R213]</a>.</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 DiGraph</p>
<blockquote>
<div><p>A directed graph</p>
</div></blockquote>
</td>
</tr>
<tr class="field-even field"><th class="field-name">Returns :</th><td class="field-body"><p class="first"><strong>cycle_generator: generator</strong> :</p>
<blockquote class="last">
<div><p>A generator that produces elementary cycles of the graph. Each cycle is
a list of nodes with the first and last nodes being the same.</p>
</div></blockquote>
</td>
</tr>
</tbody>
</table>
<div class="admonition-see-also admonition seealso">
<p class="first admonition-title">See also</p>
<p class="last"><a class="reference internal" href="networkx.algorithms.cycles.cycle_basis.html#networkx.algorithms.cycles.cycle_basis" title="networkx.algorithms.cycles.cycle_basis"><tt class="xref py py-obj docutils literal"><span class="pre">cycle_basis</span></tt></a></p>
</div>
<p class="rubric">Notes</p>
<p>The implementation follows pp. 79-80 in <a class="reference internal" href="#r211">[R211]</a>.</p>
<p>The time complexity is O((n+e)(c+1)) for n nodes, e edges and c
elementary circuits.</p>
<p>To filter the cycles so that they don’t include certain nodes or edges,
copy your graph and eliminate those nodes or edges before calling.
>>> copyG = G.copy()
>>> copyG.remove_nodes_from([1])
>>> copyG.remove_edges_from([(0,1)])
>>> list(nx.simple_cycles(copyG))
[[2], [2, 0], [0]]</p>
<p class="rubric">References</p>
<table class="docutils citation" frame="void" id="r211" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label">[R211]</td><td><em>(<a class="fn-backref" href="#id1">1</a>, <a class="fn-backref" href="#id4">2</a>, <a class="fn-backref" href="#id5">3</a>)</em> Finding all the elementary circuits of a directed graph.
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
<a class="reference external" href="http://dx.doi.org/10.1137/0204007">http://dx.doi.org/10.1137/0204007</a></td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="r212" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label">[R212]</td><td><em>(<a class="fn-backref" href="#id2">1</a>, <a class="fn-backref" href="#id6">2</a>)</em> Enumerating the cycles of a digraph: a new preprocessing strategy.
G. Loizou and P. Thanish, Information Sciences, v. 27, 163-182, 1982.</td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="r213" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label">[R213]</td><td><em>(<a class="fn-backref" href="#id3">1</a>, <a class="fn-backref" href="#id7">2</a>)</em> A search strategy for the elementary cycles of a directed graph.
J.L. Szwarcfiter and P.E. Lauer, BIT NUMERICAL MATHEMATICS,
v. 16, no. 2, 192-204, 1976.</td></tr>
</tbody>
</table>
<p class="rubric">Examples</p>
<div class="highlight-python"><div class="highlight"><pre><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="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">),</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">),</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">2</span><span class="p">),</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">),</span> <span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="mi">0</span><span class="p">),</span> <span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="mi">1</span><span class="p">),</span> <span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="mi">2</span><span class="p">)])</span>
<span class="gp">>>> </span><span class="nb">list</span><span class="p">(</span><span class="n">nx</span><span class="o">.</span><span class="n">simple_cycles</span><span class="p">(</span><span class="n">G</span><span class="p">))</span>
<span class="go">[[2], [2, 1], [2, 0], [2, 0, 1], [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="../algorithms.dag.html" title="Directed Acyclic Graphs"
>next</a> |</li>
<li class="right" >
<a href="networkx.algorithms.cycles.cycle_basis.html" title="cycle_basis"
>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.cycles.html" >Cycles</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>
