NetworkX

Source code for networkx.algorithms.approximation.clique

# -*- coding: utf-8 -*-
"""
Cliques.
"""
#   Copyright (C) 2011-2012 by
#   Nicholas Mancuso <nick.mancuso@gmail.com>
#   All rights reserved.
#   BSD license.
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