Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (8.61 KB)

1
import networkx as nx
2
from networkx.algorithms.planar_drawing import triangulate_embedding
3
import math
4
from nose.tools import assert_true, assert_equals, raises
5

    
6

    
7
def test_graph1():
8
    embedding_data = {0: [1, 2, 3], 1: [2, 0], 2: [3, 0, 1], 3: [2, 0]}
9
    check_embedding_data(embedding_data)
10

    
11

    
12
def test_graph2():
13
    embedding_data = {
14
        0: [8, 6], 1: [2, 6, 9], 2: [8, 1, 7, 9, 6, 4], 3: [9], 4: [2],
15
        5: [6, 8], 6: [9, 1, 0, 5, 2], 7: [9, 2], 8: [0, 2, 5],
16
        9: [1, 6, 2, 7, 3]
17
    }
18
    check_embedding_data(embedding_data)
19

    
20

    
21
def test_circle_graph():
22
    embedding_data = {
23
        0: [1, 9], 1: [0, 2], 2: [1, 3], 3: [2, 4], 4: [3, 5],
24
        5: [4, 6], 6: [5, 7], 7: [6, 8], 8: [7, 9], 9: [8, 0]
25
    }
26
    check_embedding_data(embedding_data)
27

    
28

    
29
def test_grid_graph():
30
    embedding_data = {
31
        (0, 1): [(0, 0), (1, 1), (0, 2)], (1, 2): [(1, 1), (2, 2), (0, 2)],
32
        (0, 0): [(0, 1), (1, 0)],  (2, 1): [(2, 0), (2, 2), (1, 1)],
33
        (1, 1): [(2, 1), (1, 2), (0, 1), (1, 0)],
34
        (2, 0): [(1, 0), (2, 1)], (2, 2): [(1, 2), (2, 1)],
35
        (1, 0): [(0, 0), (2, 0), (1, 1)], (0, 2): [(1, 2), (0, 1)]
36
    }
37
    check_embedding_data(embedding_data)
38

    
39

    
40
def test_one_node_graph():
41
    embedding_data = {0: []}
42
    check_embedding_data(embedding_data)
43

    
44

    
45
def test_two_node_graph():
46
    embedding_data = {0: [1], 1: [0]}
47
    check_embedding_data(embedding_data)
48

    
49

    
50
def test_three_node_graph():
51
    embedding_data = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
52
    check_embedding_data(embedding_data)
53

    
54

    
55
def test_multiple_component_graph1():
56
    embedding_data = {0: [], 1: []}
57
    check_embedding_data(embedding_data)
58

    
59

    
60
def test_multiple_component_graph2():
61
    embedding_data = {
62
        0: [1, 2], 1: [0, 2], 2: [0, 1],
63
        3: [4, 5], 4: [3, 5], 5: [3, 4]
64
    }
65
    check_embedding_data(embedding_data)
66

    
67

    
68
@raises(nx.NetworkXException)
69
def test_invalid_half_edge():
70
    embedding_data = {1: [2, 3], 2: [1, 3], 3: [1, 2], 4: [1, 2, 3]}
71
    embedding = nx.PlanarEmbedding()
72
    embedding.set_data(embedding_data)
73
    nx.combinatorial_embedding_to_pos(embedding)
74

    
75

    
76
def test_triangulate_embedding1():
77
    embedding = nx.PlanarEmbedding()
78
    embedding.add_node(1)
79
    expected_embedding = {1: []}
80
    check_triangulation(embedding, expected_embedding)
81

    
82

    
83
def test_triangulate_embedding2():
84
    embedding = nx.PlanarEmbedding()
85
    embedding.connect_components(1, 2)
86
    expected_embedding = {1: [2], 2: [1]}
87
    check_triangulation(embedding, expected_embedding)
88

    
89

    
90
def check_triangulation(embedding, expected_embedding):
91
    res_embedding, _ = triangulate_embedding(embedding, True)
92
    assert_equals(res_embedding.get_data(), expected_embedding,
93
                  "Expected embedding incorrect")
94
    res_embedding, _ = triangulate_embedding(embedding, False)
95
    assert_equals(res_embedding.get_data(), expected_embedding,
96
                  "Expected embedding incorrect")
97

    
98

    
99
def check_embedding_data(embedding_data):
100
    """Checks that the planar embedding of the input is correct"""
101
    embedding = nx.PlanarEmbedding()
102
    embedding.set_data(embedding_data)
103
    pos_fully = nx.combinatorial_embedding_to_pos(embedding, False)
104
    msg = "Planar drawing does not conform to the embedding (fully " \
105
          "triangulation)"
106
    assert_true(planar_drawing_conforms_to_embedding(embedding, pos_fully),
107
                msg)
108
    check_edge_intersections(embedding, pos_fully)
109
    pos_internally = nx.combinatorial_embedding_to_pos(embedding, True)
110
    msg = "Planar drawing does not conform to the embedding (internal " \
111
          "triangulation)"
112
    assert_true(planar_drawing_conforms_to_embedding(embedding,
113
                                                     pos_internally),
114
                msg)
115
    check_edge_intersections(embedding, pos_internally)
116

    
117

    
118
def is_close(a, b, rel_tol=1e-09, abs_tol=0.0):
119
    # Check if float numbers are basically equal, for python >=3.5 there is
120
    # function for that in the standard library
