### view env/lib/python3.9/site-packages/networkx/algorithms/approximation/tests/test_clique.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
line wrap: on
line source
```
"""Unit tests for the :mod:`networkx.algorithms.approximation.clique`
module.

"""

import networkx as nx
from networkx.algorithms.approximation import max_clique
from networkx.algorithms.approximation import clique_removal
from networkx.algorithms.approximation import large_clique_size

def is_independent_set(G, nodes):
"""Returns True if and only if `nodes` is a clique in `G`.

`G` is a NetworkX graph. `nodes` is an iterable of nodes in
`G`.

"""
return G.subgraph(nodes).number_of_edges() == 0

def is_clique(G, nodes):
"""Returns True if and only if `nodes` is an independent set
in `G`.

`G` is an undirected simple graph. `nodes` is an iterable of
nodes in `G`.

"""
H = G.subgraph(nodes)
n = len(H)
return H.number_of_edges() == n * (n - 1) // 2

class TestCliqueRemoval:
"""Unit tests for the
:func:`~networkx.algorithms.approximation.clique_removal` function.

"""

def test_trivial_graph(self):
G = nx.trivial_graph()
independent_set, cliques = clique_removal(G)
assert is_independent_set(G, independent_set)
assert all(is_clique(G, clique) for clique in cliques)
# In fact, we should only have 1-cliques, that is, singleton nodes.
assert all(len(clique) == 1 for clique in cliques)

def test_complete_graph(self):
G = nx.complete_graph(10)
independent_set, cliques = clique_removal(G)
assert is_independent_set(G, independent_set)
assert all(is_clique(G, clique) for clique in cliques)

def test_barbell_graph(self):
G = nx.barbell_graph(10, 5)
independent_set, cliques = clique_removal(G)
assert is_independent_set(G, independent_set)
assert all(is_clique(G, clique) for clique in cliques)

class TestMaxClique:
"""Unit tests for the :func:`networkx.algorithms.approximation.max_clique`
function.

"""

def test_null_graph(self):
G = nx.null_graph()
assert len(max_clique(G)) == 0

def test_complete_graph(self):
graph = nx.complete_graph(30)
# this should return the entire graph
mc = max_clique(graph)
assert 30 == len(mc)

def test_maximal_by_cardinality(self):
"""Tests that the maximal clique is computed according to maximum
cardinality of the sets.

For more information, see pull request #1531.

"""
G = nx.complete_graph(5)
clique = max_clique(G)
assert len(clique) > 1

G = nx.lollipop_graph(30, 2)
clique = max_clique(G)
assert len(clique) > 2

def test_large_clique_size():
G = nx.complete_graph(9)
nx.add_cycle(G, [9, 10, 11])