Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (3.26 KB)

1
# -*- coding: utf-8 -*-
2
# test_centrality.py - unit tests for algorithms.community.centrality
3
#
4
# Copyright 2015, 2016 NetworkX developers.
5
#
6
# This file is part of NetworkX.
7
#
8
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
9
# information.
10
"""Unit tests for the :mod:`networkx.algorithms.community.centrality`
11
module.
12

13
"""
14
from operator import itemgetter
15

    
16
from nose.tools import assert_equal
17
from nose.tools import assert_true
18

    
19
import networkx as nx
20
from networkx.algorithms.community import girvan_newman
21

    
22

    
23
def set_of_sets(iterable):
24
    return set(map(frozenset, iterable))
25

    
26

    
27
def validate_communities(result, expected):
28
    assert_equal(set_of_sets(result), set_of_sets(expected))
29

    
30

    
31
def validate_possible_communities(result, *expected):
32
    assert_true(any(set_of_sets(result) == set_of_sets(p) for p in expected))
33

    
34

    
35
class TestGirvanNewman(object):
36
    """Unit tests for the
37
    :func:`networkx.algorithms.community.centrality.girvan_newman`
38
    function.
39

40
    """
41

    
42
    def test_no_edges(self):
43
        G = nx.empty_graph(3)
44
        communities = list(girvan_newman(G))
45
        assert_equal(len(communities), 1)
46
        validate_communities(communities[0], [{0}, {1}, {2}])
47

    
48
    def test_undirected(self):
49
        # Start with the graph .-.-.-.
50
        G = nx.path_graph(4)
51
        communities = list(girvan_newman(G))
52
        assert_equal(len(communities), 3)
53
        # After one removal, we get the graph .-. .-.
54
        validate_communities(communities[0], [{0, 1}, {2, 3}])
55
        # After the next, we get the graph .-. . ., but there are two
56
        # symmetric possible versions.
57
        validate_possible_communities(communities[1], [{0}, {1}, {2, 3}],
58
                                      [{0, 1}, {2}, {3}])
59
        # After the last removal, we always get the empty graph.
60
        validate_communities(communities[2], [{0}, {1}, {2}, {3}])
61

    
62
    def test_directed(self):
63
        G = nx.DiGraph(nx.path_graph(4))
64
        communities = list(girvan_newman(G))
65
        assert_equal(len(communities), 3)
66
        validate_communities(communities[0], [{0, 1}, {2, 3}])
67
        validate_possible_communities(communities[1], [{0}, {1}, {2, 3}],
68
                                      [{0, 1}, {2}, {3}])
69
        validate_communities(communities[2], [{0}, {1}, {2}, {3}])
70

    
71
    def test_selfloops(self):
72
        G = nx.path_graph(4)
73
        G.add_edge(0, 0)
74
        G.add_edge(2, 2)
75
        communities = list(girvan_newman(G))
76
        assert_equal(len(communities), 3)
77
        validate_communities(communities[0], [{0, 1}, {2, 3}])
78
        validate_possible_communities(communities[1], [{0}, {1}, {2, 3}],
79
                                      [{0, 1}, {2}, {3}])
80
        validate_communities(communities[2], [{0}, {1}, {2}, {3}])
81

    
82
    def test_most_valuable_edge(self):
83
        G = nx.Graph()
84
        G.add_weighted_edges_from([(0, 1, 3), (1, 2, 2), (2, 3, 1)])
85
        # Let the most valuable edge be the one with the highest weight.
86

    
87
        def heaviest(G): return max(G.edges(data='weight'), key=itemgetter(2))[:2]
88
        communities = list(girvan_newman(G, heaviest))
89
        assert_equal(len(communities), 3)
90
        validate_communities(communities[0], [{0}, {1, 2, 3}])
91
        validate_communities(communities[1], [{0}, {1}, {2, 3}])
92
        validate_communities(communities[2], [{0}, {1}, {2}, {3}])