Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / classes / tests / test_subgraphviews.py @ 5cef0f13

History | View | Annotate | Download (13 KB)

1
from nose.tools import assert_equal, assert_not_equal, \
2
    assert_is, assert_true, assert_raises
3

    
4
import networkx as nx
5

    
6

    
7
class TestSubGraphView(object):
8
    gview = staticmethod(nx.graphviews.SubGraph)
9
    graph = nx.Graph
10
    hide_edges_filter = staticmethod(nx.filters.hide_edges)
11
    show_edges_filter = staticmethod(nx.filters.show_edges)
12

    
13
    def setUp(self):
14
        self.G = nx.path_graph(9, create_using=self.graph())
15
        self.hide_edges_w_hide_nodes = {(3, 4), (4, 5), (5, 6)}
16

    
17
    def test_hidden_nodes(self):
18
        hide_nodes = [4, 5, 111]
19
        nodes_gone = nx.filters.hide_nodes(hide_nodes)
20
        gview = self.gview
21
        print(gview)
22
        G = gview(self.G, filter_node=nodes_gone)
23
        assert_equal(self.G.nodes - G.nodes, {4, 5})
24
        assert_equal(self.G.edges - G.edges, self.hide_edges_w_hide_nodes)
25
        if G.is_directed():
26
            assert_equal(list(G[3]), [])
27
            assert_equal(list(G[2]), [3])
28
        else:
29
            assert_equal(list(G[3]), [2])
30
            assert_equal(set(G[2]), {1, 3})
31
        assert_raises(KeyError, G.__getitem__, 4)
32
        assert_raises(KeyError, G.__getitem__, 112)
33
        assert_raises(KeyError, G.__getitem__, 111)
34
        assert_equal(G.degree(3), 3 if G.is_multigraph() else 1)
35
        assert_equal(G.size(), 7 if G.is_multigraph() else 5)
36

    
37
    def test_hidden_edges(self):
38
        hide_edges = [(2, 3), (8, 7), (222, 223)]
39
        edges_gone = self.hide_edges_filter(hide_edges)
40
        gview = self.gview
41
        G = gview(self.G, filter_edge=edges_gone)
42
        assert_equal(self.G.nodes, G.nodes)
43
        if G.is_directed():
44
            assert_equal(self.G.edges - G.edges, {(2, 3)})
45
            assert_equal(list(G[2]), [])
46
            assert_equal(list(G.pred[3]), [])
47
            assert_equal(list(G.pred[2]), [1])
48
            assert_equal(G.size(), 7)
49
        else:
50
            assert_equal(self.G.edges - G.edges, {(2, 3), (7, 8)})
51
            assert_equal(list(G[2]), [1])
52
            assert_equal(G.size(), 6)
53
        assert_equal(list(G[3]), [4])
54
        assert_raises(KeyError, G.__getitem__, 221)
55
        assert_raises(KeyError, G.__getitem__, 222)
56
        assert_equal(G.degree(3), 1)
57

    
58
    def test_shown_node(self):
59
        induced_subgraph = nx.filters.show_nodes([2, 3, 111])
60
        gview = self.gview
61
        G = gview(self.G, filter_node=induced_subgraph)
62
        assert_equal(set(G.nodes), {2, 3})
63
        if G.is_directed():
64
            assert_equal(list(G[3]), [])
65
        else:
66
            assert_equal(list(G[3]), [2])
67
        assert_equal(list(G[2]), [3])
68
        assert_raises(KeyError, G.__getitem__, 4)
69
        assert_raises(KeyError, G.__getitem__, 112)
70
        assert_raises(KeyError, G.__getitem__, 111)
71
        assert_equal(G.degree(3), 3 if G.is_multigraph() else 1)
72
        assert_equal(G.size(), 3 if G.is_multigraph() else 1)
73

    
74
    def test_shown_edges(self):
75
        show_edges = [(2, 3), (8, 7), (222, 223)]
76
        edge_subgraph = self.show_edges_filter(show_edges)
77
        G = self.gview(self.G, filter_edge=edge_subgraph)
78
        assert_equal(self.G.nodes, G.nodes)
79
        if G.is_directed():
80
            assert_equal(G.edges, {(2, 3)})
81
            assert_equal(list(G[3]), [])
82
            assert_equal(list(G[2]), [3])
83
            assert_equal(list(G.pred[3]), [2])
