We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
Improve test coverage for clique.py
There is a line left uncovered in https://app.codecov.io/gh/networkx/networkx/blob/main/networkx/algorithms/approximation/clique.py and I am looking into it. There is a bit of an issue though when I try G = None. An attribute error is raised not a value error. 

Steps to Reproduce

from networkx.algorithms.approximation.clique import maximum_independent_set,max_clique
G=nx.Graph()
G.add_nodes_from([(2,3),(5,6),(3,6)])
max_clique(G=None)

output:

AttributeError                            Traceback (most recent call last)
Cell In[84], line 1
----> 1 max_clique(G)

File <class 'networkx.utils.decorators.argmap'> compilation 32:3, in argmap_max_clique_28(G)
      1 import bz2
      2 import collections
----> 3 import gzip
      4 import inspect
      5 import itertools

File ~\anaconda3\lib\site-packages\networkx\utils\decorators.py:83, in not_implemented_for.<locals>._not_implemented_for(g)
     82 def _not_implemented_for(g):
---> 83     if (mval is None or mval == g.is_multigraph()) and (
     84         dval is None or dval == g.is_directed()
     85     ):
     86         raise nx.NetworkXNotImplemented(errmsg)
     88     return g

AttributeError: 'NoneType' object has no attribute 'is_multigraph'

