Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (6.7 KB)

1
# test_boundary.py - unit tests for the boundary module
2
#
3
# Copyright 2015 NetworkX developers.
4
#
5
# This file is part of NetworkX.
6
#
7
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
8
# information.
9
"""Unit tests for the :mod:`networkx.algorithms.boundary` module."""
10
from __future__ import division
11

    
12
from itertools import combinations
13

    
14
from nose.tools import assert_almost_equals
15
from nose.tools import assert_equal
16

    
17
import networkx as nx
18
from networkx.testing.utils import *
19
from networkx import convert_node_labels_to_integers as cnlti
20

    
21

    
22
class TestNodeBoundary(object):
23
    """Unit tests for the :func:`~networkx.node_boundary` function."""
24

    
25
    def test_null_graph(self):
26
        """Tests that the null graph has empty node boundaries."""
27
        null = nx.null_graph()
28
        assert_equal(nx.node_boundary(null, []), set())
29
        assert_equal(nx.node_boundary(null, [], []), set())
30
        assert_equal(nx.node_boundary(null, [1, 2, 3]), set())
31
        assert_equal(nx.node_boundary(null, [1, 2, 3], [4, 5, 6]), set())
32
        assert_equal(nx.node_boundary(null, [1, 2, 3], [3, 4, 5]), set())
33

    
34
    def test_path_graph(self):
35
        P10 = cnlti(nx.path_graph(10), first_label=1)
36
        assert_equal(nx.node_boundary(P10, []), set())
37
        assert_equal(nx.node_boundary(P10, [], []), set())
38
        assert_equal(nx.node_boundary(P10, [1, 2, 3]), {4})
39
        assert_equal(nx.node_boundary(P10, [4, 5, 6]), {3, 7})
40
        assert_equal(nx.node_boundary(P10, [3, 4, 5, 6, 7]), {2, 8})
41
        assert_equal(nx.node_boundary(P10, [8, 9, 10]), {7})
42
        assert_equal(nx.node_boundary(P10, [4, 5, 6], [9, 10]), set())
43

    
44
    def test_complete_graph(self):
45
        K10 = cnlti(nx.complete_graph(10), first_label=1)
46
        assert_equal(nx.node_boundary(K10, []), set())
47
        assert_equal(nx.node_boundary(K10, [], []), set())
48
        assert_equal(nx.node_boundary(K10, [1, 2, 3]), {4, 5, 6, 7, 8, 9, 10})
49
        assert_equal(nx.node_boundary(K10, [4, 5, 6]), {1, 2, 3, 7, 8, 9, 10})
50
        assert_equal(nx.node_boundary(K10, [3, 4, 5, 6, 7]), {1, 2, 8, 9, 10})
51
        assert_equal(nx.node_boundary(K10, [4, 5, 6], []), set())
52
        assert_equal(nx.node_boundary(K10, K10), set())
53
        assert_equal(nx.node_boundary(K10, [1, 2, 3], [3, 4, 5]), {4, 5})
54

    
55
    def test_petersen(self):
56
        """Check boundaries in the petersen graph
57

58
        cheeger(G,k)=min(|bdy(S)|/|S| for |S|=k, 0<k<=|V(G)|/2)
59

60
        """
61

    
62
        def cheeger(G, k):
63
            return min(len(nx.node_boundary(G, nn)) / k
64
                       for nn in combinations(G, k))
65

    
66
        P = nx.petersen_graph()
67
        assert_almost_equals(cheeger(P, 1), 3.00, places=2)
68
        assert_almost_equals(cheeger(P, 2), 2.00, places=2)
69
        assert_almost_equals(cheeger(P, 3), 1.67, places=2)
70
        assert_almost_equals(cheeger(P, 4), 1.00, places=2)
71
        assert_almost_equals(cheeger(P, 5), 0.80, places=2)
72

    
73
    def test_directed(self):
74
        """Tests the node boundary of a directed graph."""
75
        G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)])
76
        S = {0, 1}
77
        boundary = nx.node_boundary(G, S)
78
        expected = {2}
79
        assert_equal(boundary, expected)
80

    
81
    def test_multigraph(self):
82
        """Tests the node boundary of a multigraph."""
83
        G = nx.MultiGraph(list(nx.cycle_graph(5).edges()) * 2)
84
        S = {0, 1}
85
        boundary = nx.node_boundary(G, S)
86
        expected = {2, 4}
87
        assert_equal(boundary, expected)
