ioftools / networkxMiCe / networkxmaster / networkx / algorithms / tests / test_cuts.py @ 5cef0f13
History  View  Annotate  Download (5.11 KB)
1 
# test_cuts.py  unit tests for the cuts 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.cuts` module."""

10 
from __future__ import division 
11  
12 
from nose.tools import assert_equal 
13  
14 
import networkx as nx 
15  
16  
17 
class TestCutSize(object): 
18 
"""Unit tests for the :func:`~networkx.cut_size` function."""

19  
20 
def test_symmetric(self): 
21 
"""Tests that the cut size is symmetric."""

22 
G = nx.barbell_graph(3, 0) 
23 
S = {0, 1, 4} 
24 
T = {2, 3, 5} 
25 
assert_equal(nx.cut_size(G, S, T), 4)

26 
assert_equal(nx.cut_size(G, T, S), 4)

27  
28 
def test_single_edge(self): 
29 
"""Tests for a cut of a single edge."""

30 
G = nx.barbell_graph(3, 0) 
31 
S = {0, 1, 2} 
32 
T = {3, 4, 5} 
33 
assert_equal(nx.cut_size(G, S, T), 1)

34 
assert_equal(nx.cut_size(G, T, S), 1)

35  
36 
def test_directed(self): 
37 
"""Tests that each directed edge is counted once in the cut."""

38 
G = nx.barbell_graph(3, 0).to_directed() 
39 
S = {0, 1, 2} 
40 
T = {3, 4, 5} 
41 
assert_equal(nx.cut_size(G, S, T), 2)

42 
assert_equal(nx.cut_size(G, T, S), 2)

43  
44 
def test_directed_symmetric(self): 
45 
"""Tests that a cut in a directed graph is symmetric."""

46 
G = nx.barbell_graph(3, 0).to_directed() 
47 
S = {0, 1, 4} 
48 
T = {2, 3, 5} 
49 
assert_equal(nx.cut_size(G, S, T), 8)

50 
assert_equal(nx.cut_size(G, T, S), 8)

51  
52 
def test_multigraph(self): 
53 
"""Tests that parallel edges are each counted for a cut."""

54 
G = nx.MultiGraph(['ab', 'ab']) 
55 
assert_equal(nx.cut_size(G, {'a'}, {'b'}), 2) 
56  
57  
58 
class TestVolume(object): 
59 
"""Unit tests for the :func:`~networkx.volume` function."""

60  
61 
def test_graph(self): 
62 
G = nx.cycle_graph(4)

63 
assert_equal(nx.volume(G, {0, 1}), 4) 
64  
65 
def test_digraph(self): 
66 
G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 0)]) 
67 
assert_equal(nx.volume(G, {0, 1}), 2) 
68  
69 
def test_multigraph(self): 
70 
edges = list(nx.cycle_graph(4).edges()) 
71 
G = nx.MultiGraph(edges * 2)

72 
assert_equal(nx.volume(G, {0, 1}), 8) 
73  
74 
def test_multidigraph(self): 
75 
edges = [(0, 1), (1, 2), (2, 3), (3, 0)] 
76 
G = nx.MultiDiGraph(edges * 2)

77 
assert_equal(nx.volume(G, {0, 1}), 4) 
78  
79  
80 
class TestNormalizedCutSize(object): 
81 
"""Unit tests for the :func:`~networkx.normalized_cut_size`

82 
function.

83 

84 
"""

85  
86 
def test_graph(self): 
87 
G = nx.path_graph(4)

88 
S = {1, 2} 
89 
T = set(G)  S

90 
size = nx.normalized_cut_size(G, S, T) 
91 
# The cut looks like this: o{oo}o

92 
expected = 2 * ((1 / 4) + (1 / 2)) 
93 
assert_equal(expected, size) 
94  
95 
def test_directed(self): 
96 
G = nx.DiGraph([(0, 1), (1, 2), (2, 3)]) 
97 
S = {1, 2} 
98 
T = set(G)  S

99 
size = nx.normalized_cut_size(G, S, T) 
100 
# The cut looks like this: o{>o>o}>o

101 
expected = 2 * ((1 / 2) + (1 / 1)) 
102 
assert_equal(expected, size) 
103  
104  
105 
class TestConductance(object): 
106 
"""Unit tests for the :func:`~networkx.conductance` function."""

107  
108 
def test_graph(self): 
109 
G = nx.barbell_graph(5, 0) 
110 
# Consider the singleton sets containing the "bridge" nodes.

111 
# There is only one cut edge, and each set has volume five.

112 
S = {4}

113 
T = {5}

114 
conductance = nx.conductance(G, S, T) 
115 
expected = 1 / 5 
116 
assert_equal(expected, conductance) 
117  
118  
119 
class TestEdgeExpansion(object): 
120 
"""Unit tests for the :func:`~networkx.edge_expansion` function."""

121  
122 
def test_graph(self): 
123 
G = nx.barbell_graph(5, 0) 
124 
S = set(range(5)) 
125 
T = set(G)  S

126 
expansion = nx.edge_expansion(G, S, T) 
127 
expected = 1 / 5 
128 
assert_equal(expected, expansion) 
129  
130  
131 
class TestNodeExpansion(object): 
132 
"""Unit tests for the :func:`~networkx.node_expansion` function.

133 

134 
"""

135  
136 
def test_graph(self): 
137 
G = nx.path_graph(8)

138 
S = {3, 4, 5} 
139 
expansion = nx.node_expansion(G, S) 
140 
# The neighborhood of S has cardinality five, and S has

141 
# cardinality three.

142 
expected = 5 / 3 
143 
assert_equal(expected, expansion) 
144  
145  
146 
class TestBoundaryExpansion(object): 
147 
"""Unit tests for the :func:`~networkx.boundary_expansion` function.

148 

149 
"""

150  
151 
def test_graph(self): 
152 
G = nx.complete_graph(10)

153 
S = set(range(4)) 
154 
expansion = nx.boundary_expansion(G, S) 
155 
# The node boundary of S has cardinality six, and S has

156 
# cardinality three.

157 
expected = 6 / 4 
158 
assert_equal(expected, expansion) 
159  
160  
161 
class TestMixingExpansion(object): 
162 
"""Unit tests for the :func:`~networkx.mixing_expansion` function.

163 

164 
"""

165  
166 
def test_graph(self): 
167 
G = nx.barbell_graph(5, 0) 
168 
S = set(range(5)) 
169 
T = set(G)  S

170 
expansion = nx.mixing_expansion(G, S, T) 
171 
# There is one cut edge, and the total number of edges in the

172 
# graph is twice the total number of edges in a clique of size

173 
# five, plus one more for the bridge.

174 
expected = 1 / (2 * (5 * 4 + 1)) 
175 
assert_equal(expected, expansion) 