Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (4.02 KB)

1

    
2
from nose.tools import *
3
import networkx as nx
4

    
5

    
6
class TestTreeRecognition(object):
7

    
8
    graph = nx.Graph
9
    multigraph = nx.MultiGraph
10

    
11
    def setUp(self):
12

    
13
        self.T1 = self.graph()
14

    
15
        self.T2 = self.graph()
16
        self.T2.add_node(1)
17

    
18
        self.T3 = self.graph()
19
        self.T3.add_nodes_from(range(5))
20
        edges = [(i, i + 1) for i in range(4)]
21
        self.T3.add_edges_from(edges)
22

    
23
        self.T5 = self.multigraph()
24
        self.T5.add_nodes_from(range(5))
25
        edges = [(i, i + 1) for i in range(4)]
26
        self.T5.add_edges_from(edges)
27

    
28
        self.T6 = self.graph()
29
        self.T6.add_nodes_from([6, 7])
30
        self.T6.add_edge(6, 7)
31

    
32
        self.F1 = nx.compose(self.T6, self.T3)
33

    
34
        self.N4 = self.graph()
35
        self.N4.add_node(1)
36
        self.N4.add_edge(1, 1)
37

    
38
        self.N5 = self.graph()
39
        self.N5.add_nodes_from(range(5))
40

    
41
        self.N6 = self.graph()
42
        self.N6.add_nodes_from(range(3))
43
        self.N6.add_edges_from([(0, 1), (1, 2), (2, 0)])
44

    
45
        self.NF1 = nx.compose(self.T6, self.N6)
46

    
47
    @raises(nx.NetworkXPointlessConcept)
48
    def test_null_tree(self):
49
        nx.is_tree(self.graph())
50
        nx.is_tree(self.multigraph())
51

    
52
    @raises(nx.NetworkXPointlessConcept)
53
    def test_null_forest(self):
54
        nx.is_forest(self.graph())
55
        nx.is_forest(self.multigraph())
56

    
57
    def test_is_tree(self):
58
        assert_true(nx.is_tree(self.T2))
59
        assert_true(nx.is_tree(self.T3))
60
        assert_true(nx.is_tree(self.T5))
61

    
62
    def test_is_not_tree(self):
63
        assert_false(nx.is_tree(self.N4))
64
        assert_false(nx.is_tree(self.N5))
65
        assert_false(nx.is_tree(self.N6))
66

    
67
    def test_is_forest(self):
68
        assert_true(nx.is_forest(self.T2))
69
        assert_true(nx.is_forest(self.T3))
70
        assert_true(nx.is_forest(self.T5))
71
        assert_true(nx.is_forest(self.F1))
72
        assert_true(nx.is_forest(self.N5))
73

    
74
    def test_is_not_forest(self):
75
        assert_false(nx.is_forest(self.N4))
76
        assert_false(nx.is_forest(self.N6))
77
        assert_false(nx.is_forest(self.NF1))
78

    
79

    
80
class TestDirectedTreeRecognition(TestTreeRecognition):
81
    graph = nx.DiGraph
82
    multigraph = nx.MultiDiGraph
83

    
84

    
85
def test_disconnected_graph():
86
    # https://github.com/networkx/networkx/issues/1144
87
    G = nx.Graph()
88
    G.add_edges_from([(0, 1), (1, 2), (2, 0), (3, 4)])
89
    assert_false(nx.is_tree(G))
90

    
91
    G = nx.DiGraph()
92
    G.add_edges_from([(0, 1), (1, 2), (2, 0), (3, 4)])
93
    assert_false(nx.is_tree(G))
94

    
95

    
96
def test_dag_nontree():
97
    G = nx.DiGraph()
98
    G.add_edges_from([(0, 1), (0, 2), (1, 2)])
99
    assert_false(nx.is_tree(G))
100
    assert_true(nx.is_directed_acyclic_graph(G))
101

    
102

    
103
def test_multicycle():
104
    G = nx.MultiDiGraph()
105
    G.add_edges_from([(0, 1), (0, 1)])
106
    assert_false(nx.is_tree(G))
107
    assert_true(nx.is_directed_acyclic_graph(G))
108

    
109

    
110
def test_emptybranch():
111
    G = nx.DiGraph()
112
    G.add_nodes_from(range(10))
113
    assert_true(nx.is_branching(G))
114
    assert_false(nx.is_arborescence(G))
115

    
116

    
117
def test_path():
118
    G = nx.DiGraph()
119
    nx.add_path(G, range(5))
120
    assert_true(nx.is_branching(G))
121
    assert_true(nx.is_arborescence(G))
122

    
123

    
124
def test_notbranching1():
125
    # Acyclic violation.
126
    G = nx.MultiDiGraph()
127
    G.add_nodes_from(range(10))
128
    G.add_edges_from([(0, 1), (1, 0)])
129
    assert_false(nx.is_branching(G))
130
    assert_false(nx.is_arborescence(G))
131

    
132

    
133
def test_notbranching2():
134
    # In-degree violation.
135
    G = nx.MultiDiGraph()
136
    G.add_nodes_from(range(10))
137
    G.add_edges_from([(0, 1), (0, 2), (3, 2)])
138
    assert_false(nx.is_branching(G))
139
    assert_false(nx.is_arborescence(G))
140

    
141

    
142
def test_notarborescence1():
143
    # Not an arborescence due to not spanning.
144
    G = nx.MultiDiGraph()
145
    G.add_nodes_from(range(10))
146
    G.add_edges_from([(0, 1), (0, 2), (1, 3), (5, 6)])
147
    assert_true(nx.is_branching(G))
148
    assert_false(nx.is_arborescence(G))
149

    
150

    
151
def test_notarborescence2():
152
    # Not an arborescence due to in-degree violation.
153
    G = nx.MultiDiGraph()
154
    nx.add_path(G, range(5))
155
    G.add_edge(6, 4)
156
    assert_false(nx.is_branching(G))
157
    assert_false(nx.is_arborescence(G))