ioftools / networkxMiCe / networkxmaster / networkx / algorithms / tree / tests / test_coding.py @ 5cef0f13
History  View  Annotate  Download (4.16 KB)
1 
# * encoding: utf8 *


2 
# test_coding.py  unit tests for the coding module

3 
#

4 
# Copyright 20152019 NetworkX developers.

5 
#

6 
# This file is part of NetworkX.

7 
#

8 
# NetworkX is distributed under a BSD license; see LICENSE.txt for more

9 
# information.

10 
"""Unit tests for the :mod:`~networkx.algorithms.tree.coding` module."""

11 
from itertools import product 
12  
13 
from nose.tools import assert_equal 
14 
from nose.tools import assert_true 
15 
from nose.tools import raises 
16  
17 
import networkx as nx 
18 
from networkx.testing import assert_nodes_equal 
19 
from networkx.testing import assert_edges_equal 
20  
21  
22 
class TestPruferSequence(object): 
23 
"""Unit tests for the Prüfer sequence encoding and decoding

24 
functions.

25 

26 
"""

27  
28 
@raises(nx.NotATree)

29 
def test_nontree(self): 
30 
G = nx.cycle_graph(3)

31 
nx.to_prufer_sequence(G) 
32  
33 
@raises(nx.NetworkXPointlessConcept)

34 
def test_null_graph(self): 
35 
nx.to_prufer_sequence(nx.null_graph()) 
36  
37 
@raises(nx.NetworkXPointlessConcept)

38 
def test_trivial_graph(self): 
39 
nx.to_prufer_sequence(nx.trivial_graph()) 
40  
41 
@raises(KeyError) 
42 
def test_bad_integer_labels(self): 
43 
T = nx.Graph(nx.utils.pairwise('abc'))

44 
nx.to_prufer_sequence(T) 
45  
46 
def test_encoding(self): 
47 
"""Tests for encoding a tree as a Prüfer sequence using the

48 
iterative strategy.

49 

50 
"""

51 
# Example from Wikipedia.

52 
tree = nx.Graph([(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)]) 
53 
sequence = nx.to_prufer_sequence(tree) 
54 
assert_equal(sequence, [3, 3, 3, 4]) 
55  
56 
def test_decoding(self): 
57 
"""Tests for decoding a tree from a Prüfer sequence."""

58 
# Example from Wikipedia.

59 
sequence = [3, 3, 3, 4] 
60 
tree = nx.from_prufer_sequence(sequence) 
61 
assert_nodes_equal(list(tree), list(range(6))) 
62 
edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)] 
63 
assert_edges_equal(list(tree.edges()), edges)

64  
65 
def test_decoding2(self): 
66 
# Example from "An Optimal Algorithm for Prufer Codes".

67 
sequence = [2, 4, 0, 1, 3, 3] 
68 
tree = nx.from_prufer_sequence(sequence) 
69 
assert_nodes_equal(list(tree), list(range(8))) 
70 
edges = [(0, 1), (0, 4), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)] 
71 
assert_edges_equal(list(tree.edges()), edges)

72  
73 
def test_inverse(self): 
74 
"""Tests that the encoding and decoding functions are inverses.

75 

76 
"""

77 
for T in nx.nonisomorphic_trees(4): 
78 
T2 = nx.from_prufer_sequence(nx.to_prufer_sequence(T)) 
79 
assert_nodes_equal(list(T), list(T2)) 
80 
assert_edges_equal(list(T.edges()), list(T2.edges())) 
81  
82 
for seq in product(range(4), repeat=2): 
83 
seq2 = nx.to_prufer_sequence(nx.from_prufer_sequence(seq)) 
84 
assert_equal(list(seq), seq2)

85  
86  
87 
class TestNestedTuple(object): 
88 
"""Unit tests for the nested tuple encoding and decoding functions.

89 

90 
"""

91  
92 
@raises(nx.NotATree)

93 
def test_nontree(self): 
94 
G = nx.cycle_graph(3)

95 
nx.to_nested_tuple(G, 0)

96  
97 
@raises(nx.NodeNotFound)

98 
def test_unknown_root(self): 
99 
G = nx.path_graph(2)

100 
nx.to_nested_tuple(G, 'bogus')

101  
102 
def test_encoding(self): 
103 
T = nx.full_rary_tree(2, 2 ** 3  1) 
104 
expected = (((), ()), ((), ())) 
105 
actual = nx.to_nested_tuple(T, 0)

106 
assert_nodes_equal(expected, actual) 
107  
108 
def test_canonical_form(self): 
109 
T = nx.Graph() 
110 
T.add_edges_from([(0, 1), (0, 2), (0, 3)]) 
111 
T.add_edges_from([(1, 4), (1, 5)]) 
112 
T.add_edges_from([(3, 6), (3, 7)]) 
113 
root = 0

114 
actual = nx.to_nested_tuple(T, root, canonical_form=True)

115 
expected = ((), ((), ()), ((), ())) 
116 
assert_equal(actual, expected) 
117  
118 
def test_decoding(self): 
119 
balanced = (((), ()), ((), ())) 
120 
expected = nx.full_rary_tree(2, 2 ** 3  1) 
121 
actual = nx.from_nested_tuple(balanced) 
122 
assert_true(nx.is_isomorphic(expected, actual)) 
123  
124 
def test_sensible_relabeling(self): 
125 
balanced = (((), ()), ((), ())) 
126 
T = nx.from_nested_tuple(balanced, sensible_relabeling=True)

127 
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)] 
128 
assert_nodes_equal(list(T), list(range(2 ** 3  1))) 
129 
assert_edges_equal(list(T.edges()), edges)
