aboutsummaryrefslogtreecommitdiff
path: root/.venv/lib/python3.12/site-packages/networkx/algorithms/tests/test_sparsifiers.py
blob: e8604e61ae45aca9092226a793a02b082b126738 (about) (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
"""Unit tests for the sparsifier computation functions."""

import pytest

import networkx as nx
from networkx.utils import py_random_state

_seed = 2


def _test_spanner(G, spanner, stretch, weight=None):
    """Test whether a spanner is valid.

    This function tests whether the given spanner is a subgraph of the
    given graph G with the same node set. It also tests for all shortest
    paths whether they adhere to the given stretch.

    Parameters
    ----------
    G : NetworkX graph
        The original graph for which the spanner was constructed.

    spanner : NetworkX graph
        The spanner to be tested.

    stretch : float
        The proclaimed stretch of the spanner.

    weight : object
        The edge attribute to use as distance.
    """
    # check node set
    assert set(G.nodes()) == set(spanner.nodes())

    # check edge set and weights
    for u, v in spanner.edges():
        assert G.has_edge(u, v)
        if weight:
            assert spanner[u][v][weight] == G[u][v][weight]

    # check connectivity and stretch
    original_length = dict(nx.shortest_path_length(G, weight=weight))
    spanner_length = dict(nx.shortest_path_length(spanner, weight=weight))
    for u in G.nodes():
        for v in G.nodes():
            if u in original_length and v in original_length[u]:
                assert spanner_length[u][v] <= stretch * original_length[u][v]


@py_random_state(1)
def _assign_random_weights(G, seed=None):
    """Assigns random weights to the edges of a graph.

    Parameters
    ----------

    G : NetworkX graph
        The original graph for which the spanner was constructed.

    seed : integer, random_state, or None (default)
        Indicator of random number generation state.
        See :ref:`Randomness<randomness>`.
    """
    for u, v in G.edges():
        G[u][v]["weight"] = seed.random()


def test_spanner_trivial():
    """Test a trivial spanner with stretch 1."""
    G = nx.complete_graph(20)
    spanner = nx.spanner(G, 1, seed=_seed)

    for u, v in G.edges:
        assert spanner.has_edge(u, v)


def test_spanner_unweighted_complete_graph():
    """Test spanner construction on a complete unweighted graph."""
    G = nx.complete_graph(20)

    spanner = nx.spanner(G, 4, seed=_seed)
    _test_spanner(G, spanner, 4)

    spanner = nx.spanner(G, 10, seed=_seed)
    _test_spanner(G, spanner, 10)


def test_spanner_weighted_complete_graph():
    """Test spanner construction on a complete weighted graph."""
    G = nx.complete_graph(20)
    _assign_random_weights(G, seed=_seed)

    spanner = nx.spanner(G, 4, weight="weight", seed=_seed)
    _test_spanner(G, spanner, 4, weight="weight")

    spanner = nx.spanner(G, 10, weight="weight", seed=_seed)
    _test_spanner(G, spanner, 10, weight="weight")


def test_spanner_unweighted_gnp_graph():
    """Test spanner construction on an unweighted gnp graph."""
    G = nx.gnp_random_graph(20, 0.4, seed=_seed)

    spanner = nx.spanner(G, 4, seed=_seed)
    _test_spanner(G, spanner, 4)

    spanner = nx.spanner(G, 10, seed=_seed)
    _test_spanner(G, spanner, 10)


def test_spanner_weighted_gnp_graph():
    """Test spanner construction on an weighted gnp graph."""
    G = nx.gnp_random_graph(20, 0.4, seed=_seed)
    _assign_random_weights(G, seed=_seed)

    spanner = nx.spanner(G, 4, weight="weight", seed=_seed)
    _test_spanner(G, spanner, 4, weight="weight")

    spanner = nx.spanner(G, 10, weight="weight", seed=_seed)
    _test_spanner(G, spanner, 10, weight="weight")


def test_spanner_unweighted_disconnected_graph():
    """Test spanner construction on a disconnected graph."""
    G = nx.disjoint_union(nx.complete_graph(10), nx.complete_graph(10))

    spanner = nx.spanner(G, 4, seed=_seed)
    _test_spanner(G, spanner, 4)

    spanner = nx.spanner(G, 10, seed=_seed)
    _test_spanner(G, spanner, 10)


def test_spanner_invalid_stretch():
    """Check whether an invalid stretch is caught."""
    with pytest.raises(ValueError):
        G = nx.empty_graph()
        nx.spanner(G, 0)