lib/python2.7/site-packages/setoolsgui/networkx/algorithms/centrality/tests/test_betweenness_centrality.py

#!/usr/bin/env python
from nose.tools import *
import networkx as nx

def weighted_G():
    G=nx.Graph();
    G.add_edge(0,1,weight=3)
    G.add_edge(0,2,weight=2)
    G.add_edge(0,3,weight=6)
    G.add_edge(0,4,weight=4)
    G.add_edge(1,3,weight=5)
    G.add_edge(1,5,weight=5)
    G.add_edge(2,4,weight=1)
    G.add_edge(3,4,weight=2)
    G.add_edge(3,5,weight=1)
    G.add_edge(4,5,weight=4)

    return G


class TestBetweennessCentrality(object):
        
    def test_K5(self):
        """Betweenness centrality: K5"""
        G=nx.complete_graph(5)
        b=nx.betweenness_centrality(G,
                                             weight=None,
                                             normalized=False)
        b_answer={0: 0.0, 1: 0.0, 2: 0.0, 3: 0.0, 4: 0.0}
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n])

    def test_K5_endpoints(self):
        """Betweenness centrality: K5 endpoints"""
        G=nx.complete_graph(5)
        b=nx.betweenness_centrality(G,
                                          weight=None,
                                          normalized=False,
                                          endpoints=True)
        b_answer={0: 4.0, 1: 4.0, 2: 4.0, 3: 4.0, 4: 4.0}
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n])


    def test_P3_normalized(self):
        """Betweenness centrality: P3 normalized"""
        G=nx.path_graph(3)
        b=nx.betweenness_centrality(G,
                                          weight=None,
                                          normalized=True)
        b_answer={0: 0.0, 1: 1.0, 2: 0.0}
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n])


    def test_P3(self):
        """Betweenness centrality: P3"""
        G=nx.path_graph(3)
        b_answer={0: 0.0, 1: 1.0, 2: 0.0}
        b=nx.betweenness_centrality(G,
                                          weight=None,
                                          normalized=False)
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n])

    def test_P3_endpoints(self):
        """Betweenness centrality: P3 endpoints"""
        G=nx.path_graph(3)
        b_answer={0: 2.0, 1: 3.0, 2: 2.0}
        b=nx.betweenness_centrality(G,
                                          weight=None,
                                          normalized=False,
                                          endpoints=True)
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n])


    def test_krackhardt_kite_graph(self):
        """Betweenness centrality: Krackhardt kite graph"""
        G=nx.krackhardt_kite_graph()
        b_answer={0: 1.667,1: 1.667,2: 0.000,3: 7.333,4: 0.000,
                  5: 16.667,6: 16.667,7: 28.000,8: 16.000,9: 0.000}
        for b in b_answer:
            b_answer[b]/=2.0
        b=nx.betweenness_centrality(G,
                                          weight=None,
                                          normalized=False)

        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n],places=3)


    def test_krackhardt_kite_graph_normalized(self):
        """Betweenness centrality: Krackhardt kite graph normalized"""
        G=nx.krackhardt_kite_graph()
        b_answer={0:0.023,1:0.023,2:0.000,3:0.102,4:0.000,
                  5:0.231,6:0.231,7:0.389,8:0.222,9:0.000}
        b=nx.betweenness_centrality(G,
                                          weight=None,
                                          normalized=True)

        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n],places=3)


    def test_florentine_families_graph(self):
        """Betweenness centrality: Florentine families graph"""
        G=nx.florentine_families_graph()
        b_answer=\
             {'Acciaiuoli':    0.000,
              'Albizzi':       0.212,
              'Barbadori':     0.093,
              'Bischeri':      0.104,
              'Castellani':    0.055,
              'Ginori':        0.000,
              'Guadagni':      0.255,
              'Lamberteschi':  0.000,
              'Medici':        0.522,
              'Pazzi':         0.000,
              'Peruzzi':       0.022,
              'Ridolfi':       0.114,
              'Salviati':      0.143,
              'Strozzi':       0.103,
              'Tornabuoni':    0.092}

        b=nx.betweenness_centrality(G,
                                             weight=None,
                                             normalized=True)
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n],places=3)


    def test_ladder_graph(self):
        """Betweenness centrality: Ladder graph"""
        G = nx.Graph() # ladder_graph(3)
        G.add_edges_from([(0,1), (0,2), (1,3), (2,3), 
                          (2,4), (4,5), (3,5)])
        b_answer={0:1.667,1: 1.667,2: 6.667,
                  3: 6.667,4: 1.667,5: 1.667}
        for b in b_answer:
            b_answer[b]/=2.0
        b=nx.betweenness_centrality(G,
                                          weight=None,
                                          normalized=False)
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n],places=3)

    def test_disconnected_path(self):
        """Betweenness centrality: disconnected path"""
        G=nx.Graph()
        G.add_path([0,1,2])
        G.add_path([3,4,5,6])
        b_answer={0:0,1:1,2:0,3:0,4:2,5:2,6:0}
        b=nx.betweenness_centrality(G,
                                          weight=None,
                                          normalized=False)
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n])

    def test_disconnected_path_endpoints(self):
        """Betweenness centrality: disconnected path endpoints"""
        G=nx.Graph()
        G.add_path([0,1,2])
        G.add_path([3,4,5,6])
        b_answer={0:2,1:3,2:2,3:3,4:5,5:5,6:3}
        b=nx.betweenness_centrality(G,
                                          weight=None,
                                          normalized=False,
                                          endpoints=True)
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n])


    def test_directed_path(self):
        """Betweenness centrality: directed path"""
        G=nx.DiGraph()
        G.add_path([0,1,2])
        b=nx.betweenness_centrality(G,
                                          weight=None,
                                          normalized=False)
        b_answer={0: 0.0, 1: 1.0, 2: 0.0}
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n])

    def test_directed_path_normalized(self):
        """Betweenness centrality: directed path normalized"""
        G=nx.DiGraph()
        G.add_path([0,1,2])
        b=nx.betweenness_centrality(G,
                                          weight=None,
                                          normalized=True)
        b_answer={0: 0.0, 1: 0.5, 2: 0.0}
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n])



