Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / 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-{-o--o-}-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)