Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (3.65 KB)

1
# test_voronoi.py - unit tests for the networkx.algorithms.voronoi module
2
#
3
# Copyright 2016-2019 NetworkX developers.
4
#
5
# This file is part of NetworkX.
6
#
7
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
8
# information.
9
from nose.tools import assert_equal
10

    
11
import networkx as nx
12
from networkx.utils import pairwise
13

    
14

    
15
class TestVoronoiCells(object):
16
    """Unit tests for the Voronoi cells function."""
17

    
18
    def test_isolates(self):
19
        """Tests that a graph with isolated nodes has all isolates in
20
        one block of the partition.
21

22
        """
23
        G = nx.empty_graph(5)
24
        cells = nx.voronoi_cells(G, {0, 2, 4})
25
        expected = {0: {0}, 2: {2}, 4: {4}, 'unreachable': {1, 3}}
26
        assert_equal(expected, cells)
27

    
28
    def test_undirected_unweighted(self):
29
        G = nx.cycle_graph(6)
30
        cells = nx.voronoi_cells(G, {0, 3})
31
        expected = {0: {0, 1, 5}, 3: {2, 3, 4}}
32
        assert_equal(expected, cells)
33

    
34
    def test_directed_unweighted(self):
35
        # This is the singly-linked directed cycle graph on six nodes.
36
        G = nx.DiGraph(pairwise(range(6), cyclic=True))
37
        cells = nx.voronoi_cells(G, {0, 3})
38
        expected = {0: {0, 1, 2}, 3: {3, 4, 5}}
39
        assert_equal(expected, cells)
40

    
41
    def test_directed_inward(self):
42
        """Tests that reversing the graph gives the "inward" Voronoi
43
        partition.
44

45
        """
46
        # This is the singly-linked reverse directed cycle graph on six nodes.
47
        G = nx.DiGraph(pairwise(range(6), cyclic=True))
48
        G = G.reverse(copy=False)
49
        cells = nx.voronoi_cells(G, {0, 3})
50
        expected = {0: {0, 4, 5}, 3: {1, 2, 3}}
51
        assert_equal(expected, cells)
52

    
53
    def test_undirected_weighted(self):
54
        edges = [(0, 1, 10), (1, 2, 1), (2, 3, 1)]
55
        G = nx.Graph()
56
        G.add_weighted_edges_from(edges)
57
        cells = nx.voronoi_cells(G, {0, 3})
58
        expected = {0: {0}, 3: {1, 2, 3}}
59
        assert_equal(expected, cells)
60

    
61
    def test_directed_weighted(self):
62
        edges = [(0, 1, 10), (1, 2, 1), (2, 3, 1), (3, 2, 1), (2, 1, 1)]
63
        G = nx.DiGraph()
64
        G.add_weighted_edges_from(edges)
65
        cells = nx.voronoi_cells(G, {0, 3})
66
        expected = {0: {0}, 3: {1, 2, 3}}
67
        assert_equal(expected, cells)
68

    
69
    def test_multigraph_unweighted(self):
70
        """Tests that the Voronoi cells for a multigraph are the same as
71
        for a simple graph.
72

73
        """
74
        edges = [(0, 1), (1, 2), (2, 3)]
75
        G = nx.MultiGraph(2 * edges)
76
        H = nx.Graph(G)
77
        G_cells = nx.voronoi_cells(G, {0, 3})
78
        H_cells = nx.voronoi_cells(H, {0, 3})
79
        assert_equal(G_cells, H_cells)
80

    
81
    def test_multidigraph_unweighted(self):
82
        # This is the twice-singly-linked directed cycle graph on six nodes.
83
        edges = list(pairwise(range(6), cyclic=True))
84
        G = nx.MultiDiGraph(2 * edges)
85
        H = nx.DiGraph(G)
86
        G_cells = nx.voronoi_cells(G, {0, 3})
87
        H_cells = nx.voronoi_cells(H, {0, 3})
88
        assert_equal(G_cells, H_cells)
89

    
90
    def test_multigraph_weighted(self):
91
        edges = [(0, 1, 10), (0, 1, 10), (1, 2, 1), (1, 2, 100), (2, 3, 1),
92
                 (2, 3, 100)]
93
        G = nx.MultiGraph()
94
        G.add_weighted_edges_from(edges)
95
        cells = nx.voronoi_cells(G, {0, 3})
96
        expected = {0: {0}, 3: {1, 2, 3}}
97
        assert_equal(expected, cells)
98

    
99
    def test_multidigraph_weighted(self):
100
        edges = [(0, 1, 10), (0, 1, 10), (1, 2, 1), (2, 3, 1), (3, 2, 10),
101
                 (3, 2, 1), (2, 1, 10), (2, 1, 1)]
102
        G = nx.MultiDiGraph()
103
        G.add_weighted_edges_from(edges)
104
        cells = nx.voronoi_cells(G, {0, 3})
105
        expected = {0: {0}, 3: {1, 2, 3}}
106
        assert_equal(expected, cells)