Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (9.46 KB)

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

    
4

    
5
class TestImmediateDominators(object):
6

    
7
    def test_exceptions(self):
8
        G = nx.Graph()
9
        G.add_node(0)
10
        assert_raises(nx.NetworkXNotImplemented, nx.immediate_dominators, G, 0)
11
        G = nx.MultiGraph(G)
12
        assert_raises(nx.NetworkXNotImplemented, nx.immediate_dominators, G, 0)
13
        G = nx.DiGraph([[0, 0]])
14
        assert_raises(nx.NetworkXError, nx.immediate_dominators, G, 1)
15

    
16
    def test_singleton(self):
17
        G = nx.DiGraph()
18
        G.add_node(0)
19
        assert_equal(nx.immediate_dominators(G, 0), {0: 0})
20
        G.add_edge(0, 0)
21
        assert_equal(nx.immediate_dominators(G, 0), {0: 0})
22

    
23
    def test_path(self):
24
        n = 5
25
        G = nx.path_graph(n, create_using=nx.DiGraph())
26
        assert_equal(nx.immediate_dominators(G, 0),
27
                     {i: max(i - 1, 0) for i in range(n)})
28

    
29
    def test_cycle(self):
30
        n = 5
31
        G = nx.cycle_graph(n, create_using=nx.DiGraph())
32
        assert_equal(nx.immediate_dominators(G, 0),
33
                     {i: max(i - 1, 0) for i in range(n)})
34

    
35
    def test_unreachable(self):
36
        n = 5
37
        assert_greater(n, 1)
38
        G = nx.path_graph(n, create_using=nx.DiGraph())
