Statistics
| Branch: | Revision:

## iof-tools / networkxMiCe / networkx-master / networkx / generators / tests / test_classic.py @ 5cef0f13

History | View | Annotate | Download (16.3 KB)

 1 ```#!/usr/bin/env python ``` ```""" ``` ```==================== ``` ```Generators - Classic ``` ```==================== ``` ``` ``` ```Unit tests for various classic graph generators in generators/classic.py ``` ```""" ``` ```import itertools ``` ```from nose.tools import * ``` ```import networkx as nx ``` ```from networkx import * ``` ```from networkx.algorithms.isomorphism.isomorph import graph_could_be_isomorphic ``` ```from networkx.testing import assert_edges_equal ``` ```from networkx.testing import assert_nodes_equal ``` ```is_isomorphic = graph_could_be_isomorphic ``` ```class TestGeneratorClassic(): ``` ``` def test_balanced_tree(self): ``` ``` # balanced_tree(r,h) is a tree with (r**(h+1)-1)/(r-1) edges ``` ``` for r, h in [(2, 2), (3, 3), (6, 2)]: ``` ``` t = balanced_tree(r, h) ``` ``` order = t.order() ``` ``` assert_true(order == (r**(h + 1) - 1) / (r - 1)) ``` ``` assert_true(is_connected(t)) ``` ``` assert_true(t.size() == order - 1) ``` ``` dh = degree_histogram(t) ``` ``` assert_equal(dh[0], 0) # no nodes of 0 ``` ``` assert_equal(dh[1], r**h) # nodes of degree 1 are leaves ``` ``` assert_equal(dh[r], 1) # root is degree r ``` ``` assert_equal(dh[r + 1], order - r**h - 1) # everyone else is degree r+1 ``` ``` assert_equal(len(dh), r + 2) ``` ``` def test_balanced_tree_star(self): ``` ``` # balanced_tree(r,1) is the r-star ``` ``` t = balanced_tree(r=2, h=1) ``` ``` assert_true(is_isomorphic(t, star_graph(2))) ``` ``` t = balanced_tree(r=5, h=1) ``` ``` assert_true(is_isomorphic(t, star_graph(5))) ``` ``` t = balanced_tree(r=10, h=1) ``` ``` assert_true(is_isomorphic(t, star_graph(10))) ``` ``` def test_balanced_tree_path(self): ``` ``` """Tests that the balanced tree with branching factor one is the ``` ``` path graph. ``` ``` ``` ``` """ ``` ``` # A tree of height four has five levels. ``` ``` T = balanced_tree(1, 4) ``` ``` P = path_graph(5) ``` ``` assert_true(is_isomorphic(T, P)) ``` ``` def test_full_rary_tree(self): ``` ``` r = 2 ``` ``` n = 9 ``` ``` t = full_rary_tree(r, n) ``` ``` assert_equal(t.order(), n) ``` ``` assert_true(is_connected(t)) ``` ``` dh = degree_histogram(t) ``` ``` assert_equal(dh[0], 0) # no nodes of 0 ``` ``` assert_equal(dh[1], 5) # nodes of degree 1 are leaves ``` ``` assert_equal(dh[r], 1) # root is degree r ``` ``` assert_equal(dh[r + 1], 9 - 5 - 1) # everyone else is degree r+1 ``` ``` assert_equal(len(dh), r + 2) ``` ``` def test_full_rary_tree_balanced(self): ``` ``` t = full_rary_tree(2, 15) ``` ``` th = balanced_tree(2, 3) ``` ``` assert_true(is_isomorphic(t, th)) ``` ``` def test_full_rary_tree_path(self): ``` ``` t = full_rary_tree(1, 10) ``` ``` assert_true(is_isomorphic(t, path_graph(10))) ``` ``` def test_full_rary_tree_empty(self): ``` ``` t = full_rary_tree(0, 10) ``` ``` assert_true(is_isomorphic(t, empty_graph(10))) ``` ``` t = full_rary_tree(3, 0) ``` ``` assert_true(is_isomorphic(t, empty_graph(0))) ``` ``` def test_full_rary_tree_3_20(self): ``` ``` t = full_rary_tree(3, 20) ``` ``` assert_equal(t.order(), 20) ``` ``` def test_barbell_graph(self): ``` ``` # number of nodes = 2*m1 + m2 (2 m1-complete graphs + m2-path + 2 edges) ``` ``` # number of edges = 2*(number_of_edges(m1-complete graph) + m2 + 1 ``` ``` m1 = 3 ``` ``` m2 = 5 ``` ``` b = barbell_graph(m1, m2) ``` ``` assert_true(number_of_nodes(b) == 2 * m1 + m2) ``` ``` assert_true(number_of_edges(b) == m1 * (m1 - 1) + m2 + 1) ``` ``` m1 = 4 ``` ``` m2 = 10 ``` ``` b = barbell_graph(m1, m2) ``` ``` assert_true(number_of_nodes(b) == 2 * m1 + m2) ``` ``` assert_true(number_of_edges(b) == m1 * (m1 - 1) + m2 + 1) ``` ``` m1 = 3 ``` ``` m2 = 20 ``` ``` b = barbell_graph(m1, m2) ``` ``` assert_true(number_of_nodes(b) == 2 * m1 + m2) ``` ``` assert_true(number_of_edges(b) == m1 * (m1 - 1) + m2 + 1) ``` ``` # Raise NetworkXError if m1<2 ``` ``` m1 = 1 ``` ``` m2 = 20 ``` ``` assert_raises(networkx.exception.NetworkXError, barbell_graph, m1, m2) ``` ``` # Raise NetworkXError if m2<0 ``` ``` m1 = 5 ``` ``` m2 = -2 ``` ``` assert_raises(networkx.exception.NetworkXError, barbell_graph, m1, m2) ``` ``` # barbell_graph(2,m) = path_graph(m+4) ``` ``` m1 = 2 ``` ``` m2 = 5 ``` ``` b = barbell_graph(m1, m2) ``` ``` assert_true(is_isomorphic(b, path_graph(m2 + 4))) ``` ``` m1 = 2 ``` ``` m2 = 10 ``` ``` b = barbell_graph(m1, m2) ``` ``` assert_true(is_isomorphic(b, path_graph(m2 + 4))) ``` ``` m1 = 2 ``` ``` m2 = 20 ``` ``` b = barbell_graph(m1, m2) ``` ``` assert_true(is_isomorphic(b, path_graph(m2 + 4))) ``` ``` assert_raises(networkx.exception.NetworkXError, barbell_graph, m1, m2, ``` ``` create_using=DiGraph()) ``` ``` mb = barbell_graph(m1, m2, create_using=MultiGraph()) ``` ``` assert_edges_equal(mb.edges(), b.edges()) ``` ``` def test_binomial_tree(self): ``` ``` for n in range(0,4): ``` ``` b = binomial_tree(n) ``` ``` assert_true(number_of_nodes(b) == 2**n) ``` ``` assert_true(number_of_edges(b) == (2**n - 1)) ``` ``` def test_complete_graph(self): ``` ``` # complete_graph(m) is a connected graph with ``` ``` # m nodes and m*(m+1)/2 edges ``` ``` for m in [0, 1, 3, 5]: ``` ``` g = complete_graph(m) ``` ``` assert_true(number_of_nodes(g) == m) ``` ``` assert_true(number_of_edges(g) == m * (m - 1) // 2) ``` ``` mg = complete_graph(m, create_using=MultiGraph()) ``` ``` assert_edges_equal(mg.edges(), g.edges()) ``` ``` g = complete_graph("abc") ``` ``` assert_nodes_equal(g.nodes(), ['a', 'b', 'c']) ``` ``` assert_equal(g.size(), 3) ``` ``` def test_complete_digraph(self): ``` ``` # complete_graph(m) is a connected graph with ``` ``` # m nodes and m*(m+1)/2 edges ``` ``` for m in [0, 1, 3, 5]: ``` ``` g = complete_graph(m, create_using=DiGraph()) ``` ``` assert_true(number_of_nodes(g) == m) ``` ``` assert_true(number_of_edges(g) == m * (m - 1)) ``` ``` g = complete_graph("abc", create_using=DiGraph()) ``` ``` assert_equal(len(g), 3) ``` ``` assert_equal(g.size(), 6) ``` ``` assert_true(g.is_directed()) ``` ``` def test_circular_ladder_graph(self): ``` ``` G = circular_ladder_graph(5) ``` ``` assert_raises(networkx.exception.NetworkXError, circular_ladder_graph, ``` ``` 5, create_using=DiGraph()) ``` ``` mG = circular_ladder_graph(5, create_using=MultiGraph()) ``` ``` assert_edges_equal(mG.edges(), G.edges()) ``` ``` def test_circulant_graph(self): ``` ``` # Ci_n(1) is the cycle graph for all n ``` ``` Ci6_1 = circulant_graph(6, [1]) ``` ``` C6 = cycle_graph(6) ``` ``` assert_edges_equal(Ci6_1.edges(), C6.edges()) ``` ``` # Ci_n(1, 2, ..., n div 2) is the complete graph for all n ``` ``` Ci7 = circulant_graph(7, [1, 2, 3]) ``` ``` K7 = complete_graph(7) ``` ``` assert_edges_equal(Ci7.edges(), K7.edges()) ``` ``` # Ci_6(1, 3) is K_3,3 i.e. the utility graph ``` ``` Ci6_1_3 = circulant_graph(6, [1, 3]) ``` ``` K3_3 = complete_bipartite_graph(3, 3) ``` ``` assert_true(is_isomorphic(Ci6_1_3, K3_3)) ``` ``` def test_cycle_graph(self): ``` ``` G = cycle_graph(4) ``` ``` assert_edges_equal(G.edges(), [(0, 1), (0, 3), (1, 2), (2, 3)]) ``` ``` mG = cycle_graph(4, create_using=MultiGraph()) ``` ``` assert_edges_equal(mG.edges(), [(0, 1), (0, 3), (1, 2), (2, 3)]) ``` ``` G = cycle_graph(4, create_using=DiGraph()) ``` ``` assert_false(G.has_edge(2, 1)) ``` ``` assert_true(G.has_edge(1, 2)) ``` ``` assert_true(G.is_directed()) ``` ``` G = cycle_graph("abc") ``` ``` assert_equal(len(G), 3) ``` ``` assert_equal(G.size(), 3) ``` ``` g = cycle_graph("abc", DiGraph()) ``` ``` assert_equal(len(g), 3) ``` ``` assert_equal(g.size(), 3) ``` ``` assert_true(g.is_directed()) ``` ``` def test_dorogovtsev_goltsev_mendes_graph(self): ``` ``` G = dorogovtsev_goltsev_mendes_graph(0) ``` ``` assert_edges_equal(G.edges(), [(0, 1)]) ``` ``` assert_nodes_equal(list(G), [0, 1]) ``` ``` G = dorogovtsev_goltsev_mendes_graph(1) ``` ``` assert_edges_equal(G.edges(), [(0, 1), (0, 2), (1, 2)]) ``` ``` assert_equal(average_clustering(G), 1.0) ``` ``` assert_equal(sorted(triangles(G).values()), [1, 1, 1]) ``` ``` G = dorogovtsev_goltsev_mendes_graph(10) ``` ``` assert_equal(number_of_nodes(G), 29526) ``` ``` assert_equal(number_of_edges(G), 59049) ``` ``` assert_equal(G.degree(0), 1024) ``` ``` assert_equal(G.degree(1), 1024) ``` ``` assert_equal(G.degree(2), 1024) ``` ``` assert_raises(networkx.exception.NetworkXError, ``` ``` dorogovtsev_goltsev_mendes_graph, 7, ``` ``` create_using=DiGraph()) ``` ``` assert_raises(networkx.exception.NetworkXError, ``` ``` dorogovtsev_goltsev_mendes_graph, 7, ``` ``` create_using=MultiGraph()) ``` ``` def test_create_using(self): ``` ``` G = empty_graph() ``` ``` assert_true(isinstance(G, Graph)) ``` ``` assert_raises(TypeError, empty_graph, create_using=0.0) ``` ``` assert_raises(TypeError, empty_graph, create_using="Graph") ``` ``` G = empty_graph(create_using=MultiGraph) ``` ``` assert_true(isinstance(G, MultiGraph)) ``` ``` G = empty_graph(create_using=DiGraph) ``` ``` assert_true(isinstance(G, DiGraph)) ``` ``` G = empty_graph(create_using=DiGraph, default=MultiGraph) ``` ``` assert_true(isinstance(G, DiGraph)) ``` ``` G = empty_graph(create_using=None, default=MultiGraph) ``` ``` assert_true(isinstance(G, MultiGraph)) ``` ``` G = empty_graph(default=MultiGraph) ``` ``` assert_true(isinstance(G, MultiGraph)) ``` ``` G = path_graph(5) ``` ``` H = empty_graph(create_using=G) ``` ``` assert_false(H.is_multigraph()) ``` ``` assert_false(H.is_directed()) ``` ``` assert_equal(len(H), 0) ``` ``` assert_is(G, H) ``` ``` H = empty_graph(create_using=MultiGraph()) ``` ``` assert_true(H.is_multigraph()) ``` ``` assert_false(H.is_directed()) ``` ``` assert_is_not(G, H) ``` ``` def test_empty_graph(self): ``` ``` G = empty_graph() ``` ``` assert_equal(number_of_nodes(G), 0) ``` ``` G = empty_graph(42) ``` ``` assert_equal(number_of_nodes(G), 42) ``` ``` assert_equal(number_of_edges(G), 0) ``` ``` G = empty_graph("abc") ``` ``` assert_equal(len(G), 3) ``` ``` assert_equal(G.size(), 0) ``` ``` # create empty digraph ``` ``` G = empty_graph(42, create_using=DiGraph(name="duh")) ``` ``` assert_equal(number_of_nodes(G), 42) ``` ``` assert_equal(number_of_edges(G), 0) ``` ``` assert_true(isinstance(G, DiGraph)) ``` ``` # create empty multigraph ``` ``` G = empty_graph(42, create_using=MultiGraph(name="duh")) ``` ``` assert_equal(number_of_nodes(G), 42) ``` ``` assert_equal(number_of_edges(G), 0) ``` ``` assert_true(isinstance(G, MultiGraph)) ``` ``` # create empty graph from another ``` ``` pete = petersen_graph() ``` ``` G = empty_graph(42, create_using=pete) ``` ``` assert_equal(number_of_nodes(G), 42) ``` ``` assert_equal(number_of_edges(G), 0) ``` ``` assert_true(isinstance(G, Graph)) ``` ``` def test_ladder_graph(self): ``` ``` for i, G in [(0, empty_graph(0)), (1, path_graph(2)), ``` ``` (2, hypercube_graph(2)), (10, grid_graph([2, 10]))]: ``` ``` assert_true(is_isomorphic(ladder_graph(i), G)) ``` ``` assert_raises(networkx.exception.NetworkXError, ``` ``` ladder_graph, 2, create_using=DiGraph()) ``` ``` g = ladder_graph(2) ``` ``` mg = ladder_graph(2, create_using=MultiGraph()) ``` ``` assert_edges_equal(mg.edges(), g.edges()) ``` ``` def test_lollipop_graph(self): ``` ``` # number of nodes = m1 + m2 ``` ``` # number of edges = number_of_edges(complete_graph(m1)) + m2 ``` ``` for m1, m2 in [(3, 5), (4, 10), (3, 20)]: ``` ``` b = lollipop_graph(m1, m2) ``` ``` assert_equal(number_of_nodes(b), m1 + m2) ``` ``` assert_equal(number_of_edges(b), m1 * (m1 - 1) / 2 + m2) ``` ``` # Raise NetworkXError if m<2 ``` ``` assert_raises(networkx.exception.NetworkXError, ``` ``` lollipop_graph, 1, 20) ``` ``` # Raise NetworkXError if n<0 ``` ``` assert_raises(networkx.exception.NetworkXError, ``` ``` lollipop_graph, 5, -2) ``` ``` # lollipop_graph(2,m) = path_graph(m+2) ``` ``` for m1, m2 in [(2, 5), (2, 10), (2, 20)]: ``` ``` b = lollipop_graph(m1, m2) ``` ``` assert_true(is_isomorphic(b, path_graph(m2 + 2))) ``` ``` assert_raises(networkx.exception.NetworkXError, ``` ``` lollipop_graph, m1, m2, create_using=DiGraph()) ``` ``` mb = lollipop_graph(m1, m2, create_using=MultiGraph()) ``` ``` assert_edges_equal(mb.edges(), b.edges()) ``` ``` g = lollipop_graph([1, 2, 3, 4], "abc") ``` ``` assert_equal(len(g), 7) ``` ``` assert_equal(g.size(), 9) ``` ``` def test_null_graph(self): ``` ``` assert_equal(number_of_nodes(null_graph()), 0) ``` ``` def test_path_graph(self): ``` ``` p = path_graph(0) ``` ``` assert_true(is_isomorphic(p, null_graph())) ``` ``` p = path_graph(1) ``` ``` assert_true(is_isomorphic(p, empty_graph(1))) ``` ``` p = path_graph(10) ``` ``` assert_true(is_connected(p)) ``` ``` assert_equal(sorted(d for n, d in p.degree()), ``` ``` [1, 1, 2, 2, 2, 2, 2, 2, 2, 2]) ``` ``` assert_equal(p.order() - 1, p.size()) ``` ``` dp = path_graph(3, create_using=DiGraph()) ``` ``` assert_true(dp.has_edge(0, 1)) ``` ``` assert_false(dp.has_edge(1, 0)) ``` ``` mp = path_graph(10, create_using=MultiGraph()) ``` ``` assert_edges_equal(mp.edges(), p.edges()) ``` ``` G = path_graph("abc") ``` ``` assert_equal(len(G), 3) ``` ``` assert_equal(G.size(), 2) ``` ``` g = path_graph("abc", DiGraph()) ``` ``` assert_equal(len(g), 3) ``` ``` assert_equal(g.size(), 2) ``` ``` assert_true(g.is_directed()) ``` ``` def test_star_graph(self): ``` ``` assert_true(is_isomorphic(star_graph(0), empty_graph(1))) ``` ``` assert_true(is_isomorphic(star_graph(1), path_graph(2))) ``` ``` assert_true(is_isomorphic(star_graph(2), path_graph(3))) ``` ``` assert_true(is_isomorphic(star_graph(5), complete_bipartite_graph(1, 5))) ``` ``` s = star_graph(10) ``` ``` assert_equal(sorted(d for n, d in s.degree()), ``` ``` [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 10]) ``` ``` assert_raises(networkx.exception.NetworkXError, ``` ``` star_graph, 10, create_using=DiGraph()) ``` ``` ms = star_graph(10, create_using=MultiGraph()) ``` ``` assert_edges_equal(ms.edges(), s.edges()) ``` ``` G = star_graph("abcdefg") ``` ``` assert_equal(len(G), 7) ``` ``` assert_equal(G.size(), 6) ``` ``` def test_trivial_graph(self): ``` ``` assert_equal(number_of_nodes(trivial_graph()), 1) ``` ``` def test_turan_graph(self): ``` ``` assert_equal(number_of_edges(turan_graph(13, 4)), 63) ``` ``` assert_true(is_isomorphic(turan_graph(13, 4), complete_multipartite_graph(3, 4, 3, 3))) ``` ``` def test_wheel_graph(self): ``` ``` for n, G in [(0, null_graph()), (1, empty_graph(1)), ``` ``` (2, path_graph(2)), (3, complete_graph(3)), ``` ``` (4, complete_graph(4))]: ``` ``` g = wheel_graph(n) ``` ``` assert_true(is_isomorphic(g, G)) ``` ``` g = wheel_graph(10) ``` ``` assert_equal(sorted(d for n, d in g.degree()), ``` ``` [3, 3, 3, 3, 3, 3, 3, 3, 3, 9]) ``` ``` assert_raises(networkx.exception.NetworkXError, ``` ``` wheel_graph, 10, create_using=DiGraph()) ``` ``` mg = wheel_graph(10, create_using=MultiGraph()) ``` ``` assert_edges_equal(mg.edges(), g.edges()) ``` ``` G = wheel_graph("abc") ``` ``` assert_equal(len(G), 3) ``` ``` assert_equal(G.size(), 3) ``` ``` def test_complete_0_partite_graph(self): ``` ``` """Tests that the complete 0-partite graph is the null graph.""" ``` ``` G = complete_multipartite_graph() ``` ``` H = null_graph() ``` ``` assert_nodes_equal(G, H) ``` ``` assert_edges_equal(G.edges(), H.edges()) ``` ``` def test_complete_1_partite_graph(self): ``` ``` """Tests that the complete 1-partite graph is the empty graph.""" ``` ``` G = complete_multipartite_graph(3) ``` ``` H = empty_graph(3) ``` ``` assert_nodes_equal(G, H) ``` ``` assert_edges_equal(G.edges(), H.edges()) ``` ``` def test_complete_2_partite_graph(self): ``` ``` """Tests that the complete 2-partite graph is the complete bipartite ``` ``` graph. ``` ``` ``` ``` """ ``` ``` G = complete_multipartite_graph(2, 3) ``` ``` H = complete_bipartite_graph(2, 3) ``` ``` assert_nodes_equal(G, H) ``` ``` assert_edges_equal(G.edges(), H.edges()) ``` ``` def test_complete_multipartite_graph(self): ``` ``` """Tests for generating the complete multipartite graph.""" ``` ``` G = complete_multipartite_graph(2, 3, 4) ``` ``` blocks = [(0, 1), (2, 3, 4), (5, 6, 7, 8)] ``` ``` # Within each block, no two vertices should be adjacent. ``` ``` for block in blocks: ``` ``` for u, v in itertools.combinations_with_replacement(block, 2): ``` ``` assert_true(v not in G[u]) ``` ``` assert_equal(G.nodes[u], G.nodes[v]) ``` ``` # Across blocks, all vertices should be adjacent. ``` ``` for (block1, block2) in itertools.combinations(blocks, 2): ``` ``` for u, v in itertools.product(block1, block2): ``` ``` assert_true(v in G[u]) ``` ``` assert_not_equal(G.nodes[u], G.nodes[v]) ```