<!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>find_cliques — 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="Clique" href="../algorithms.clique.html" />
<link rel="next" title="make_max_clique_graph" href="networkx.algorithms.clique.make_max_clique_graph.html" />
<link rel="prev" title="cliques_containing_node" href="networkx.algorithms.clique.cliques_containing_node.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.clique.make_max_clique_graph.html" title="make_max_clique_graph"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="networkx.algorithms.clique.cliques_containing_node.html" title="cliques_containing_node"
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.clique.html" accesskey="U">Clique</a> »</li>
</ul>
</div>
<div class="sphinxsidebar">
<div class="sphinxsidebarwrapper">
<h4>Previous topic</h4>
<p class="topless"><a href="networkx.algorithms.clique.cliques_containing_node.html"
title="previous chapter">cliques_containing_node</a></p>
<h4>Next topic</h4>
<p class="topless"><a href="networkx.algorithms.clique.make_max_clique_graph.html"
title="next chapter">make_max_clique_graph</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="find-cliques">
<h1>find_cliques<a class="headerlink" href="#find-cliques" title="Permalink to this headline">¶</a></h1>
<dl class="function">
<dt id="networkx.algorithms.clique.find_cliques">
<tt class="descname">find_cliques</tt><big>(</big><em>G</em><big>)</big><a class="reference internal" href="../../_modules/networkx/algorithms/clique.html#find_cliques"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#networkx.algorithms.clique.find_cliques" title="Permalink to this definition">¶</a></dt>
<dd><p>Search for all maximal cliques in a graph.</p>
<p>Maximal cliques are the largest complete subgraph containing
a given node. The largest maximal clique is sometimes called
the maximum clique.</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">Returns :</th><td class="field-body"><strong>generator of lists: genetor of member list for each maximal clique</strong> :</td>
</tr>
</tbody>
</table>
<div class="admonition-see-also admonition seealso">
<p class="first admonition-title">See also</p>
<p class="last"><tt class="xref py py-obj docutils literal"><span class="pre">find_cliques_recursive</span></tt>, <tt class="xref py py-obj docutils literal"><span class="pre">A</span></tt></p>
</div>
<p class="rubric">Notes</p>
<p>To obtain a list of cliques, use list(find_cliques(G)).</p>
<p>Based on the algorithm published by Bron & Kerbosch (1973) <a class="reference internal" href="#r180">[R180]</a>
as adapated by Tomita, Tanaka and Takahashi (2006) <a class="reference internal" href="#r181">[R181]</a>
and discussed in Cazals and Karande (2008) <a class="reference internal" href="#r182">[R182]</a>.
The method essentially unrolls the recursion used in
the references to avoid issues of recursion stack depth.</p>
<p>This algorithm is not suitable for directed graphs.</p>
<p>This algorithm ignores self-loops and parallel edges as
clique is not conventionally defined with such edges.</p>
<p>There are often many cliques in graphs. This algorithm can
run out of memory for large graphs.</p>
<p class="rubric">References</p>
<table class="docutils citation" frame="void" id="r180" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label">[R180]</td><td><em>(<a class="fn-backref" href="#id1">1</a>, <a class="fn-backref" href="#id4">2</a>)</em> Bron, C. and Kerbosch, J. 1973.
Algorithm 457: finding all cliques of an undirected graph.
Commun. ACM 16, 9 (Sep. 1973), 575-577.
<a class="reference external" href="http://portal.acm.org/citation.cfm?doid=362342.362367">http://portal.acm.org/citation.cfm?doid=362342.362367</a></td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="r181" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label">[R181]</td><td><em>(<a class="fn-backref" href="#id2">1</a>, <a class="fn-backref" href="#id5">2</a>)</em> Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi,
The worst-case time complexity for generating all maximal
cliques and computational experiments,
Theoretical Computer Science, Volume 363, Issue 1,
Computing and Combinatorics,
10th Annual International Conference on
Computing and Combinatorics (COCOON 2004), 25 October 2006, Pages 28-42
<a class="reference external" href="http://dx.doi.org/10.1016/j.tcs.2006.06.015">http://dx.doi.org/10.1016/j.tcs.2006.06.015</a></td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="r182" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label">[R182]</td><td><em>(<a class="fn-backref" href="#id3">1</a>, <a class="fn-backref" href="#id6">2</a>)</em> F. Cazals, C. Karande,
A note on the problem of reporting maximal cliques,
Theoretical Computer Science,
Volume 407, Issues 1-3, 6 November 2008, Pages 564-568,
<a class="reference external" href="http://dx.doi.org/10.1016/j.tcs.2008.05.010">http://dx.doi.org/10.1016/j.tcs.2008.05.010</a></td></tr>
</tbody>
</table>
</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.clique.make_max_clique_graph.html" title="make_max_clique_graph"
>next</a> |</li>
<li class="right" >
<a href="networkx.algorithms.clique.cliques_containing_node.html" title="cliques_containing_node"
>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.clique.html" >Clique</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>
