1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# $Id: test_maximal_independent_set.py 577 2011-03-01 06:07:53Z lleeoo $
"""
Tests for maximal (not maximum) independent sets.
"""
# Copyright (C) 2004-2010 by
# Leo Lopes <leo.lopes@monash.edu>
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__author__ = """Leo Lopes (leo.lopes@monash.edu)"""
from nose.tools import *
import networkx as nx
import random
class TestMaximalIndependantSet(object):
def setup(self):
self.florentine = nx.Graph()
self.florentine.add_edge('Acciaiuoli','Medici')
self.florentine.add_edge('Castellani','Peruzzi')
self.florentine.add_edge('Castellani','Strozzi')
self.florentine.add_edge('Castellani','Barbadori')
self.florentine.add_edge('Medici','Barbadori')
self.florentine.add_edge('Medici','Ridolfi')
self.florentine.add_edge('Medici','Tornabuoni')
self.florentine.add_edge('Medici','Albizzi')
self.florentine.add_edge('Medici','Salviati')
self.florentine.add_edge('Salviati','Pazzi')
self.florentine.add_edge('Peruzzi','Strozzi')
self.florentine.add_edge('Peruzzi','Bischeri')
self.florentine.add_edge('Strozzi','Ridolfi')
self.florentine.add_edge('Strozzi','Bischeri')
self.florentine.add_edge('Ridolfi','Tornabuoni')
self.florentine.add_edge('Tornabuoni','Guadagni')
self.florentine.add_edge('Albizzi','Ginori')
self.florentine.add_edge('Albizzi','Guadagni')
self.florentine.add_edge('Bischeri','Guadagni')
self.florentine.add_edge('Guadagni','Lamberteschi')
def test_K5(self):
"""Maximal independent set: K5"""
G = nx.complete_graph(5)
for node in G:
assert_equal(nx.maximal_independent_set(G, [node]), [node])
def test_K55(self):
"""Maximal independent set: K55"""
G = nx.complete_graph(55)
for node in G:
assert_equal(nx.maximal_independent_set(G, [node]), [node])
def test_exception(self):
"""Bad input should raise exception."""
G = self.florentine
assert_raises(nx.NetworkXUnfeasible,
nx.maximal_independent_set, G, ["Smith"])
assert_raises(nx.NetworkXUnfeasible,
nx.maximal_independent_set, G, ["Salviati", "Pazzi"])
def test_florentine_family(self):
G = self.florentine
indep = nx.maximal_independent_set(G, ["Medici", "Bischeri"])
assert_equal(sorted(indep),
sorted(["Medici", "Bischeri", "Castellani", "Pazzi",
"Ginori", "Lamberteschi"]))
def test_bipartite(self):
G = nx.complete_bipartite_graph(12, 34)
indep = nx.maximal_independent_set(G, [4, 5, 9, 10])
assert_equal(sorted(indep), list(range(12)))
def test_random_graphs(self):
"""Generate 50 random graphs of different types and sizes and
make sure that all sets are independent and maximal."""
for i in range(0, 50, 10):
G = nx.random_graphs.erdos_renyi_graph(i*10+1, random.random())
IS = nx.maximal_independent_set(G)
assert_false(G.subgraph(IS).edges())
neighbors_of_MIS = set.union(*(set(G.neighbors(v)) for v in IS))
for v in set(G.nodes()).difference(IS):
assert_true(v in neighbors_of_MIS)
|
