Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / tree / tests / test_coding.py @ 5cef0f13

History | View | Annotate | Download (4.16 KB)

1
# -*- encoding: utf-8 -*-
2
# test_coding.py - unit tests for the coding module
3
#
4
# Copyright 2015-2019 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)