84
            assert_equal(list(G.pred[2]), [])
85
            assert_equal(G.size(), 1)
86
        else:
87
            assert_equal(G.edges, {(2, 3), (7, 8)})
88
            assert_equal(list(G[3]), [2])
89
            assert_equal(list(G[2]), [3])
90
            assert_equal(G.size(), 2)
91
        assert_raises(KeyError, G.__getitem__, 221)
92
        assert_raises(KeyError, G.__getitem__, 222)
93
        assert_equal(G.degree(3), 1)
94

    
95

    
96
class TestSubDiGraphView(TestSubGraphView):
97
    gview = staticmethod(nx.graphviews.SubDiGraph)
98
    graph = nx.DiGraph
99
    hide_edges_filter = staticmethod(nx.filters.hide_diedges)
100
    show_edges_filter = staticmethod(nx.filters.show_diedges)
101
    hide_edges = [(2, 3), (8, 7), (222, 223)]
102
    excluded = {(2, 3), (3, 4), (4, 5), (5, 6)}
103

    
104
    def test_inoutedges(self):
105
        edges_gone = self.hide_edges_filter(self.hide_edges)
106
        hide_nodes = [4, 5, 111]
107
        nodes_gone = nx.filters.hide_nodes(hide_nodes)
108
        G = self.gview(self.G, nodes_gone, edges_gone)
109

    
110
        assert_equal(self.G.in_edges - G.in_edges, self.excluded)
111
        assert_equal(self.G.out_edges - G.out_edges, self.excluded)
112

    
113
    def test_pred(self):
114
        edges_gone = self.hide_edges_filter(self.hide_edges)
115
        hide_nodes = [4, 5, 111]
116
        nodes_gone = nx.filters.hide_nodes(hide_nodes)
117
        G = self.gview(self.G, nodes_gone, edges_gone)
118

    
119
        assert_equal(list(G.pred[2]), [1])
120
        assert_equal(list(G.pred[6]), [])
121

    
122
    def test_inout_degree(self):
123
        edges_gone = self.hide_edges_filter(self.hide_edges)
124
        hide_nodes = [4, 5, 111]
125
        nodes_gone = nx.filters.hide_nodes(hide_nodes)
126
        G = self.gview(self.G, nodes_gone, edges_gone)
127

    
128
        assert_equal(G.degree(2), 1)
129
        assert_equal(G.out_degree(2), 0)
130
        assert_equal(G.in_degree(2), 1)
131
        assert_equal(G.size(), 4)
132

    
133

    
134
# multigraph
135
class TestMultiGraphView(TestSubGraphView):
136
    gview = staticmethod(nx.graphviews.SubMultiGraph)
137
    graph = nx.MultiGraph
138
    hide_edges_filter = staticmethod(nx.filters.hide_multiedges)
139
    show_edges_filter = staticmethod(nx.filters.show_multiedges)
140

    
141
    def setUp(self):
142
        self.G = nx.path_graph(9, create_using=self.graph())
143
        multiedges = {(2, 3, 4), (2, 3, 5)}
144
        self.G.add_edges_from(multiedges)
145
        self.hide_edges_w_hide_nodes = {(3, 4, 0), (4, 5, 0), (5, 6, 0)}
146

    
147
    def test_hidden_edges(self):
148
        hide_edges = [(2, 3, 4), (2, 3, 3), (8, 7, 0), (222, 223, 0)]
149
        edges_gone = self.hide_edges_filter(hide_edges)
150
        G = self.gview(self.G, filter_edge=edges_gone)
151
        assert_equal(self.G.nodes, G.nodes)
152
        if G.is_directed():
153
            assert_equal(self.G.edges - G.edges, {(2, 3, 4)})
154
            assert_equal(list(G[3]), [4])
155
            assert_equal(list(G[2]), [3])
156
            assert_equal(list(G.pred[3]), [2])  # only one 2 but two edges
157
            assert_equal(list(G.pred[2]), [1])
158
            assert_equal(G.size(), 9)
159
        else:
160
            assert_equal(self.G.edges - G.edges, {(2, 3, 4), (7, 8, 0)})
161
            assert_equal(list(G[3]), [2, 4])
162
            assert_equal(list(G[2]), [1, 3])
163
            assert_equal(G.size(), 8)
164
        assert_equal(G.degree(3), 3)
165
        assert_raises(KeyError, G.__getitem__, 221)
