diff env/lib/python3.9/site-packages/networkx/algorithms/approximation/clique.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/algorithms/approximation/clique.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,159 @@
+"""Functions for computing large cliques."""
+import networkx as nx
+from networkx.utils import not_implemented_for
+from networkx.algorithms.approximation import ramsey
+
+__all__ = ["clique_removal", "max_clique", "large_clique_size"]
+
+
+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.
+
+    https://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
+
+
+def clique_removal(G):
+    r""" Repeatedly remove cliques from the graph.
+
+    Results in a $O(|V|/(\log |V|)^2)$ approximation of maximum clique
+    and 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
+        2-tuple of Maximal Independent Set and list of maximal cliques (sets).
+
+    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)
+    # Determine the largest independent set as measured by cardinality.
+    maxiset = max(isets, key=len)
+    return maxiset, cliques
+
+
+@not_implemented_for("directed")
+@not_implemented_for("multigraph")
+def large_clique_size(G):
+    """Find the size of a large clique in a graph.
+
+    A *clique* is a subset of nodes in which each pair of nodes is
+    adjacent. This function is a heuristic for finding the size of a
+    large clique in the graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    Returns
+    -------
+    int
+       The size of a large clique in the graph.
+
+    Notes
+    -----
+    This implementation is from [1]_. Its worst case time complexity is
+    :math:`O(n d^2)`, where *n* is the number of nodes in the graph and
+    *d* is the maximum degree.
+
+    This function is a heuristic, which means it may work well in
+    practice, but there is no rigorous mathematical guarantee on the
+    ratio between the returned number and the actual largest clique size
+    in the graph.
+
+    References
+    ----------
+    .. [1] Pattabiraman, Bharath, et al.
+       "Fast Algorithms for the Maximum Clique Problem on Massive Graphs
+       with Applications to Overlapping Community Detection."
+       *Internet Mathematics* 11.4-5 (2015): 421--448.
+       <https://doi.org/10.1080/15427951.2014.986778>
+
+    See also
+    --------
+
+    :func:`networkx.algorithms.approximation.clique.max_clique`
+        A function that returns an approximate maximum clique with a
+        guarantee on the approximation ratio.
+
+    :mod:`networkx.algorithms.clique`
+        Functions for finding the exact maximum clique in a graph.
+
+    """
+    degrees = G.degree
+
+    def _clique_heuristic(G, U, size, best_size):
+        if not U:
+            return max(best_size, size)
+        u = max(U, key=degrees)
+        U.remove(u)
+        N_prime = {v for v in G[u] if degrees[v] >= best_size}
+        return _clique_heuristic(G, U & N_prime, size + 1, best_size)
+
+    best_size = 0
+    nodes = (u for u in G if degrees[u] >= best_size)
+    for u in nodes:
+        neighbors = {v for v in G[u] if degrees[v] >= best_size}
+        best_size = _clique_heuristic(G, neighbors, 1, best_size)
+    return best_size