Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# Source code for networkx.algorithms.approximation.clique

# -*- coding: utf-8 -*-
"""
Cliques.
"""
#   Nicholas Mancuso <nick.mancuso@gmail.com>
import networkx as nx
from networkx.algorithms.approximation import ramsey
__author__ = """Nicholas Mancuso (nick.mancuso@gmail.com)"""
__all__ = ["clique_removal","max_clique"]

[docs]def max_clique(G):
r"""Find the Maximum Clique

Finds the O(|V|/(log|V|)^2) apx of maximum clique/independent set
in the worst case.

Parameters
----------
G : NetworkX graph
Undirected graph

Returns
-------
clique : set
The apx-maximum clique of the graph

Notes
------
A clique in an undirected graph G = (V, E) is a subset of the vertex set
C \subseteq V, such that for every two vertices in C, there exists an edge
connecting the two. This is equivalent to saying that the subgraph
induced by C is complete (in some cases, the term clique may also refer
to the subgraph).

A maximum clique is a clique of the largest possible size in a given graph.
The clique number \omega(G) of a graph G is the number of
vertices in a maximum clique in G. The intersection number of
G is the smallest number of cliques that together cover all edges of G.

http://en.wikipedia.org/wiki/Maximum_clique

References
----------
.. [1] Boppana, R., & Halldórsson, M. M. (1992).
Approximating maximum independent sets by excluding subgraphs.
BIT Numerical Mathematics, 32(2), 180–196. Springer.
doi:10.1007/BF01994876
"""
if G is None:
raise ValueError("Expected NetworkX graph!")

# finding the maximum clique in a graph is equivalent to finding
# the independent set in the complementary graph
cgraph = nx.complement(G)
iset, _ = clique_removal(cgraph)
return iset

[docs]def clique_removal(G):
""" Repeatedly remove cliques from the graph.

Results in a O(|V|/(\log |V|)^2) approximation of maximum clique
& independent set. Returns the largest independent set found, along
with found maximal cliques.

Parameters
----------
G : NetworkX graph
Undirected graph

Returns
-------
max_ind_cliques : (set, list) tuple
Maximal independent set and list of maximal cliques (sets) in the graph.

References
----------
.. [1] Boppana, R., & Halldórsson, M. M. (1992).
Approximating maximum independent sets by excluding subgraphs.
BIT Numerical Mathematics, 32(2), 180–196. Springer.
"""
graph = G.copy()
c_i, i_i = ramsey.ramsey_R2(graph)
cliques = [c_i]
isets = [i_i]
while graph:
graph.remove_nodes_from(c_i)
c_i, i_i = ramsey.ramsey_R2(graph)
if c_i:
cliques.append(c_i)
if i_i:
isets.append(i_i)

maxiset = max(isets)
return maxiset, cliques