Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (9.14 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2018 by
3
#    Rudolf-Andreas Floren <rudi.floren@gmail.com>
4
#    Dominik Meier <dominik.meier@rwth-aachen.de>
5
#    All rights reserved.
6
#    BSD license.
7
import networkx as nx
8
from nose.tools import assert_equals, ok_
9
from networkx.algorithms.approximation import treewidth_min_degree
10
from networkx.algorithms.approximation import treewidth_min_fill_in
11
from networkx.algorithms.approximation.treewidth import min_fill_in_heuristic
12
from networkx.algorithms.approximation.treewidth import MinDegreeHeuristic
13
import itertools
14

    
15

    
16
def is_tree_decomp(graph, decomp):
17
    """Check if the given tree decomposition is valid."""
18
    for x in graph.nodes():
19
        appear_once = False
20
        for bag in decomp.nodes():
21
            if x in bag:
22
                appear_once = True
23
                break
24
        ok_(appear_once)
25

    
26
    # Check if each connected pair of nodes are at least once together in a bag
27
    for (x, y) in graph.edges():
28
        appear_together = False
29
        for bag in decomp.nodes():
30
            if x in bag and y in bag:
31
                appear_together = True
32
                break
33
        ok_(appear_together)
34

    
35
    # Check if the nodes associated with vertex v form a connected subset of T
36
    for v in graph.nodes():
37
        subset = []
38
        for bag in decomp.nodes():
39
            if v in bag:
40
                subset.append(bag)
41
        sub_graph = decomp.subgraph(subset)
42
        ok_(nx.is_connected(sub_graph))
43

    
44

    
45
class TestTreewidthMinDegree(object):
46
    """Unit tests for the min_degree function"""
47
    def setUp(self):
48
        """Setup for different kinds of trees"""
49
        self.complete = nx.Graph()
50
        self.complete.add_edge(1, 2)
51
        self.complete.add_edge(2, 3)
52
        self.complete.add_edge(1, 3)
53

    
54
        self.small_tree = nx.Graph()
55
        self.small_tree.add_edge(1, 3)
56
        self.small_tree.add_edge(4, 3)
57
        self.small_tree.add_edge(2, 3)
58
        self.small_tree.add_edge(3, 5)
59
        self.small_tree.add_edge(5, 6)
60
        self.small_tree.add_edge(5, 7)
61
        self.small_tree.add_edge(6, 7)
62

    
63
        self.deterministic_graph = nx.Graph()
64
        self.deterministic_graph.add_edge(0, 1)  # deg(0) = 1
65

    
66
        self.deterministic_graph.add_edge(1, 2)  # deg(1) = 2
67

    
68
        self.deterministic_graph.add_edge(2, 3)
69
        self.deterministic_graph.add_edge(2, 4)  # deg(2) = 3
70

    
71
        self.deterministic_graph.add_edge(3, 4)
72
        self.deterministic_graph.add_edge(3, 5)
73
        self.deterministic_graph.add_edge(3, 6)  # deg(3) = 4
74

    
75
        self.deterministic_graph.add_edge(4, 5)
76
        self.deterministic_graph.add_edge(4, 6)
77
        self.deterministic_graph.add_edge(4, 7)  # deg(4) = 5
78

    
79
        self.deterministic_graph.add_edge(5, 6)
80
        self.deterministic_graph.add_edge(5, 7)
81
        self.deterministic_graph.add_edge(5, 8)
82
        self.deterministic_graph.add_edge(5, 9)  # deg(5) = 6
83

    
84
        self.deterministic_graph.add_edge(6, 7)
85
        self.deterministic_graph.add_edge(6, 8)
86
        self.deterministic_graph.add_edge(6, 9)  # deg(6) = 6
87

    
88
        self.deterministic_graph.add_edge(7, 8)
89
        self.deterministic_graph.add_edge(7, 9)  # deg(7) = 5
90

    
91
        self.deterministic_graph.add_edge(8, 9)  # deg(8) = 4
92

    
93
    def test_petersen_graph(self):
94
        """Test Petersen graph tree decomposition result"""
95
        G = nx.petersen_graph()
96
        _, decomp = treewidth_min_degree(G)
97
        is_tree_decomp(G, decomp)
98

    
99
    def test_small_tree_treewidth(self):
100
        """Test small tree
101

102
        Test if the computed treewidth of the known self.small_tree is 2.
103
        As we know which value we can expect from our heuristic, values other
104
        than two are regressions
105
        """
106
        G = self.small_tree
107
        # the order of removal should be [1,2,4]3[5,6,7]
108
        # (with [] denoting any order of the containing nodes)
109
        # resulting in treewidth 2 for the heuristic
110
        treewidth, _ = treewidth_min_fill_in(G)
111
        assert_equals(treewidth, 2)
112

    
113
    def test_heuristic_abort(self):
114
        """Test heuristic abort condition for fully connected graph"""
115
        graph = {}
116
        for u in self.complete:
117
            graph[u] = set()
118
            for v in self.complete[u]:
119
                if u != v:  # ignore self-loop
120
                    graph[u].add(v)
121

    
122
        deg_heuristic = MinDegreeHeuristic(graph)
123
        node = deg_heuristic.best_node(graph)
124
        if node is None:
125
            pass
126
        else:
127
            assert False
128

    
129
    def test_empty_graph(self):
130
        """Test empty graph"""
131
        G = nx.Graph()
132
        _, _ = treewidth_min_degree(G)
133

    
134
    def test_two_component_graph(self):
135
        """Test empty graph"""
136
        G = nx.Graph()
137
        G.add_node(1)
138
        G.add_node(2)
139
        treewidth, _ = treewidth_min_degree(G)
140
        assert_equals(treewidth, 0)
141

    
142
    def test_heuristic_first_steps(self):
143
        """Test first steps of min_degree heuristic"""
144
        graph = {n: set(self.deterministic_graph[n]) - set([n])
145
                 for n in self.deterministic_graph}
146
        deg_heuristic = MinDegreeHeuristic(graph)
147
        elim_node = deg_heuristic.best_node(graph)
148
        print("Graph {}:".format(graph))
149
        steps = []
150

    
151
        while elim_node is not None:
152
            print("Removing {}:".format(elim_node))
153
            steps.append(elim_node)
154
            nbrs = graph[elim_node]
155

    
156
            for u, v in itertools.permutations(nbrs, 2):
157
                if v not in graph[u]:
158
                    graph[u].add(v)
159

    
160
            for u in graph:
161
                if elim_node in graph[u]:
162
                    graph[u].remove(elim_node)
163

    
164
            del graph[elim_node]
165
            print("Graph {}:".format(graph))
166
            elim_node = deg_heuristic.best_node(graph)
167

    
168
        # check only the first 5 elements for equality
169
        assert_equals(steps[:5], [0, 1, 2, 3, 4])
170

    
171

    
172
class TestTreewidthMinFillIn(object):
173
    """Unit tests for the treewidth_min_fill_in function."""
174
    def setUp(self):
175
        """Setup for different kinds of trees"""
176
        self.complete = nx.Graph()
177
        self.complete.add_edge(1, 2)
178
        self.complete.add_edge(2, 3)
179
        self.complete.add_edge(1, 3)
180

    
181
        self.small_tree = nx.Graph()
182
        self.small_tree.add_edge(1, 2)
183
        self.small_tree.add_edge(2, 3)
184
        self.small_tree.add_edge(3, 4)
185
        self.small_tree.add_edge(1, 4)
186
        self.small_tree.add_edge(2, 4)
187
        self.small_tree.add_edge(4, 5)
188
        self.small_tree.add_edge(5, 6)
189
        self.small_tree.add_edge(5, 7)
190
        self.small_tree.add_edge(6, 7)
191

    
192
        self.deterministic_graph = nx.Graph()
193
        self.deterministic_graph.add_edge(1, 2)
194
        self.deterministic_graph.add_edge(1, 3)
195
        self.deterministic_graph.add_edge(3, 4)
196
        self.deterministic_graph.add_edge(2, 4)
197
        self.deterministic_graph.add_edge(3, 5)
198
        self.deterministic_graph.add_edge(4, 5)
199
        self.deterministic_graph.add_edge(3, 6)
200
        self.deterministic_graph.add_edge(5, 6)
201

    
202
    def test_petersen_graph(self):
203
        """Test Petersen graph tree decomposition result"""
204
        G = nx.petersen_graph()
205
        _, decomp = treewidth_min_fill_in(G)
206
        is_tree_decomp(G, decomp)
207

    
208
    def test_small_tree_treewidth(self):
209
        """Test if the computed treewidth of the known self.small_tree is 2"""
210
        G = self.small_tree
211
        # the order of removal should be [1,2,4]3[5,6,7]
212
        # (with [] denoting any order of the containing nodes)
213
        # resulting in treewidth 2 for the heuristic
214
        treewidth, _ = treewidth_min_fill_in(G)
215
        assert_equals(treewidth, 2)
216

    
217
    def test_heuristic_abort(self):
218
        """Test if min_fill_in returns None for fully connected graph"""
219
        graph = {}
220
        for u in self.complete:
221
            graph[u] = set()
222
            for v in self.complete[u]:
223
                if u != v:  # ignore self-loop
224
                    graph[u].add(v)
225
        next_node = min_fill_in_heuristic(graph)
226
        if next_node is None:
227
            pass
228
        else:
229
            assert False
230

    
231
    def test_empty_graph(self):
232
        """Test empty graph"""
233
        G = nx.Graph()
234
        _, _ = treewidth_min_fill_in(G)
235

    
236
    def test_two_component_graph(self):
237
        """Test empty graph"""
238
        G = nx.Graph()
239
        G.add_node(1)
240
        G.add_node(2)
241
        treewidth, _ = treewidth_min_fill_in(G)
242
        assert_equals(treewidth, 0)
243

    
244
    def test_heuristic_first_steps(self):
245
        """Test first steps of min_fill_in heuristic"""
246
        graph = {n: set(self.deterministic_graph[n]) - set([n])
247
                 for n in self.deterministic_graph}
248
        print("Graph {}:".format(graph))
249
        elim_node = min_fill_in_heuristic(graph)
250
        steps = []
251

    
252
        while elim_node is not None:
253
            print("Removing {}:".format(elim_node))
254
            steps.append(elim_node)
255
            nbrs = graph[elim_node]
256

    
257
            for u, v in itertools.permutations(nbrs, 2):
258
                if v not in graph[u]:
259
                    graph[u].add(v)
260

    
261
            for u in graph:
262
                if elim_node in graph[u]:
263
                    graph[u].remove(elim_node)
264

    
265
            del graph[elim_node]
266
            print("Graph {}:".format(graph))
267
            elim_node = min_fill_in_heuristic(graph)
268

    
269
        # check only the first 2 elements for equality
270
        assert_equals(steps[:2], [6, 5])