166
        assert_raises(KeyError, G.__getitem__, 222)
167

    
168
    def test_shown_edges(self):
169
        show_edges = [(2, 3, 4), (2, 3, 3), (8, 7, 0), (222, 223, 0)]
170
        edge_subgraph = self.show_edges_filter(show_edges)
171
        G = self.gview(self.G, filter_edge=edge_subgraph)
172
        assert_equal(self.G.nodes, G.nodes)
173
        if G.is_directed():
174
            assert_equal(G.edges, {(2, 3, 4)})
175
            assert_equal(list(G[3]), [])
176
            assert_equal(list(G.pred[3]), [2])
177
            assert_equal(list(G.pred[2]), [])
178
            assert_equal(G.size(), 1)
179
        else:
180
            assert_equal(G.edges, {(2, 3, 4), (7, 8, 0)})
181
            assert_equal(G.size(), 2)
182
            assert_equal(list(G[3]), [2])
183
        assert_equal(G.degree(3), 1)
184
        assert_equal(list(G[2]), [3])
185
        assert_raises(KeyError, G.__getitem__, 221)
186
        assert_raises(KeyError, G.__getitem__, 222)
187

    
188

    
189
# multidigraph
190
class TestMultiDiGraphView(TestMultiGraphView, TestSubDiGraphView):
191
    gview = staticmethod(nx.graphviews.SubMultiDiGraph)
192
    graph = nx.MultiDiGraph
193
    hide_edges_filter = staticmethod(nx.filters.hide_multidiedges)
194
    show_edges_filter = staticmethod(nx.filters.show_multidiedges)
195
    hide_edges = [(2, 3, 0), (8, 7, 0), (222, 223, 0)]
196
    excluded = {(2, 3, 0), (3, 4, 0), (4, 5, 0), (5, 6, 0)}
197

    
198
    def test_inout_degree(self):
199
        edges_gone = self.hide_edges_filter(self.hide_edges)
200
        hide_nodes = [4, 5, 111]
201
        nodes_gone = nx.filters.hide_nodes(hide_nodes)
202
        G = self.gview(self.G, nodes_gone, edges_gone)
203

    
204
        assert_equal(G.degree(2), 3)
205
        assert_equal(G.out_degree(2), 2)
206
        assert_equal(G.in_degree(2), 1)
207
        assert_equal(G.size(), 6)
208

    
209

    
210
# induced_subgraph
211
class TestInducedSubGraph(object):
212
    def setUp(self):
213
        self.K3 = G = nx.complete_graph(3)
214
        G.graph['foo'] = []
215
        G.nodes[0]['foo'] = []
216
        G.remove_edge(1, 2)
217
        ll = []
218
        G.add_edge(1, 2, foo=ll)
219
        G.add_edge(2, 1, foo=ll)
220

    
221
    def test_full_graph(self):
222
        G = self.K3
223
        H = nx.induced_subgraph(G, [0, 1, 2, 5])
224
        assert_equal(H.name, G.name)
225
        self.graphs_equal(H, G)
226
        self.same_attrdict(H, G)
227

    
228
    def test_partial_subgraph(self):
229
        G = self.K3
230
        H = nx.induced_subgraph(G, 0)
231
        assert_equal(dict(H.adj), {0: {}})
232
        assert_not_equal(dict(G.adj), {0: {}})
233

    
234
        H = nx.induced_subgraph(G, [0, 1])
235
        assert_equal(dict(H.adj), {0: {1: {}}, 1: {0: {}}})
236

    
237
    def same_attrdict(self, H, G):
238
        old_foo = H[1][2]['foo']
239
        H.edges[1, 2]['foo'] = 'baz'
240
        assert_equal(G.edges, H.edges)
241
        H.edges[1, 2]['foo'] = old_foo
242
        assert_equal(G.edges, H.edges)
243
        old_foo = H.nodes[0]['foo']
244
        H.nodes[0]['foo'] = 'baz'
245
        assert_equal(G.nodes, H.nodes)
246
        H.nodes[0]['foo'] = old_foo
247
        assert_equal(G.nodes, H.nodes)
248

    
249
    def graphs_equal(self, H, G):
250
        assert_equal(G._adj, H._adj)
251
        assert_equal(G._node, H._node)
252
        assert_equal(G.graph, H.graph)
253
        assert_equal(G.name, H.name)
