Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (3.77 KB)

1
#!/usr/bin/env python
2
# -*- coding: utf-8 -*-
3
# $Id: test_maximal_independent_set.py 577 2011-03-01 06:07:53Z lleeoo $
4
#    Copyright (C) 2004-2019 by
5
#    Leo Lopes <leo.lopes@monash.edu>
6
#    Aric Hagberg <hagberg@lanl.gov>
7
#    Dan Schult <dschult@colgate.edu>
8
#    Pieter Swart <swart@lanl.gov>
9
#    All rights reserved.
10
#    BSD license.
11
#
12
# Author: Leo Lopes <leo.lopes@monash.edu>
13
"""
14
Tests for maximal (not maximum) independent sets.
15

16
"""
17

    
18
from nose.tools import *
19
import networkx as nx
20
import random
21

    
22

    
23
class TestMaximalIndependantSet(object):
24
    def setup(self):
25
        self.florentine = nx.Graph()
26
        self.florentine.add_edge('Acciaiuoli', 'Medici')
27
        self.florentine.add_edge('Castellani', 'Peruzzi')
28
        self.florentine.add_edge('Castellani', 'Strozzi')
29
        self.florentine.add_edge('Castellani', 'Barbadori')
30
        self.florentine.add_edge('Medici', 'Barbadori')
31
        self.florentine.add_edge('Medici', 'Ridolfi')
32
        self.florentine.add_edge('Medici', 'Tornabuoni')
33
        self.florentine.add_edge('Medici', 'Albizzi')
34
        self.florentine.add_edge('Medici', 'Salviati')
35
        self.florentine.add_edge('Salviati', 'Pazzi')
36
        self.florentine.add_edge('Peruzzi', 'Strozzi')
37
        self.florentine.add_edge('Peruzzi', 'Bischeri')
38
        self.florentine.add_edge('Strozzi', 'Ridolfi')
39
        self.florentine.add_edge('Strozzi', 'Bischeri')
40
        self.florentine.add_edge('Ridolfi', 'Tornabuoni')
41
        self.florentine.add_edge('Tornabuoni', 'Guadagni')
42
        self.florentine.add_edge('Albizzi', 'Ginori')
43
        self.florentine.add_edge('Albizzi', 'Guadagni')
44
        self.florentine.add_edge('Bischeri', 'Guadagni')
45
        self.florentine.add_edge('Guadagni', 'Lamberteschi')
46

    
47
    def test_random_seed(self):
48
        G = nx.complete_graph(5)
49
        for node in G:
50
            assert_equal(nx.maximal_independent_set(G, [node], seed=1), [node])
51

    
52
    def test_K5(self):
53
        """Maximal independent set: K5"""
54
        G = nx.complete_graph(5)
55
        for node in G:
56
            assert_equal(nx.maximal_independent_set(G, [node]), [node])
57

    
58
    def test_K55(self):
59
        """Maximal independent set: K55"""
60
        G = nx.complete_graph(55)
61
        for node in G:
62
            assert_equal(nx.maximal_independent_set(G, [node]), [node])
63

    
64
    def test_exception(self):
65
        """Bad input should raise exception."""
66
        G = self.florentine
67
        assert_raises(nx.NetworkXUnfeasible,
68
                      nx.maximal_independent_set, G, ["Smith"])
69
        assert_raises(nx.NetworkXUnfeasible,
70
                      nx.maximal_independent_set, G, ["Salviati", "Pazzi"])
71

    
72
    def test_digraph_exception(self):
73
        G = nx.DiGraph([(1, 2), (3, 4)])
74
        assert_raises(nx.NetworkXNotImplemented, nx.maximal_independent_set, G)
75

    
76
    def test_florentine_family(self):
77
        G = self.florentine
78
        indep = nx.maximal_independent_set(G, ["Medici", "Bischeri"])
79
        assert_equal(sorted(indep),
80
                     sorted(["Medici", "Bischeri", "Castellani", "Pazzi",
81
                             "Ginori", "Lamberteschi"]))
82

    
83
    def test_bipartite(self):
84
        G = nx.complete_bipartite_graph(12, 34)
85
        indep = nx.maximal_independent_set(G, [4, 5, 9, 10])
86
        assert_equal(sorted(indep), list(range(12)))
87

    
88
    def test_random_graphs(self):
89
        """Generate 50 random graphs of different types and sizes and
90
        make sure that all sets are independent and maximal."""
91
        for i in range(0, 50, 10):
92
            G = nx.random_graphs.erdos_renyi_graph(i * 10 + 1, random.random())
93
            IS = nx.maximal_independent_set(G)
94
            assert_false(list(G.subgraph(IS).edges()))
95
            neighbors_of_MIS = set.union(*(set(G.neighbors(v)) for v in IS))
96
            for v in set(G.nodes()).difference(IS):
97
                assert_true(v in neighbors_of_MIS)