121
    return abs(a-b) <= max(rel_tol * max(abs(a), abs(b)), abs_tol)
122

    
123

    
124
def point_in_between(a, b, p):
125
    # checks if p is on the line between a and b
126
    x1, y1 = a
127
    x2, y2 = b
128
    px, py = p
129
    dist_1_2 = math.sqrt((x1 - x2)**2 + (y1 - y2)**2)
130
    dist_1_p = math.sqrt((x1 - px)**2 + (y1 - py)**2)
131
    dist_2_p = math.sqrt((x2 - px)**2 + (y2 - py)**2)
132
    return is_close(dist_1_p+dist_2_p, dist_1_2)
133

    
134

    
135
def check_edge_intersections(G, pos):
136
    """Check all edges in G for intersections.
137

138
    Raises an exception if an intersection is found.
139

140
    Parameters
141
    ----------
142
    G : NetworkX graph
143
    pos : dict
144
        Maps every node to a tuple (x, y) representing its position
145

146
    """
147
    for a, b in G.edges():
148
        for c, d in G.edges():
149
            # Check if end points are different
150
            if a != c and b != d and b != c and a != d:
151
                x1, y1 = pos[a]
152
                x2, y2 = pos[b]
153
                x3, y3 = pos[c]
154
                x4, y4 = pos[d]
155
                determinant = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)
156
                if determinant != 0:  # the lines are not parallel
157
                    # calculate intersection point, see:
158
                    # https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection
159
                    px = ((x1 * y2 - y1 * x2) * (x3 - x4) -
160
                          (x1 - x2) * (x3 * y4 - y3 * x4) / float(determinant))
161
                    py = ((x1 * y2 - y1 * x2) * (y3 - y4) -
162
                          (y1 - y2) * (x3 * y4 - y3 * x4) / float(determinant))
163

    
164
                    # Check if intersection lies between the points
165
                    if (point_in_between(pos[a], pos[b], (px, py)) and
166
                            point_in_between(pos[c], pos[d], (px, py))):
167
                        msg = "There is an intersection at {},{}".format(px,
168
                                                                         py)
169
                        raise nx.NetworkXException(msg)
170

    
171
                #  Check overlap
172
                msg = "A node lies on a edge connecting two other nodes"
173
                if (point_in_between(pos[a], pos[b], pos[c]) or
174
                        point_in_between(pos[a], pos[b], pos[d]) or
175
                        point_in_between(pos[c], pos[d], pos[a]) or
176
                        point_in_between(pos[c], pos[d], pos[b])):
177
                    raise nx.NetworkXException(msg)
178
    # No edge intersection found
179

    
180

    
181
class Vector(object):
182
    """Compare vectors by their angle without loss of precision
183

184
    All vectors in direction [0, 1] are the smallest.
185
    The vectors grow in clockwise direction.
186
    """
187
    __slots__ = ['x', 'y', 'node', 'quadrant']
188

    
189
    def __init__(self, x, y, node):
190
        self.x = x
191
        self.y = y
192
        self.node = node
193
        if self.x >= 0 and self.y > 0:
194
            self.quadrant = 1
195
        elif self.x > 0 and self.y <= 0:
196
            self.quadrant = 2
197
        elif self.x <= 0 and self.y < 0:
198
            self.quadrant = 3
199
        else:
200
            self.quadrant = 4
201

    
202
    def __eq__(self, other):
203
        return (self.quadrant == other.quadrant and
204
                self.x * other.y == self.y * other.x)
205

    
206
    def __lt__(self, other):
207
        if self.quadrant < other.quadrant:
208
            return True
209
        elif self.quadrant > other.quadrant:
210
            return False
211
        else:
212
            return self.x * other.y < self.y * other.x
213

    
214
    def __ne__(self, other):
215
        return not self == other
216

    
217
    def __le__(self, other):
218
        return not other < self
219

    
220
    def __gt__(self, other):
221
        return other < self
222

    
223
    def __ge__(self, other):
224
        return not self < other
225

    
226

    
227
def planar_drawing_conforms_to_embedding(embedding, pos):
228
    """Checks if pos conforms to the planar embedding
229

230
    Returns true iff the neighbors are actually oriented in the orientation
231
    specified of the embedding
232
    """
233
    for v in embedding:
234
        nbr_vectors = []
235
        v_pos = pos[v]
236
        for nbr in embedding[v]:
237
            new_vector = Vector(pos[nbr][0] - v_pos[0], pos[nbr][1] - v_pos[1],
238
                                nbr)
239
            nbr_vectors.append(new_vector)
240
        # Sort neighbors according to their phi angle
241
        nbr_vectors.sort()
242
        for idx, nbr_vector in enumerate(nbr_vectors):
243
            cw_vector = nbr_vectors[(idx + 1) % len(nbr_vectors)]
244
            ccw_vector = nbr_vectors[idx - 1]
245
            if (embedding[v][nbr_vector.node]['cw'] != cw_vector.node or
246
                    embedding[v][nbr_vector.node]['ccw'] != ccw_vector.node):
247
                return False
248
            if cw_vector.node != nbr_vector.node and cw_vector == nbr_vector:
249
                # Lines overlap
250
                return False
251
            if ccw_vector.node != nbr_vector.node and ccw_vector == nbr_vector:
252
                # Lines overlap
253
                return False
254
    return True