88

    
89
    def test_multidigraph(self):
90
        """Tests the edge boundary of a multdiigraph."""
91
        edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
92
        G = nx.MultiDiGraph(edges * 2)
93
        S = {0, 1}
94
        boundary = nx.node_boundary(G, S)
95
        expected = {2}
96
        assert_equal(boundary, expected)
97

    
98

    
99
class TestEdgeBoundary(object):
100
    """Unit tests for the :func:`~networkx.edge_boundary` function."""
101

    
102
    def test_null_graph(self):
103
        null = nx.null_graph()
104
        assert_equal(list(nx.edge_boundary(null, [])), [])
105
        assert_equal(list(nx.edge_boundary(null, [], [])), [])
106
        assert_equal(list(nx.edge_boundary(null, [1, 2, 3])), [])
107
        assert_equal(list(nx.edge_boundary(null, [1, 2, 3], [4, 5, 6])), [])
108
        assert_equal(list(nx.edge_boundary(null, [1, 2, 3], [3, 4, 5])), [])
109

    
110
    def test_path_graph(self):
111
        P10 = cnlti(nx.path_graph(10), first_label=1)
112
        assert_equal(list(nx.edge_boundary(P10, [])), [])
113
        assert_equal(list(nx.edge_boundary(P10, [], [])), [])
114
        assert_equal(list(nx.edge_boundary(P10, [1, 2, 3])), [(3, 4)])
115
        assert_equal(sorted(nx.edge_boundary(P10, [4, 5, 6])),
116
                     [(4, 3), (6, 7)])
117
        assert_equal(sorted(nx.edge_boundary(P10, [3, 4, 5, 6, 7])),
118
                     [(3, 2), (7, 8)])
119
        assert_equal(list(nx.edge_boundary(P10, [8, 9, 10])), [(8, 7)])
120
        assert_equal(sorted(nx.edge_boundary(P10, [4, 5, 6], [9, 10])), [])
121
        assert_equal(list(nx.edge_boundary(P10, [1, 2, 3], [3, 4, 5])),
122
                     [(2, 3), (3, 4)])
123

    
124
    def test_complete_graph(self):
125
        K10 = cnlti(nx.complete_graph(10), first_label=1)
126

    
127
        def ilen(iterable): return sum(1 for i in iterable)
128
        assert_equal(list(nx.edge_boundary(K10, [])), [])
129
        assert_equal(list(nx.edge_boundary(K10, [], [])), [])
130
        assert_equal(ilen(nx.edge_boundary(K10, [1, 2, 3])), 21)
131
        assert_equal(ilen(nx.edge_boundary(K10, [4, 5, 6, 7])), 24)
132
        assert_equal(ilen(nx.edge_boundary(K10, [3, 4, 5, 6, 7])), 25)
133
        assert_equal(ilen(nx.edge_boundary(K10, [8, 9, 10])), 21)
134
        assert_edges_equal(nx.edge_boundary(K10, [4, 5, 6], [9, 10]),
135
                           [(4, 9), (4, 10), (5, 9), (5, 10), (6, 9), (6, 10)])
136
        assert_edges_equal(nx.edge_boundary(K10, [1, 2, 3], [3, 4, 5]),
137
                           [(1, 3), (1, 4), (1, 5), (2, 3), (2, 4),
138
                            (2, 5), (3, 4), (3, 5)])
139

    
140
    def test_directed(self):
141
        """Tests the edge boundary of a directed graph."""
142
        G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)])
143
        S = {0, 1}
144
        boundary = list(nx.edge_boundary(G, S))
145
        expected = [(1, 2)]
146
        assert_equal(boundary, expected)
147

    
148
    def test_multigraph(self):
149
        """Tests the edge boundary of a multigraph."""
150
        G = nx.MultiGraph(list(nx.cycle_graph(5).edges()) * 2)
151
        S = {0, 1}
152
        boundary = list(nx.edge_boundary(G, S))
153
        expected = [(0, 4), (0, 4), (1, 2), (1, 2)]
154
        assert_equal(boundary, expected)
155

    
156
    def test_multidigraph(self):
157
        """Tests the edge boundary of a multdiigraph."""
158
        edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
159
        G = nx.MultiDiGraph(edges * 2)
160
        S = {0, 1}
161
        boundary = list(nx.edge_boundary(G, S))
162
        expected = [(1, 2), (1, 2)]
163
        assert_equal(boundary, expected)