ioftools / networkxMiCe / networkxmaster / 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) 