class TestWeightedBetweennessCentrality(object):
        
    def test_K5(self):
        """Weighted betweenness centrality: K5"""
        G=nx.complete_graph(5)
        b=nx.betweenness_centrality(G,
                                          weight='weight',
                                          normalized=False)
        b_answer={0: 0.0, 1: 0.0, 2: 0.0, 3: 0.0, 4: 0.0}
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n])

    def test_P3_normalized(self):
        """Weighted betweenness centrality: P3 normalized"""
        G=nx.path_graph(3)
        b=nx.betweenness_centrality(G,
                                          weight='weight',
                                          normalized=True)
        b_answer={0: 0.0, 1: 1.0, 2: 0.0}
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n])


    def test_P3(self):
        """Weighted betweenness centrality: P3"""
        G=nx.path_graph(3)
        b_answer={0: 0.0, 1: 1.0, 2: 0.0}
        b=nx.betweenness_centrality(G,
                                          weight='weight',
                                          normalized=False)
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n])

    def test_krackhardt_kite_graph(self):
        """Weighted betweenness centrality: Krackhardt kite graph"""
        G=nx.krackhardt_kite_graph()
        b_answer={0: 1.667,1: 1.667,2: 0.000,3: 7.333,4: 0.000,
                  5: 16.667,6: 16.667,7: 28.000,8: 16.000,9: 0.000}
        for b in b_answer:
            b_answer[b]/=2.0

        b=nx.betweenness_centrality(G,
                                          weight='weight',
                                          normalized=False)

        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n],places=3)


    def test_krackhardt_kite_graph_normalized(self):
        """Weighted betweenness centrality: 
        Krackhardt kite graph normalized
        """
        G=nx.krackhardt_kite_graph()
        b_answer={0:0.023,1:0.023,2:0.000,3:0.102,4:0.000,
                  5:0.231,6:0.231,7:0.389,8:0.222,9:0.000}
        b=nx.betweenness_centrality(G,
                                          weight='weight',
                                          normalized=True)

        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n],places=3)


    def test_florentine_families_graph(self):
        """Weighted betweenness centrality: 
        Florentine families graph"""
        G=nx.florentine_families_graph()
        b_answer=\
             {'Acciaiuoli':    0.000,
              'Albizzi':       0.212,
              'Barbadori':     0.093,
              'Bischeri':      0.104,
              'Castellani':    0.055,
              'Ginori':        0.000,
              'Guadagni':      0.255,
              'Lamberteschi':  0.000,
              'Medici':        0.522,
              'Pazzi':         0.000,
              'Peruzzi':       0.022,
              'Ridolfi':       0.114,
              'Salviati':      0.143,
              'Strozzi':       0.103,
              'Tornabuoni':    0.092}

        b=nx.betweenness_centrality(G,
                                          weight='weight',
                                          normalized=True)
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n],places=3)


    def test_ladder_graph(self):
        """Weighted betweenness centrality: Ladder graph"""
        G = nx.Graph() # ladder_graph(3)
        G.add_edges_from([(0,1), (0,2), (1,3), (2,3), 
                          (2,4), (4,5), (3,5)])
        b_answer={0:1.667,1: 1.667,2: 6.667,
                  3: 6.667,4: 1.667,5: 1.667}
        for b in b_answer:
            b_answer[b]/=2.0
        b=nx.betweenness_centrality(G,
                                          weight='weight',
                                          normalized=False)
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n],places=3)

    def test_G(self):
        """Weighted betweenness centrality: G"""                   
        G = weighted_G()               
        b_answer={0: 2.0, 1: 0.0, 2: 4.0, 3: 3.0, 4: 4.0, 5: 0.0}
        b=nx.betweenness_centrality(G,
                                          weight='weight',
                                          normalized=False)
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n])

    def test_G2(self):
        """Weighted betweenness centrality: G2"""                   
        G=nx.DiGraph()
        G.add_weighted_edges_from([('s','u',10) ,('s','x',5) ,
                                   ('u','v',1) ,('u','x',2) ,
                                   ('v','y',1) ,('x','u',3) ,
                                   ('x','v',5) ,('x','y',2) ,
                                   ('y','s',7) ,('y','v',6)])

        b_answer={'y':5.0,'x':5.0,'s':4.0,'u':2.0,'v':2.0}

        b=nx.betweenness_centrality(G,
                                             weight='weight',
                                             normalized=False)
        for n in sorted(G):
            assert_almost_equal(b[n],b_answer[n])


