ioftools / networkxMiCe / networkxmaster / 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=1e09, 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(ab) <= 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 