254
        if not G.is_directed() and not H.is_directed():
255
            assert_true(H._adj[1][2] is H._adj[2][1])
256
            assert_true(G._adj[1][2] is G._adj[2][1])
257
        else:  # at least one is directed
258
            if not G.is_directed():
259
                G._pred = G._adj
260
                G._succ = G._adj
261
            if not H.is_directed():
262
                H._pred = H._adj
263
                H._succ = H._adj
264
            assert_equal(G._pred, H._pred)
265
            assert_equal(G._succ, H._succ)
266
            assert_true(H._succ[1][2] is H._pred[2][1])
267
            assert_true(G._succ[1][2] is G._pred[2][1])
268

    
269

    
270
# edge_subgraph
271
class TestEdgeSubGraph(object):
272
    def setup(self):
273
        # Create a path graph on five nodes.
274
        self.G = G = nx.path_graph(5)
275
        # Add some node, edge, and graph attributes.
276
        for i in range(5):
277
            G.nodes[i]['name'] = 'node{}'.format(i)
278
        G.edges[0, 1]['name'] = 'edge01'
279
        G.edges[3, 4]['name'] = 'edge34'
280
        G.graph['name'] = 'graph'
281
        # Get the subgraph induced by the first and last edges.
282
        self.H = nx.edge_subgraph(G, [(0, 1), (3, 4)])
283

    
284
    def test_correct_nodes(self):
285
        """Tests that the subgraph has the correct nodes."""
286
        assert_equal([0, 1, 3, 4], sorted(self.H.nodes))
287

    
288
    def test_correct_edges(self):
289
        """Tests that the subgraph has the correct edges."""
290
        assert_equal([(0, 1, 'edge01'), (3, 4, 'edge34')],
291
                     sorted(self.H.edges(data='name')))
292

    
293
    def test_add_node(self):
294
        """Tests that adding a node to the original graph does not
295
        affect the nodes of the subgraph.
296

297
        """
298
        self.G.add_node(5)
299
        assert_equal([0, 1, 3, 4], sorted(self.H.nodes))
300
        self.G.remove_node(5)
301

    
302
    def test_remove_node(self):
303
        """Tests that removing a node in the original graph
304
        removes the nodes of the subgraph.
305

306
        """
307
        self.G.remove_node(0)
308
        assert_equal([1, 3, 4], sorted(self.H.nodes))
309
        self.G.add_edge(0, 1)
310

    
311
    def test_node_attr_dict(self):
312
        """Tests that the node attribute dictionary of the two graphs is
313
        the same object.
314

315
        """
316
        for v in self.H:
317
            assert_equal(self.G.nodes[v], self.H.nodes[v])
318
        # Making a change to G should make a change in H and vice versa.
319
        self.G.nodes[0]['name'] = 'foo'
320
        assert_equal(self.G.nodes[0], self.H.nodes[0])
321
        self.H.nodes[1]['name'] = 'bar'
322
        assert_equal(self.G.nodes[1], self.H.nodes[1])
323

    
324
    def test_edge_attr_dict(self):
325
        """Tests that the edge attribute dictionary of the two graphs is
326
        the same object.
327

328
        """
329
        for u, v in self.H.edges():
330
            assert_equal(self.G.edges[u, v], self.H.edges[u, v])
331
        # Making a change to G should make a change in H and vice versa.
332
        self.G.edges[0, 1]['name'] = 'foo'
333
        assert_equal(self.G.edges[0, 1]['name'],
334
                     self.H.edges[0, 1]['name'])
335
        self.H.edges[3, 4]['name'] = 'bar'
336
        assert_equal(self.G.edges[3, 4]['name'],
337
                     self.H.edges[3, 4]['name'])
338

    
339
    def test_graph_attr_dict(self):
340
        """Tests that the graph attribute dictionary of the two graphs
341
        is the same object.
342

343
        """
344
        assert_is(self.G.graph, self.H.graph)
345

    
346
    def test_readonly(self):
347
        """Tests that the subgraph cannot change the graph structure"""
348
        assert_raises(nx.NetworkXError, self.H.add_node, 5)
349
        assert_raises(nx.NetworkXError, self.H.remove_node, 0)
350
        assert_raises(nx.NetworkXError, self.H.add_edge, 5, 6)
351
        assert_raises(nx.NetworkXError, self.H.remove_edge, 0, 1)