--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `networkx/algorithms/approximation/clique.py`
Content:
```
1 """Functions for computing large cliques and maximum independent sets."""
2 import networkx as nx
3 from networkx.algorithms.approximation import ramsey
4 from networkx.utils import not_implemented_for
5 
6 __all__ = [
7     "clique_removal",
8     "max_clique",
9     "large_clique_size",
10     "maximum_independent_set",
11 ]
12 
13 
14 @not_implemented_for("directed")
15 @not_implemented_for("multigraph")
16 def maximum_independent_set(G):
17     """Returns an approximate maximum independent set.
18 
19     Independent set or stable set is a set of vertices in a graph, no two of
20     which are adjacent. That is, it is a set I of vertices such that for every
21     two vertices in I, there is no edge connecting the two. Equivalently, each
22     edge in the graph has at most one endpoint in I. The size of an independent
23     set is the number of vertices it contains [1]_.
24 
25     A maximum independent set is a largest independent set for a given graph G
26     and its size is denoted $\\alpha(G)$. The problem of finding such a set is called
27     the maximum independent set problem and is an NP-hard optimization problem.
28     As such, it is unlikely that there exists an efficient algorithm for finding
29     a maximum independent set of a graph.
30 
31     The Independent Set algorithm is based on [2]_.
32 
33     Parameters
34     ----------
35     G : NetworkX graph
36         Undirected graph
37 
38     Returns
39     -------
40     iset : Set
41         The apx-maximum independent set
42 
43     Examples
44     --------
45     >>> G = nx.path_graph(10)
46     >>> nx.approximation.maximum_independent_set(G)
47     {0, 2, 4, 6, 9}
48 
49     Raises
50     ------
51     NetworkXNotImplemented
52         If the graph is directed or is a multigraph.
53 
54     Notes
55     -----
56     Finds the $O(|V|/(log|V|)^2)$ apx of independent set in the worst case.
57 
58     References
59     ----------
60     .. [1] `Wikipedia: Independent set
61         <https://en.wikipedia.org/wiki/Independent_set_(graph_theory)>`_
62     .. [2] Boppana, R., & Halldórsson, M. M. (1992).
63        Approximating maximum independent sets by excluding subgraphs.
64        BIT Numerical Mathematics, 32(2), 180–196. Springer.
65     """
66     iset, _ = clique_removal(G)
67     return iset
68 
69 
70 @not_implemented_for("directed")
71 @not_implemented_for("multigraph")
72 def max_clique(G):
73     r"""Find the Maximum Clique
74 
75     Finds the $O(|V|/(log|V|)^2)$ apx of maximum clique/independent set
76     in the worst case.
77 
78     Parameters
79     ----------
80     G : NetworkX graph
81         Undirected graph
82 
83     Returns
84     -------
85     clique : set
86         The apx-maximum clique of the graph
87 
88     Examples
89     --------
90     >>> G = nx.path_graph(10)
91     >>> nx.approximation.max_clique(G)
92     {8, 9}
93 
94     Raises
95     ------
96     NetworkXNotImplemented
97         If the graph is directed or is a multigraph.
98 
99     Notes
100     -----
101     A clique in an undirected graph G = (V, E) is a subset of the vertex set
102     `C \subseteq V` such that for every two vertices in C there exists an edge
103     connecting the two. This is equivalent to saying that the subgraph
104     induced by C is complete (in some cases, the term clique may also refer
105     to the subgraph).
106 
107     A maximum clique is a clique of the largest possible size in a given graph.
108     The clique number `\omega(G)` of a graph G is the number of
109     vertices in a maximum clique in G. The intersection number of
110     G is the smallest number of cliques that together cover all edges of G.
111 
112     https://en.wikipedia.org/wiki/Maximum_clique
113 
114     References
115     ----------
116     .. [1] Boppana, R., & Halldórsson, M. M. (1992).
117         Approximating maximum independent sets by excluding subgraphs.
118         BIT Numerical Mathematics, 32(2), 180–196. Springer.
119         doi:10.1007/BF01994876
120     """
121     if G is None:
122         raise ValueError("Expected NetworkX graph!")
123 
124     # finding the maximum clique in a graph is equivalent to finding
125     # the independent set in the complementary graph
126     cgraph = nx.complement(G)
127     iset, _ = clique_removal(cgraph)
128     return iset
129 
130 
131 @not_implemented_for("directed")
132 @not_implemented_for("multigraph")
133 def clique_removal(G):
134     r"""Repeatedly remove cliques from the graph.
135 
136     Results in a $O(|V|/(\log |V|)^2)$ approximation of maximum clique
137     and independent set. Returns the largest independent set found, along
138     with found maximal cliques.
139 
140     Parameters
141     ----------
142     G : NetworkX graph
143         Undirected graph
144 
145     Returns
146     -------
147     max_ind_cliques : (set, list) tuple
148         2-tuple of Maximal Independent Set and list of maximal cliques (sets).
149 
150     Examples
151     --------
152     >>> G = nx.path_graph(10)
153     >>> nx.approximation.clique_removal(G)
154     ({0, 2, 4, 6, 9}, [{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}])
155 
156     Raises
157     ------
158     NetworkXNotImplemented
159         If the graph is directed or is a multigraph.
160 
161     References
162     ----------
163     .. [1] Boppana, R., & Halldórsson, M. M. (1992).
164         Approximating maximum independent sets by excluding subgraphs.
165         BIT Numerical Mathematics, 32(2), 180–196. Springer.
166     """
167     graph = G.copy()
168     c_i, i_i = ramsey.ramsey_R2(graph)
169     cliques = [c_i]
170     isets = [i_i]
171     while graph:
172         graph.remove_nodes_from(c_i)
173         c_i, i_i = ramsey.ramsey_R2(graph)
174         if c_i:
175             cliques.append(c_i)
176         if i_i:
177             isets.append(i_i)
178     # Determine the largest independent set as measured by cardinality.
179     maxiset = max(isets, key=len)
180     return maxiset, cliques
181 
182 
183 @not_implemented_for("directed")
184 @not_implemented_for("multigraph")
185 def large_clique_size(G):
186     """Find the size of a large clique in a graph.
187 
188     A *clique* is a subset of nodes in which each pair of nodes is
189     adjacent. This function is a heuristic for finding the size of a
190     large clique in the graph.
191 
192     Parameters
193     ----------
194     G : NetworkX graph
195 
196     Returns
197     -------
198     k: integer
199        The size of a large clique in the graph.
200 
201     Examples
202     --------
203     >>> G = nx.path_graph(10)
204     >>> nx.approximation.large_clique_size(G)
205     2
206 
207     Raises
208     ------
209     NetworkXNotImplemented
210         If the graph is directed or is a multigraph.
211 
212     Notes
213     -----
214     This implementation is from [1]_. Its worst case time complexity is
215     :math:`O(n d^2)`, where *n* is the number of nodes in the graph and
216     *d* is the maximum degree.
217 
218     This function is a heuristic, which means it may work well in
219     practice, but there is no rigorous mathematical guarantee on the
220     ratio between the returned number and the actual largest clique size
221     in the graph.
222 
223     References
224     ----------
225     .. [1] Pattabiraman, Bharath, et al.
226        "Fast Algorithms for the Maximum Clique Problem on Massive Graphs
227        with Applications to Overlapping Community Detection."
228        *Internet Mathematics* 11.4-5 (2015): 421--448.
229        <https://doi.org/10.1080/15427951.2014.986778>
230 
231     See also
232     --------
233 
234     :func:`networkx.algorithms.approximation.clique.max_clique`
235         A function that returns an approximate maximum clique with a
236         guarantee on the approximation ratio.
237 
238     :mod:`networkx.algorithms.clique`
239         Functions for finding the exact maximum clique in a graph.
240 
241     """
242     degrees = G.degree
243 
244     def _clique_heuristic(G, U, size, best_size):
245         if not U:
246             return max(best_size, size)
247         u = max(U, key=degrees)
248         U.remove(u)
249         N_prime = {v for v in G[u] if degrees[v] >= best_size}
250         return _clique_heuristic(G, U & N_prime, size + 1, best_size)
251 
252     best_size = 0
253     nodes = (u for u in G if degrees[u] >= best_size)
254     for u in nodes:
255         neighbors = {v for v in G[u] if degrees[v] >= best_size}
256         best_size = _clique_heuristic(G, neighbors, 1, best_size)
257     return best_size
258
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/networkx/algorithms/approximation/clique.py b/networkx/algorithms/approximation/clique.py
--- a/networkx/algorithms/approximation/clique.py
+++ b/networkx/algorithms/approximation/clique.py
@@ -118,9 +118,6 @@
         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)

{"golden_diff": "diff --git a/networkx/algorithms/approximation/clique.py b/networkx/algorithms/approximation/clique.py\n--- a/networkx/algorithms/approximation/clique.py\n+++ b/networkx/algorithms/approximation/clique.py\n@@ -118,9 +118,6 @@\n         BIT Numerical Mathematics, 32(2), 180\u2013196. Springer.\n         doi:10.1007/BF01994876\n     \"\"\"\n-    if G is None:\n-        raise ValueError(\"Expected NetworkX graph!\")\n-\n     # finding the maximum clique in a graph is equivalent to finding\n     # the independent set in the complementary graph\n     cgraph = nx.complement(G)\n", "issue": "Improve test coverage for clique.py\nThere is a line left uncovered in https://app.codecov.io/gh/networkx/networkx/blob/main/networkx/algorithms/approximation/clique.py and I am looking into it. There is a bit of an issue though when I try G = None. An attribute error is raised not a value error. \r\n\r\nSteps to Reproduce\r\n\r\nfrom networkx.algorithms.approximation.clique import maximum_independent_set,max_clique\r\nG=nx.Graph()\r\nG.add_nodes_from([(2,3),(5,6),(3,6)])\r\nmax_clique(G=None)\r\n\r\noutput:\r\n\r\nAttributeError                            Traceback (most recent call last)\r\nCell In[84], line 1\r\n----> 1 max_clique(G)\r\n\r\nFile <class 'networkx.utils.decorators.argmap'> compilation 32:3, in argmap_max_clique_28(G)\r\n      1 import bz2\r\n      2 import collections\r\n----> 3 import gzip\r\n      4 import inspect\r\n      5 import itertools\r\n\r\nFile ~\\anaconda3\\lib\\site-packages\\networkx\\utils\\decorators.py:83, in not_implemented_for.<locals>._not_implemented_for(g)\r\n     82 def _not_implemented_for(g):\r\n---> 83     if (mval is None or mval == g.is_multigraph()) and (\r\n     84         dval is None or dval == g.is_directed()\r\n     85     ):\r\n     86         raise nx.NetworkXNotImplemented(errmsg)\r\n     88     return g\r\n\r\nAttributeError: 'NoneType' object has no attribute 'is_multigraph'\n", "before_files": [{"content": "\"\"\"Functions for computing large cliques and maximum independent sets.\"\"\"\nimport networkx as nx\nfrom networkx.algorithms.approximation import ramsey\nfrom networkx.utils import not_implemented_for\n\n__all__ = [\n    \"clique_removal\",\n    \"max_clique\",\n    \"large_clique_size\",\n    \"maximum_independent_set\",\n]\n\n\n@not_implemented_for(\"directed\")\n@not_implemented_for(\"multigraph\")\ndef maximum_independent_set(G):\n    \"\"\"Returns an approximate maximum independent set.\n\n    Independent set or stable set is a set of vertices in a graph, no two of\n    which are adjacent. That is, it is a set I of vertices such that for every\n    two vertices in I, there is no edge connecting the two. Equivalently, each\n    edge in the graph has at most one endpoint in I. The size of an independent\n    set is the number of vertices it contains [1]_.\n\n    A maximum independent set is a largest independent set for a given graph G\n    and its size is denoted $\\\\alpha(G)$. The problem of finding such a set is called\n    the maximum independent set problem and is an NP-hard optimization problem.\n    As such, it is unlikely that there exists an efficient algorithm for finding\n    a maximum independent set of a graph.\n\n    The Independent Set algorithm is based on [2]_.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n        Undirected graph\n\n    Returns\n    -------\n    iset : Set\n        The apx-maximum independent set\n\n    Examples\n    --------\n    >>> G = nx.path_graph(10)\n    >>> nx.approximation.maximum_independent_set(G)\n    {0, 2, 4, 6, 9}\n\n    Raises\n    ------\n    NetworkXNotImplemented\n        If the graph is directed or is a multigraph.\n\n    Notes\n    -----\n    Finds the $O(|V|/(log|V|)^2)$ apx of independent set in the worst case.\n\n    References\n    ----------\n    .. [1] `Wikipedia: Independent set\n        <https://en.wikipedia.org/wiki/Independent_set_(graph_theory)>`_\n    .. [2] Boppana, R., & Halld\u00f3rsson, M. M. (1992).\n       Approximating maximum independent sets by excluding subgraphs.\n       BIT Numerical Mathematics, 32(2), 180\u2013196. Springer.\n    \"\"\"\n    iset, _ = clique_removal(G)\n    return iset\n\n\n@not_implemented_for(\"directed\")\n@not_implemented_for(\"multigraph\")\ndef max_clique(G):\n    r\"\"\"Find the Maximum Clique\n\n    Finds the $O(|V|/(log|V|)^2)$ apx of maximum clique/independent set\n    in the worst case.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n        Undirected graph\n\n    Returns\n    -------\n    clique : set\n        The apx-maximum clique of the graph\n\n    Examples\n    --------\n    >>> G = nx.path_graph(10)\n    >>> nx.approximation.max_clique(G)\n    {8, 9}\n\n    Raises\n    ------\n    NetworkXNotImplemented\n        If the graph is directed or is a multigraph.\n\n    Notes\n    -----\n    A clique in an undirected graph G = (V, E) is a subset of the vertex set\n    `C \\subseteq V` such that for every two vertices in C there exists an edge\n    connecting the two. This is equivalent to saying that the subgraph\n    induced by C is complete (in some cases, the term clique may also refer\n    to the subgraph).\n\n    A maximum clique is a clique of the largest possible size in a given graph.\n    The clique number `\\omega(G)` of a graph G is the number of\n    vertices in a maximum clique in G. The intersection number of\n    G is the smallest number of cliques that together cover all edges of G.\n\n    https://en.wikipedia.org/wiki/Maximum_clique\n\n    References\n    ----------\n    .. [1] Boppana, R., & Halld\u00f3rsson, M. M. (1992).\n        Approximating maximum independent sets by excluding subgraphs.\n        BIT Numerical Mathematics, 32(2), 180\u2013196. Springer.\n        doi:10.1007/BF01994876\n    \"\"\"\n    if G is None:\n        raise ValueError(\"Expected NetworkX graph!\")\n\n    # finding the maximum clique in a graph is equivalent to finding\n    # the independent set in the complementary graph\n    cgraph = nx.complement(G)\n    iset, _ = clique_removal(cgraph)\n    return iset\n\n\n@not_implemented_for(\"directed\")\n@not_implemented_for(\"multigraph\")\ndef clique_removal(G):\n    r\"\"\"Repeatedly remove cliques from the graph.\n\n    Results in a $O(|V|/(\\log |V|)^2)$ approximation of maximum clique\n    and independent set. Returns the largest independent set found, along\n    with found maximal cliques.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n        Undirected graph\n\n    Returns\n    -------\n    max_ind_cliques : (set, list) tuple\n        2-tuple of Maximal Independent Set and list of maximal cliques (sets).\n\n    Examples\n    --------\n    >>> G = nx.path_graph(10)\n    >>> nx.approximation.clique_removal(G)\n    ({0, 2, 4, 6, 9}, [{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}])\n\n    Raises\n    ------\n    NetworkXNotImplemented\n        If the graph is directed or is a multigraph.\n\n    References\n    ----------\n    .. [1] Boppana, R., & Halld\u00f3rsson, M. M. (1992).\n        Approximating maximum independent sets by excluding subgraphs.\n        BIT Numerical Mathematics, 32(2), 180\u2013196. Springer.\n    \"\"\"\n    graph = G.copy()\n    c_i, i_i = ramsey.ramsey_R2(graph)\n    cliques = [c_i]\n    isets = [i_i]\n    while graph:\n        graph.remove_nodes_from(c_i)\n        c_i, i_i = ramsey.ramsey_R2(graph)\n        if c_i:\n            cliques.append(c_i)\n        if i_i:\n            isets.append(i_i)\n    # Determine the largest independent set as measured by cardinality.\n    maxiset = max(isets, key=len)\n    return maxiset, cliques\n\n\n@not_implemented_for(\"directed\")\n@not_implemented_for(\"multigraph\")\ndef large_clique_size(G):\n    \"\"\"Find the size of a large clique in a graph.\n\n    A *clique* is a subset of nodes in which each pair of nodes is\n    adjacent. This function is a heuristic for finding the size of a\n    large clique in the graph.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n\n    Returns\n    -------\n    k: integer\n       The size of a large clique in the graph.\n\n    Examples\n    --------\n    >>> G = nx.path_graph(10)\n    >>> nx.approximation.large_clique_size(G)\n    2\n\n    Raises\n    ------\n    NetworkXNotImplemented\n        If the graph is directed or is a multigraph.\n\n    Notes\n    -----\n    This implementation is from [1]_. Its worst case time complexity is\n    :math:`O(n d^2)`, where *n* is the number of nodes in the graph and\n    *d* is the maximum degree.\n\n    This function is a heuristic, which means it may work well in\n    practice, but there is no rigorous mathematical guarantee on the\n    ratio between the returned number and the actual largest clique size\n    in the graph.\n\n    References\n    ----------\n    .. [1] Pattabiraman, Bharath, et al.\n       \"Fast Algorithms for the Maximum Clique Problem on Massive Graphs\n       with Applications to Overlapping Community Detection.\"\n       *Internet Mathematics* 11.4-5 (2015): 421--448.\n       <https://doi.org/10.1080/15427951.2014.986778>\n\n    See also\n    --------\n\n    :func:`networkx.algorithms.approximation.clique.max_clique`\n        A function that returns an approximate maximum clique with a\n        guarantee on the approximation ratio.\n\n    :mod:`networkx.algorithms.clique`\n        Functions for finding the exact maximum clique in a graph.\n\n    \"\"\"\n    degrees = G.degree\n\n    def _clique_heuristic(G, U, size, best_size):\n        if not U:\n            return max(best_size, size)\n        u = max(U, key=degrees)\n        U.remove(u)\n        N_prime = {v for v in G[u] if degrees[v] >= best_size}\n        return _clique_heuristic(G, U & N_prime, size + 1, best_size)\n\n    best_size = 0\n    nodes = (u for u in G if degrees[u] >= best_size)\n    for u in nodes:\n        neighbors = {v for v in G[u] if degrees[v] >= best_size}\n        best_size = _clique_heuristic(G, neighbors, 1, best_size)\n    return best_size\n", "path": "networkx/algorithms/approximation/clique.py"}], "after_files": [{"content": "\"\"\"Functions for computing large cliques and maximum independent sets.\"\"\"\nimport networkx as nx\nfrom networkx.algorithms.approximation import ramsey\nfrom networkx.utils import not_implemented_for\n\n__all__ = [\n    \"clique_removal\",\n    \"max_clique\",\n    \"large_clique_size\",\n    \"maximum_independent_set\",\n]\n\n\n@not_implemented_for(\"directed\")\n@not_implemented_for(\"multigraph\")\ndef maximum_independent_set(G):\n    \"\"\"Returns an approximate maximum independent set.\n\n    Independent set or stable set is a set of vertices in a graph, no two of\n    which are adjacent. That is, it is a set I of vertices such that for every\n    two vertices in I, there is no edge connecting the two. Equivalently, each\n    edge in the graph has at most one endpoint in I. The size of an independent\n    set is the number of vertices it contains [1]_.\n\n    A maximum independent set is a largest independent set for a given graph G\n    and its size is denoted $\\\\alpha(G)$. The problem of finding such a set is called\n    the maximum independent set problem and is an NP-hard optimization problem.\n    As such, it is unlikely that there exists an efficient algorithm for finding\n    a maximum independent set of a graph.\n\n    The Independent Set algorithm is based on [2]_.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n        Undirected graph\n\n    Returns\n    -------\n    iset : Set\n        The apx-maximum independent set\n\n    Examples\n    --------\n    >>> G = nx.path_graph(10)\n    >>> nx.approximation.maximum_independent_set(G)\n    {0, 2, 4, 6, 9}\n\n    Raises\n    ------\n    NetworkXNotImplemented\n        If the graph is directed or is a multigraph.\n\n    Notes\n    -----\n    Finds the $O(|V|/(log|V|)^2)$ apx of independent set in the worst case.\n\n    References\n    ----------\n    .. [1] `Wikipedia: Independent set\n        <https://en.wikipedia.org/wiki/Independent_set_(graph_theory)>`_\n    .. [2] Boppana, R., & Halld\u00f3rsson, M. M. (1992).\n       Approximating maximum independent sets by excluding subgraphs.\n       BIT Numerical Mathematics, 32(2), 180\u2013196. Springer.\n    \"\"\"\n    iset, _ = clique_removal(G)\n    return iset\n\n\n@not_implemented_for(\"directed\")\n@not_implemented_for(\"multigraph\")\ndef max_clique(G):\n    r\"\"\"Find the Maximum Clique\n\n    Finds the $O(|V|/(log|V|)^2)$ apx of maximum clique/independent set\n    in the worst case.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n        Undirected graph\n\n    Returns\n    -------\n    clique : set\n        The apx-maximum clique of the graph\n\n    Examples\n    --------\n    >>> G = nx.path_graph(10)\n    >>> nx.approximation.max_clique(G)\n    {8, 9}\n\n    Raises\n    ------\n    NetworkXNotImplemented\n        If the graph is directed or is a multigraph.\n\n    Notes\n    -----\n    A clique in an undirected graph G = (V, E) is a subset of the vertex set\n    `C \\subseteq V` such that for every two vertices in C there exists an edge\n    connecting the two. This is equivalent to saying that the subgraph\n    induced by C is complete (in some cases, the term clique may also refer\n    to the subgraph).\n\n    A maximum clique is a clique of the largest possible size in a given graph.\n    The clique number `\\omega(G)` of a graph G is the number of\n    vertices in a maximum clique in G. The intersection number of\n    G is the smallest number of cliques that together cover all edges of G.\n\n    https://en.wikipedia.org/wiki/Maximum_clique\n\n    References\n    ----------\n    .. [1] Boppana, R., & Halld\u00f3rsson, M. M. (1992).\n        Approximating maximum independent sets by excluding subgraphs.\n        BIT Numerical Mathematics, 32(2), 180\u2013196. Springer.\n        doi:10.1007/BF01994876\n    \"\"\"\n    # finding the maximum clique in a graph is equivalent to finding\n    # the independent set in the complementary graph\n    cgraph = nx.complement(G)\n    iset, _ = clique_removal(cgraph)\n    return iset\n\n\n@not_implemented_for(\"directed\")\n@not_implemented_for(\"multigraph\")\ndef clique_removal(G):\n    r\"\"\"Repeatedly remove cliques from the graph.\n\n    Results in a $O(|V|/(\\log |V|)^2)$ approximation of maximum clique\n    and independent set. Returns the largest independent set found, along\n    with found maximal cliques.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n        Undirected graph\n\n    Returns\n    -------\n    max_ind_cliques : (set, list) tuple\n        2-tuple of Maximal Independent Set and list of maximal cliques (sets).\n\n    Examples\n    --------\n    >>> G = nx.path_graph(10)\n    >>> nx.approximation.clique_removal(G)\n    ({0, 2, 4, 6, 9}, [{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}])\n\n    Raises\n    ------\n    NetworkXNotImplemented\n        If the graph is directed or is a multigraph.\n\n    References\n    ----------\n    .. [1] Boppana, R., & Halld\u00f3rsson, M. M. (1992).\n        Approximating maximum independent sets by excluding subgraphs.\n        BIT Numerical Mathematics, 32(2), 180\u2013196. Springer.\n    \"\"\"\n    graph = G.copy()\n    c_i, i_i = ramsey.ramsey_R2(graph)\n    cliques = [c_i]\n    isets = [i_i]\n    while graph:\n        graph.remove_nodes_from(c_i)\n        c_i, i_i = ramsey.ramsey_R2(graph)\n        if c_i:\n            cliques.append(c_i)\n        if i_i:\n            isets.append(i_i)\n    # Determine the largest independent set as measured by cardinality.\n    maxiset = max(isets, key=len)\n    return maxiset, cliques\n\n\n@not_implemented_for(\"directed\")\n@not_implemented_for(\"multigraph\")\ndef large_clique_size(G):\n    \"\"\"Find the size of a large clique in a graph.\n\n    A *clique* is a subset of nodes in which each pair of nodes is\n    adjacent. This function is a heuristic for finding the size of a\n    large clique in the graph.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n\n    Returns\n    -------\n    k: integer\n       The size of a large clique in the graph.\n\n    Examples\n    --------\n    >>> G = nx.path_graph(10)\n    >>> nx.approximation.large_clique_size(G)\n    2\n\n    Raises\n    ------\n    NetworkXNotImplemented\n        If the graph is directed or is a multigraph.\n\n    Notes\n    -----\n    This implementation is from [1]_. Its worst case time complexity is\n    :math:`O(n d^2)`, where *n* is the number of nodes in the graph and\n    *d* is the maximum degree.\n\n    This function is a heuristic, which means it may work well in\n    practice, but there is no rigorous mathematical guarantee on the\n    ratio between the returned number and the actual largest clique size\n    in the graph.\n\n    References\n    ----------\n    .. [1] Pattabiraman, Bharath, et al.\n       \"Fast Algorithms for the Maximum Clique Problem on Massive Graphs\n       with Applications to Overlapping Community Detection.\"\n       *Internet Mathematics* 11.4-5 (2015): 421--448.\n       <https://doi.org/10.1080/15427951.2014.986778>\n\n    See also\n    --------\n\n    :func:`networkx.algorithms.approximation.clique.max_clique`\n        A function that returns an approximate maximum clique with a\n        guarantee on the approximation ratio.\n\n    :mod:`networkx.algorithms.clique`\n        Functions for finding the exact maximum clique in a graph.\n\n    \"\"\"\n    degrees = G.degree\n\n    def _clique_heuristic(G, U, size, best_size):\n        if not U:\n            return max(best_size, size)\n        u = max(U, key=degrees)\n        U.remove(u)\n        N_prime = {v for v in G[u] if degrees[v] >= best_size}\n        return _clique_heuristic(G, U & N_prime, size + 1, best_size)\n\n    best_size = 0\n    nodes = (u for u in G if degrees[u] >= best_size)\n    for u in nodes:\n        neighbors = {v for v in G[u] if degrees[v] >= best_size}\n        best_size = _clique_heuristic(G, neighbors, 1, best_size)\n    return best_size\n", "path": "networkx/algorithms/approximation/clique.py"}]}