class TestEdgeBetweennessCentrality(object):
        
    def test_K5(self):
        """Edge betweenness centrality: K5"""
        G=nx.complete_graph(5)
        b=nx.edge_betweenness_centrality(G, weight=None, normalized=False)
        b_answer=dict.fromkeys(G.edges(),1)
        for n in sorted(G.edges()):
            assert_almost_equal(b[n],b_answer[n])

    def test_normalized_K5(self):
        """Edge betweenness centrality: K5"""
        G=nx.complete_graph(5)
        b=nx.edge_betweenness_centrality(G, weight=None, normalized=True)
        b_answer=dict.fromkeys(G.edges(),1/10.0)
        for n in sorted(G.edges()):
            assert_almost_equal(b[n],b_answer[n])


    def test_C4(self):
        """Edge betweenness centrality: C4"""
        G=nx.cycle_graph(4)
        b=nx.edge_betweenness_centrality(G, weight=None, normalized=True)
        b_answer={(0, 1):2,(0, 3):2, (1, 2):2, (2, 3): 2}
        for n in sorted(G.edges()):
            assert_almost_equal(b[n],b_answer[n]/6.0)

    def test_P4(self):
        """Edge betweenness centrality: P4"""
        G=nx.path_graph(4)
        b=nx.edge_betweenness_centrality(G, weight=None, normalized=False)
        b_answer={(0, 1):3,(1, 2):4, (2, 3):3}
        for n in sorted(G.edges()):
            assert_almost_equal(b[n],b_answer[n])

    def test_normalized_P4(self):
        """Edge betweenness centrality: P4"""
        G=nx.path_graph(4)
        b=nx.edge_betweenness_centrality(G, weight=None, normalized=True)
        b_answer={(0, 1):3,(1, 2):4, (2, 3):3}
        for n in sorted(G.edges()):
            assert_almost_equal(b[n],b_answer[n]/6.0)


    def test_balanced_tree(self):
        """Edge betweenness centrality: balanced tree"""
        G=nx.balanced_tree(r=2,h=2)
        b=nx.edge_betweenness_centrality(G, weight=None, normalized=False)
        b_answer={(0, 1):12,(0, 2):12,
                  (1, 3):6,(1, 4):6,(2, 5):6,(2,6):6}
        for n in sorted(G.edges()):
            assert_almost_equal(b[n],b_answer[n])

