Package networkx :: Module cliques

Module 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.

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

Author: Dan Schult (dschult@colgate.edu)

Functions

[hide private]

find_cliques(G)
Find_cliques algorithm based on Bron & Kerbosch

source code

_extend(old_nodes, num_not, num_left, G, clique, cliques)
A recursive helper routine for find_cliques

source code

make_max_clique_graph(G, create_using=None, name=None)
Create the maximal clique graph of a graph.

source code

make_clique_bipartite(G, fpos=None, create_using=None, name=None)
Create a bipartite clique graph from a graph G.

source code

project_down(B, create_using=None, name=None)
Project a bipartite graph B down onto its "Bottom Nodes".

source code

project_up(B, create_using=None, name=None)
Project a bipartite graph B up onto its "Top Nodes".

source code

graph_clique_number(G, cliques=None)
Return the clique number (size the largest clique) for G.

source code

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.

source code

node_clique_number(G, nodes=None, with_labels=False, cliques=None)
Returns the size of the largest maximal clique containing each given node.

source code

number_of_cliques(G, nodes=None, cliques=None, with_labels=False)
Returns the number of maximal cliques for each node.

source code

cliques_containing_node(G, nodes=None, cliques=None, with_labels=False)
Returns a list of cliques containing the given node.

source code

_test_suite()

source code

Variables

[hide private]

__credits__ = ''

__revision__ = '$Revision: 1021 $'

Function Details

[hide private]

find_cliques(G)

source code

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},
 }

_extend(old_nodes, num_not, num_left, G, clique, cliques)

source code

A recursive helper routine for find_cliques

This recursive routine explores the "old_nodes" set of nodes for complete subgraphs. num_left is the size of old_nodes. The first num_not nodes are called the "not" group by B&K because they have already been considered. The rest (num_left-num_not) of them are called "candidates".

G is the graph, clique is the clique being built, cliques is a list of maximal cliques found so far.

make_max_clique_graph(G, create_using=None, name=None)

source code

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.

make_clique_bipartite(G, fpos=None, create_using=None, name=None)

source code

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.

project_down(B, create_using=None, name=None)

source code

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, name=None)

source code

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.

graph_clique_number(G, cliques=None)

source code

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

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

source code

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)

source code

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.

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

source code

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.