Package networkx :: Module cliques

[frames | no frames]

## Module networkx.cliques

Cliques - Find and manipulate cliques of graphs

Note that finding the largest clique of a graph has been shown to be an NP complete problem so the algorithms here could take a LONG time to run. In practice it hasn't been too bad for the graphs tested.

Function Summary
| ``cliques_containing_node`(G, nodes, cliques, with_labels)` Returns a list of cliques containing the given node.
| ``find_cliques`(G)` Find_cliques algorithm based on Bron & Kerbosch
| ``graph_clique_number`(G, cliques)` Return the clique number (size the largest clique) for G.
| ``graph_number_of_cliques`(G, cliques)` Returns the number of maximal cliques in G Optional list of cliques can be input if already computed.
| ``make_clique_bipartite`(G, fpos, create_using, **kwds)` Create a bipartite clique graph from a graph G.
| ``make_max_clique_graph`(G, create_using, **kwds)` Create the maximal clique graph of a graph.
| ``node_clique_number`(G, nodes, with_labels, cliques)` Returns the size of the largest maximal clique containing each given node.
| ``number_of_cliques`(G, nodes, cliques, with_labels)` Returns the number of maximal cliques for each node.
| ``project_down`(B, create_using, **kwds)` Project a bipartite graph B down onto its "Bottom Nodes".
| ``project_up`(B, create_using, **kwds)` Project a bipartite graph B up onto its "Top Nodes".

Variable Summary
`str` | `__author__` = `'Dan Schult (dschult@colgate.edu)'`
`str` | `__credits__` = `''`
`str` | `__date__` = `'$Date: 2005-06-15 07:56:03 -0600 (Wed, 15 Ju...`
`str` | `__revision__` = `'$Revision: 1021 $'`

Function Details

### cliques_containing_node(G, nodes=None, cliques=None, with_labels=False)

Returns a list of cliques containing the given node.

Returns a single list or list of lists depending on input nodes. Returns a dict keyed by node if "with_labels=True". Optional list of cliques can be input if already computed.

### find_cliques(G)

Find_cliques algorithm based on Bron & Kerbosch

This algorithm searchs for maximal cliques in a graph. maximal cliques are the largest complete subgraph containing a given point. The largest maximal clique is sometimes called the maximum clique.

This algorithm produces the list of maximal cliques each of which are a list of the members of the clique.

Based on Algol algorithm published by Bron & Kerbosch A C version is available as part of the rambin package. http://www.ram.org/computing/rambin/rambin.html

Reference:

    @article{362367,
     author = {Coen Bron and Joep Kerbosch},
     title = {Algorithm 457: finding all cliques of an undirected graph},
     journal = {Commun. ACM},
     volume = {16},
     number = {9},
     year = {1973},
     issn = {0001-0782},
     pages = {575--577},
     doi = {http://doi.acm.org/10.1145/362342.362367},
     publisher = {ACM Press},
     }

### graph_clique_number(G, cliques=None)

Return the clique number (size the largest clique) for G. Optional list of cliques can be input if already computed.

### graph_number_of_cliques(G, cliques=None)

Returns the number of maximal cliques in G Optional list of cliques can be input if already computed.

### make_clique_bipartite(G, fpos=None, create_using=None, **kwds)

Create a bipartite clique graph from a graph G. Nodes of G are retained as the "bottom nodes" of B and cliques of G become "top nodes" of B. Edges are present if a bottom node belongs to the clique represented by the top node.

Returns a Graph with additional attribute B.node_type which is "Bottom" or "Top" appropriately.

if fpos is not None, a second additional attribute B.pos is created to hold the position tuple of each node for viewing the bipartite graph.

### make_max_clique_graph(G, create_using=None, **kwds)

Create the maximal clique graph of a graph. It finds the maximal cliques and treats these as nodes. The nodes are connected if they have common members in the original graph. Theory has done a lot with clique graphs, but I haven't seen much on maximal clique graphs.

Note: This should be the same as make_clique_bipartite followed by project_up, but it saves all the intermediate stuff.

### node_clique_number(G, nodes=None, with_labels=False, cliques=None)

Returns the size of the largest maximal clique containing each given node.

Returns a single or list depending on input nodes. Returns a dict keyed by node if "with_labels=True". Optional list of cliques can be input if already computed.

### number_of_cliques(G, nodes=None, cliques=None, with_labels=False)

Returns the number of maximal cliques for each node.

Returns a single or list depending on input nodes. Returns a dict keyed by node if "with_labels=True". Optional list of cliques can be input if already computed.

### project_down(B, create_using=None, **kwds)

Project a bipartite graph B down onto its "Bottom Nodes". The nodes retain their names and are connected if they share a common Top Node in the Bipartite Graph. Returns a Graph.

### project_up(B, create_using=None, **kwds)

Project a bipartite graph B up onto its "Top Nodes". The nodes retain their names and are connected if they share a common Bottom Node in the Bipartite Graph. Returns a Graph.

Variable Details

### __author__

  Type:
    `str`
  Value:

        'Dan Schult (dschult@colgate.edu)'

### __credits__

  Type:
    `str`
  Value:

        ''

### __date__

  Type:
    `str`
  Value:

        '$Date: 2005-06-15 07:56:03 -0600 (Wed, 15 Jun 2005) $'

### __revision__

  Type:
    `str`
  Value:

        '$Revision: 1021 $'

Generated by Epydoc 2.1 on Sun Aug 21 08:06:58 2005 | http://epydoc.sf.net