class TestWeightedEdgeBetweennessCentrality(object):
        
    def test_K5(self):
        """Edge betweenness centrality: K5"""
        G=nx.complete_graph(5)
        b=nx.edge_betweenness_centrality(G, weight='weight', normalized=False)
        b_answer=dict.fromkeys(G.edges(),1)
        for n in sorted(G.edges()):
            assert_almost_equal(b[n],b_answer[n])

    def test_C4(self):
        """Edge betweenness centrality: C4"""
        G=nx.cycle_graph(4)
        b=nx.edge_betweenness_centrality(G, weight='weight', normalized=False)
        b_answer={(0, 1):2,(0, 3):2, (1, 2):2, (2, 3): 2}
        for n in sorted(G.edges()):
            assert_almost_equal(b[n],b_answer[n])

    def test_P4(self):
        """Edge betweenness centrality: P4"""
        G=nx.path_graph(4)
        b=nx.edge_betweenness_centrality(G, weight='weight', normalized=False)
        b_answer={(0, 1):3,(1, 2):4, (2, 3):3}
        for n in sorted(G.edges()):
            assert_almost_equal(b[n],b_answer[n])


    def test_balanced_tree(self):
        """Edge betweenness centrality: balanced tree"""
        G=nx.balanced_tree(r=2,h=2)
        b=nx.edge_betweenness_centrality(G, weight='weight', normalized=False)
        b_answer={(0, 1):12,(0, 2):12,
                  (1, 3):6,(1, 4):6,(2, 5):6,(2,6):6}
        for n in sorted(G.edges()):
            assert_almost_equal(b[n],b_answer[n])

    def test_weighted_graph(self):
        eList = [(0, 1, 5), (0, 2, 4), (0, 3, 3), 
                 (0, 4, 2), (1, 2, 4), (1, 3, 1), 
                 (1, 4, 3), (2, 4, 5), (3, 4, 4)]
        G = nx.Graph()
        G.add_weighted_edges_from(eList)
        b = nx.edge_betweenness_centrality(G, weight='weight', normalized=False)
        b_answer={(0, 1):0.0,
                  (0, 2):1.0,
                  (0, 3):2.0,
                  (0, 4):1.0,
                  (1, 2):2.0,
                  (1, 3):3.5,
                  (1, 4):1.5,
                  (2, 4):1.0,
                  (3, 4):0.5}

        for n in sorted(G.edges()):
            assert_almost_equal(b[n],b_answer[n])

    def test_normalized_weighted_graph(self):
        eList = [(0, 1, 5), (0, 2, 4), (0, 3, 3), 
                 (0, 4, 2), (1, 2, 4), (1, 3, 1), 
                 (1, 4, 3), (2, 4, 5), (3, 4, 4)]
        G = nx.Graph()
        G.add_weighted_edges_from(eList)
        b = nx.edge_betweenness_centrality(G, weight='weight', normalized=True)
        b_answer={(0, 1):0.0,
                  (0, 2):1.0,
                  (0, 3):2.0,
                  (0, 4):1.0,
                  (1, 2):2.0,
                  (1, 3):3.5,
                  (1, 4):1.5,
                  (2, 4):1.0,
                  (3, 4):0.5}

        norm = len(G)*(len(G)-1)/2.0
        for n in sorted(G.edges()):
            assert_almost_equal(b[n],b_answer[n]/norm)