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)
|