## Mercurial > repos > shellac > sam_consensus_v3

### view env/lib/python3.9/site-packages/networkx/algorithms/tests/test_sparsifiers.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

author | shellac |
---|---|

date | Mon, 22 Mar 2021 18:12:50 +0000 |

parents | |

children |

line wrap: on

line source

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