39
        assert_equal(nx.immediate_dominators(G, n // 2),
40
                     {i: max(i - 1, n // 2) for i in range(n // 2, n)})
41

    
42
    def test_irreducible1(self):
43
        # Graph taken from Figure 2 of
44
        # K. D. Cooper, T. J. Harvey, and K. Kennedy.
45
        # A simple, fast dominance algorithm.
46
        # Software Practice & Experience, 4:110, 2001.
47
        edges = [(1, 2), (2, 1), (3, 2), (4, 1), (5, 3), (5, 4)]
48
        G = nx.DiGraph(edges)
49
        assert_equal(nx.immediate_dominators(G, 5),
50
                     {i: 5 for i in range(1, 6)})
51

    
52
    def test_irreducible2(self):
53
        # Graph taken from Figure 4 of
54
        # K. D. Cooper, T. J. Harvey, and K. Kennedy.
55
        # A simple, fast dominance algorithm.
56
        # Software Practice & Experience, 4:110, 2001.
57
        edges = [(1, 2), (2, 1), (2, 3), (3, 2), (4, 2), (4, 3), (5, 1),
58
                 (6, 4), (6, 5)]
59
        G = nx.DiGraph(edges)
60
        assert_equal(nx.immediate_dominators(G, 6),
61
                     {i: 6 for i in range(1, 7)})
62

    
63
    def test_domrel_png(self):
64
        # Graph taken from https://commons.wikipedia.org/wiki/File:Domrel.png
65
        edges = [(1, 2), (2, 3), (2, 4), (2, 6), (3, 5), (4, 5), (5, 2)]
66
        G = nx.DiGraph(edges)
67
        assert_equal(nx.immediate_dominators(G, 1),
68
                     {1: 1, 2: 1, 3: 2, 4: 2, 5: 2, 6: 2})
69
        # Test postdominance.
70
        with nx.utils.reversed(G):
71
            assert_equal(nx.immediate_dominators(G, 6),
72
                         {1: 2, 2: 6, 3: 5, 4: 5, 5: 2, 6: 6})
73

    
74
    def test_boost_example(self):
75
        # Graph taken from Figure 1 of
76
        # http://www.boost.org/doc/libs/1_56_0/libs/graph/doc/lengauer_tarjan_dominator.htm
77
        edges = [(0, 1), (1, 2), (1, 3), (2, 7), (3, 4), (4, 5), (4, 6),
78
                 (5, 7), (6, 4)]
79
        G = nx.DiGraph(edges)
80
        assert_equal(nx.immediate_dominators(G, 0),
81
                     {0: 0, 1: 0, 2: 1, 3: 1, 4: 3, 5: 4, 6: 4, 7: 1})
82
        # Test postdominance.
83
        with nx.utils.reversed(G):
84
            assert_equal(nx.immediate_dominators(G, 7),
85
                         {0: 1, 1: 7, 2: 7, 3: 4, 4: 5, 5: 7, 6: 4, 7: 7})
86

    
87

    
88
class TestDominanceFrontiers(object):
89

    
90
    def test_exceptions(self):
91
        G = nx.Graph()
92
        G.add_node(0)
93
        assert_raises(nx.NetworkXNotImplemented, nx.dominance_frontiers, G, 0)
94
        G = nx.MultiGraph(G)
95
        assert_raises(nx.NetworkXNotImplemented, nx.dominance_frontiers, G, 0)
96
        G = nx.DiGraph([[0, 0]])
97
        assert_raises(nx.NetworkXError, nx.dominance_frontiers, G, 1)
98

    
99
    def test_singleton(self):
100
        G = nx.DiGraph()
101
        G.add_node(0)
102
        assert_equal(nx.dominance_frontiers(G, 0), {0: set()})
103
        G.add_edge(0, 0)
104
        assert_equal(nx.dominance_frontiers(G, 0), {0: set()})
105

    
106
    def test_path(self):
107
        n = 5
108
        G = nx.path_graph(n, create_using=nx.DiGraph())
109
        assert_equal(nx.dominance_frontiers(G, 0),
110
                     {i: set() for i in range(n)})
111

    
112
    def test_cycle(self):
113
        n = 5
114
        G = nx.cycle_graph(n, create_using=nx.DiGraph())
115
        assert_equal(nx.dominance_frontiers(G, 0),
116
                     {i: set() for i in range(n)})
117

    
118
    def test_unreachable(self):
119
        n = 5
120
        assert_greater(n, 1)
121
        G = nx.path_graph(n, create_using=nx.DiGraph())
122
        assert_equal(nx.dominance_frontiers(G, n // 2),
123
                     {i: set() for i in range(n // 2, n)})
124

    
125
    def test_irreducible1(self):
126
        # Graph taken from Figure 2 of
127
        # K. D. Cooper, T. J. Harvey, and K. Kennedy.
128
        # A simple, fast dominance algorithm.
129
        # Software Practice & Experience, 4:110, 2001.
130
        edges = [(1, 2), (2, 1), (3, 2), (4, 1), (5, 3), (5, 4)]
131
        G = nx.DiGraph(edges)
132
        assert_equal({u: df
133
                      for u, df in nx.dominance_frontiers(G, 5).items()},
134
                     {1: set([2]), 2: set([1]), 3: set([2]),
135
                      4: set([1]), 5: set()})
136

    
137
    def test_irreducible2(self):
138
        # Graph taken from Figure 4 of
139
        # K. D. Cooper, T. J. Harvey, and K. Kennedy.
140
        # A simple, fast dominance algorithm.
141
        # Software Practice & Experience, 4:110, 2001.
142
        edges = [(1, 2), (2, 1), (2, 3), (3, 2), (4, 2), (4, 3), (5, 1),
143
                 (6, 4), (6, 5)]
144
        G = nx.DiGraph(edges)
145
        assert_equal(nx.dominance_frontiers(G, 6),
146
                     {1: set([2]), 2: set([1, 3]), 3: set([2]), 4: set([2, 3]), 5: set([1]), 6: set([])})
147

    
148
    def test_domrel_png(self):
149
        # Graph taken from https://commons.wikipedia.org/wiki/File:Domrel.png
150
        edges = [(1, 2), (2, 3), (2, 4), (2, 6), (3, 5), (4, 5), (5, 2)]
151
        G = nx.DiGraph(edges)
152
        assert_equal(nx.dominance_frontiers(G, 1),
153
                     {1: set([]), 2: set([2]), 3: set([5]), 4: set([5]),
154
                      5: set([2]), 6: set()})
155
        # Test postdominance.
156
        with nx.utils.reversed(G):
157
            assert_equal(nx.dominance_frontiers(G, 6),
158
                         {1: set(), 2: set([2]), 3: set([2]), 4: set([2]),
159
                          5: set([2]), 6: set()})
160

    
161
    def test_boost_example(self):
162
        # Graph taken from Figure 1 of
163
        # http://www.boost.org/doc/libs/1_56_0/libs/graph/doc/lengauer_tarjan_dominator.htm
164
        edges = [(0, 1), (1, 2), (1, 3), (2, 7), (3, 4), (4, 5), (4, 6),
165
                 (5, 7), (6, 4)]
166
        G = nx.DiGraph(edges)
167
        assert_equal(nx.dominance_frontiers(G, 0),
168
                     {0: set(), 1: set(), 2: set([7]), 3: set([7]),
169
                      4: set([4, 7]), 5: set([7]), 6: set([4]), 7: set()})
170
        # Test postdominance.
171
        with nx.utils.reversed(G):
172
            assert_equal(nx.dominance_frontiers(G, 7),
173
                         {0: set(), 1: set(), 2: set([1]), 3: set([1]),
174
                          4: set([1, 4]), 5: set([1]), 6: set([4]), 7: set()})
175

    
176
    def test_discard_issue(self):
177
        # https://github.com/networkx/networkx/issues/2071
178
        g = nx.DiGraph()
179
        g.add_edges_from([
180
            ('b0', 'b1'),
181
            ('b1', 'b2'),
182
            ('b2', 'b3'),
183
            ('b3', 'b1'),
184
            ('b1', 'b5'),
185
            ('b5', 'b6'),
186
            ('b5', 'b8'),
187
            ('b6', 'b7'),
188
            ('b8', 'b7'),
189
            ('b7', 'b3'),
190
            ('b3', 'b4')
191
        ]
192
        )
193
        df = nx.dominance_frontiers(g, 'b0')
194
        assert_equal(df, {'b4': set(), 'b5': set(['b3']), 'b6': set(['b7']),
195
                          'b7': set(['b3']),
196
                          'b0': set(), 'b1': set(['b1']), 'b2': set(['b3']),
197
                          'b3': set(['b1']), 'b8': set(['b7'])})
198

    
199
    def test_loop(self):
200
        g = nx.DiGraph()
201
        g.add_edges_from([('a', 'b'), ('b', 'c'), ('b', 'a')])
202
        df = nx.dominance_frontiers(g, 'a')
203
        assert_equal(df, {'a': set(), 'b': set(), 'c': set()})
204

    
205
    def test_missing_immediate_doms(self):
206
        # see https://github.com/networkx/networkx/issues/2070
207
        g = nx.DiGraph()
208
        edges = [
209
            ('entry_1', 'b1'),
210
            ('b1', 'b2'),
211
            ('b2', 'b3'),
212
            ('b3', 'exit'),
213
            ('entry_2', 'b3')
214
        ]
215

    
216
        # entry_1
217
        #   |
218
        #   b1
219
        #   |
220
        #   b2  entry_2
221
        #    |  /
222
        #    b3
223
        #    |
224
        #   exit
225

    
226
        g.add_edges_from(edges)
227
        # formerly raised KeyError on entry_2 when parsing b3
228
        # because entry_2 does not have immediate doms (no path)
229
        nx.dominance_frontiers(g, 'entry_1')
230

    
231
    def test_loops_larger(self):
232
        # from
233
        # http://ecee.colorado.edu/~waite/Darmstadt/motion.html
234
        g = nx.DiGraph()
235
        edges = [
236
            ('entry', 'exit'),
237
            ('entry', '1'),
238
            ('1', '2'),
239
            ('2', '3'),
240
            ('3', '4'),
241
            ('4', '5'),
242
            ('5', '6'),
243
            ('6', 'exit'),
244
            ('6', '2'),
245
            ('5', '3'),
246
            ('4', '4')
247
        ]
248

    
249
        g.add_edges_from(edges)
250
        df = nx.dominance_frontiers(g, 'entry')
251
        answer = {'entry': set(),
252
                  '1': set(['exit']),
253
                  '2': set(['exit', '2']),
254
                  '3': set(['exit', '3', '2']),
255
                  '4': set(['exit', '4', '3', '2']),
256
                  '5': set(['exit', '3', '2']),
257
                  '6': set(['exit', '2']),
258
                  'exit': set()}
259
        for n in df:
260
            assert_equal(set(df[n]), set(answer[n]))