ioftools / networkxMiCe / networkxmaster / networkx / algorithms / planar_drawing.py @ 5cef0f13
History  View  Annotate  Download (16 KB)
1 
import networkx as nx 

2 
from collections import defaultdict 
3  
4  
5 
__all__ = ["combinatorial_embedding_to_pos"]

6  
7  
8 
def combinatorial_embedding_to_pos(embedding, fully_triangulate=False): 
9 
"""Assigns every node a (x, y) position based on the given embedding

10 

11 
The algorithm iteratively inserts nodes of the input graph in a certain

12 
order and rearranges previously inserted nodes so that the planar drawing

13 
stays valid. This is done efficiently by only maintaining relative

14 
positions during the node placements and calculating the absolute positions

15 
at the end. For more information see [1]_.

16 

17 
Parameters

18 


19 
embedding : nx.PlanarEmbedding

20 
This defines the order of the edges

21 

22 
fully_triangulate : bool

23 
If set to True the algorithm adds edges to a copy of the input

24 
embedding and makes it chordal.

25 

26 
Returns

27 


28 
pos : dict

29 
Maps each node to a tuple that defines the (x, y) position

30 

31 
References

32 


33 
.. [1] M. Chrobak and T.H. Payne:

34 
A Lineartime Algorithm for Drawing a Planar Graph on a Grid 1989

35 
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.6677

36 

37 
"""

38 
if len(embedding.nodes()) < 4: 
39 
# Position the node in any triangle

40 
default_positions = [(0, 0), (2, 0), (1, 1)] 
41 
pos = {} 
42 
for i, v in enumerate(embedding.nodes()): 
43 
pos[v] = default_positions[i] 
44 
return pos

45  
46 
embedding, outer_face = triangulate_embedding(embedding, fully_triangulate) 
47  
48 
# The following dicts map a node to another node

49 
# If a node is not in the key set it means that the node is not yet in G_k

50 
# If a node maps to None then the corresponding subtree does not exist

51 
left_t_child = {} 
52 
right_t_child = {} 
53  
54 
# The following dicts map a node to an integer

55 
delta_x = {} 
56 
y_coordinate = {} 
57  
58 
node_list = get_canonical_ordering(embedding, outer_face) 
59  
60 
# 1. Phase: Compute relative positions

61  
62 
# Initialization

63 
v1, v2, v3 = node_list[0][0], node_list[1][0], node_list[2][0] 
64  
65 
delta_x[v1] = 0

66 
y_coordinate[v1] = 0

67 
right_t_child[v1] = v3 
68 
left_t_child[v1] = None

69  
70 
delta_x[v2] = 1

71 
y_coordinate[v2] = 0

72 
right_t_child[v2] = None

73 
left_t_child[v2] = None

74  
75 
delta_x[v3] = 1

76 
y_coordinate[v3] = 1

77 
right_t_child[v3] = v2 
78 
left_t_child[v3] = None

79  
80 
for k in range(3, len(node_list)): 
81 
vk, contour_neighbors = node_list[k] 
82 
wp = contour_neighbors[0]

83 
wp1 = contour_neighbors[1]

84 
wq = contour_neighbors[1]

85 
wq1 = contour_neighbors[2]

86 
adds_mult_tri = len(contour_neighbors) > 2 
87  
88 
# Stretch gaps:

89 
delta_x[wp1] += 1

90 
delta_x[wq] += 1

91  
92 
delta_x_wp_wq = sum((delta_x[x] for x in contour_neighbors[1:])) 
93  
94 
# Adjust offsets

95 
delta_x[vk] = (y_coordinate[wp] + delta_x_wp_wq + y_coordinate[wq])//2

96 
y_coordinate[vk] = (y_coordinate[wp] + delta_x_wp_wq + 
97 
y_coordinate[wq]) // 2

98 
delta_x[wq] = delta_x_wp_wq  delta_x[vk] 
99 
if adds_mult_tri:

100 
delta_x[wp1] = delta_x[vk] 
101  
102 
# Install v_k:

103 
right_t_child[wp] = vk 
104 
right_t_child[vk] = wq 
105 
if adds_mult_tri:

106 
left_t_child[vk] = wp1 
107 
right_t_child[wq1] = None

108 
else:

109 
left_t_child[vk] = None

110  
111 
# 2. Phase: Set absolute positions

112 
pos = dict()

113 
pos[v1] = (0, y_coordinate[v1])

114 
remaining_nodes = [v1] 
115 
while remaining_nodes:

116 
parent_node = remaining_nodes.pop() 
117  
118 
# Calculate position for left child

119 
set_position(parent_node, left_t_child, 
120 
remaining_nodes, delta_x, y_coordinate, pos) 
121 
# Calculate position for right child

122 
set_position(parent_node, right_t_child, 
123 
remaining_nodes, delta_x, y_coordinate, pos) 
124 
return pos

125  
126  
127 
def set_position(parent, tree, remaining_nodes, delta_x, y_coordinate, pos): 
128 
"""Helper method to calculate the absolute position of nodes."""

129 
child = tree[parent] 
130 
parent_node_x = pos[parent][0]

131 
if child is not None: 
132 
# Calculate pos of child

133 
child_x = parent_node_x + delta_x[child] 
134 
pos[child] = (child_x, y_coordinate[child]) 
135 
# Remember to calculate pos of its children

136 
remaining_nodes.append(child) 
137  
138  
139 
def get_canonical_ordering(embedding, outer_face): 
140 
"""Returns a canonical ordering of the nodes

141 

142 
The canonical ordering of nodes (v1, ..., vn) must fulfill the following

143 
conditions:

144 
(See Lemma 1 in [2]_)

145 

146 
 For the subgraph G_k of the input graph induced by v1, ..., vk it holds:

147 
 2connected

148 
 internally triangulated

149 
 the edge (v1, v2) is part of the outer face

150 
 For a node v(k+1) the following holds:

151 
 The node v(k+1) is part of the outer face of G_k

152 
 It has at least two neighbors in G_k

153 
 All neighbors of v(k+1) in G_k lie consecutively on the outer face of

154 
G_k (excluding the edge (v1, v2)).

155 

156 
The algorithm used here starts with G_n (containing all nodes). It first

157 
selects the nodes v1 and v2. And then tries to find the order of the other

158 
nodes by checking which node can be removed in order to fulfill the

159 
conditions mentioned above. This is done by calculating the number of

160 
chords of nodes on the outer face. For more information see [1]_.

161 

162 
Parameters

163 


164 
embedding : nx.PlanarEmbedding

165 
The embedding must be triangulated

166 
outer_face : list

167 
The nodes on the outer face of the graph

168 

169 
Returns

170 


171 
ordering : list

172 
A list of tuples `(vk, wp_wq)`. Here `vk` is the node at this position

173 
in the canonical ordering. The element `wp_wq` is a list of nodes that

174 
make up the outer face of G_k.

175 

176 
References

177 


178 
.. [1] Steven Chaplick.

179 
Canonical Orders of Planar Graphs and (some of) Their Applications 2015

180 
https://wuecampus2.uniwuerzburg.de/moodle/pluginfile.php/545727/mod_resource/content/0/vgss15vl03canonicalordersdruckversion.pdf

181 
.. [2] M. Chrobak and T.H. Payne:

182 
A Lineartime Algorithm for Drawing a Planar Graph on a Grid 1989

183 
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.6677

184 

185 
"""

186 
v1 = outer_face[0]

187 
v2 = outer_face[1]

188 
chords = defaultdict(int) # Maps nodes to the number of their chords 
189 
marked_nodes = set()

190 
ready_to_pick = set(outer_face)

191  
192 
# Initialize outer_face_ccw_nbr (do not include v1 > v2)

193 
outer_face_ccw_nbr = {} 
194 
prev_nbr = v2 
195 
for idx in range(2, len(outer_face)): 
196 
outer_face_ccw_nbr[prev_nbr] = outer_face[idx] 
197 
prev_nbr = outer_face[idx] 
198 
outer_face_ccw_nbr[prev_nbr] = v1 
199  
200 
# Initialize outer_face_cw_nbr (do not include v2 > v1)

201 
outer_face_cw_nbr = {} 
202 
prev_nbr = v1 
203 
for idx in range(len(outer_face)1, 0, 1): 
204 
outer_face_cw_nbr[prev_nbr] = outer_face[idx] 
205 
prev_nbr = outer_face[idx] 
206  
207 
def is_outer_face_nbr(x, y): 
208 
if x not in outer_face_ccw_nbr: 
209 
return outer_face_cw_nbr[x] == y

210 
if x not in outer_face_cw_nbr: 
211 
return outer_face_ccw_nbr[x] == y

212 
return outer_face_ccw_nbr[x] == y or outer_face_cw_nbr[x] == y 
213  
214 
def is_on_outer_face(x): 
215 
return x not in marked_nodes and (x in outer_face_ccw_nbr.keys() or 
216 
x == v1) 
217  
218 
# Initialize number of chords

219 
for v in outer_face: 
220 
for nbr in embedding.neighbors_cw_order(v): 
221 
if is_on_outer_face(nbr) and not is_outer_face_nbr(v, nbr): 
222 
chords[v] += 1

223 
ready_to_pick.discard(v) 
224  
225 
# Initialize canonical_ordering

226 
canonical_ordering = [None] * len(embedding.nodes()) # type: list 
227 
canonical_ordering[0] = (v1, [])

228 
canonical_ordering[1] = (v2, [])

229 
ready_to_pick.discard(v1) 
230 
ready_to_pick.discard(v2) 
231  
232 
for k in range(len(embedding.nodes())1, 1, 1): 
233 
# 1. Pick v from ready_to_pick

234 
v = ready_to_pick.pop() 
235 
marked_nodes.add(v) 
236  
237 
# v has exactly two neighbors on the outer face (wp and wq)

238 
wp = None

239 
wq = None

240 
# Iterate over neighbors of v to find wp and wq

241 
nbr_iterator = iter(embedding.neighbors_cw_order(v))

242 
while True: 
243 
nbr = next(nbr_iterator)

244 
if nbr in marked_nodes: 
245 
# Only consider nodes that are not yet removed

246 
continue

247 
if is_on_outer_face(nbr):

248 
# nbr is either wp or wq

249 
if nbr == v1:

250 
wp = v1 
251 
elif nbr == v2:

252 
wq = v2 
253 
else:

254 
if outer_face_cw_nbr[nbr] == v:

255 
# nbr is wp

256 
wp = nbr 
257 
else:

258 
# nbr is wq

259 
wq = nbr 
260 
if wp is not None and wq is not None: 
261 
# We don't need to iterate any further

262 
break

263  
264 
# Obtain new nodes on outer face (neighbors of v from wp to wq)

265 
wp_wq = [wp] 
266 
nbr = wp 
267 
while nbr != wq:

268 
# Get next next neighbor (clockwise on the outer face)

269 
next_nbr = embedding[v][nbr]['ccw']

270 
wp_wq.append(next_nbr) 
271 
# Update outer face

272 
outer_face_cw_nbr[nbr] = next_nbr 
273 
outer_face_ccw_nbr[next_nbr] = nbr 
274 
# Move to next neighbor of v

275 
nbr = next_nbr 
276  
277 
if len(wp_wq) == 2: 
278 
# There was a chord between wp and wq, decrease number of chords

279 
chords[wp] = 1

280 
if chords[wp] == 0: 
281 
ready_to_pick.add(wp) 
282 
chords[wq] = 1

283 
if chords[wq] == 0: 
284 
ready_to_pick.add(wq) 
285 
else:

286 
# Update all chords involving w_(p+1) to w_(q1)

287 
new_face_nodes = set(wp_wq[1:1]) 
288 
for w in new_face_nodes: 
289 
# If we do not find a chord for w later we can pick it next

290 
ready_to_pick.add(w) 
291 
for nbr in embedding.neighbors_cw_order(w): 
292 
if is_on_outer_face(nbr) and not is_outer_face_nbr(w, nbr): 
293 
# There is a chord involving w

294 
chords[w] += 1

295 
ready_to_pick.discard(w) 
296 
if nbr not in new_face_nodes: 
297 
# Also increase chord for the neighbor

298 
# We only iterator over new_face_nodes

299 
chords[nbr] += 1

300 
ready_to_pick.discard(nbr) 
301 
# Set the canonical ordering node and the list of contour neighbors

302 
canonical_ordering[k] = (v, wp_wq) 
303  
304 
return canonical_ordering

305  
306  
307 
def triangulate_face(embedding, v1, v2): 
308 
"""Triangulates the face given by half edge (v, w)

309 

310 
Parameters

311 


312 
embedding : nx.PlanarEmbedding

313 
v1 : node

314 
The halfedge (v1, v2) belongs to the face that gets triangulated

315 
v2 : node

316 
"""

317 
_, v3 = embedding.next_face_half_edge(v1, v2) 
318 
_, v4 = embedding.next_face_half_edge(v2, v3) 
319 
if v1 == v2 or v1 == v3: 
320 
# The component has less than 3 nodes

321 
return

322 
while v1 != v4:

323 
# Add edge if not already present on other side

324 
if embedding.has_edge(v1, v3):

325 
# Cannot triangulate at this position

326 
v1, v2, v3 = v2, v3, v4 
327 
else:

328 
# Add edge for triangulation

329 
embedding.add_half_edge_cw(v1, v3, v2) 
330 
embedding.add_half_edge_ccw(v3, v1, v2) 
331 
v1, v2, v3 = v1, v3, v4 
332 
# Get next node

333 
_, v4 = embedding.next_face_half_edge(v2, v3) 
334  
335  
336 
def triangulate_embedding(embedding, fully_triangulate=True): 
337 
"""Triangulates the embedding.

338 

339 
Traverses faces of the embedding and adds edges to a copy of the

340 
embedding to triangulate it.

341 
The method also ensures that the resulting graph is 2connected by adding

342 
edges if the same vertex is contained twice on a path around a face.

343 

344 
Parameters

345 


346 
embedding : nx.PlanarEmbedding

347 
The input graph must contain at least 3 nodes.

348 

349 
fully_triangulate : bool

350 
If set to False the face with the most nodes is chooses as outer face.

351 
This outer face does not get triangulated.

352 

353 
Returns

354 


355 
(embedding, outer_face) : (nx.PlanarEmbedding, list) tuple

356 
The element `embedding` is a new embedding containing all edges from

357 
the input embedding and the additional edges to triangulate the graph.

358 
The element `outer_face` is a list of nodes that lie on the outer face.

359 
If the graph is fully triangulated these are three arbitrary connected

360 
nodes.

361 

362 
"""

363 
if len(embedding.nodes) <= 1: 
364 
return embedding, list(embedding.nodes) 
365 
embedding = nx.PlanarEmbedding(embedding) 
366  
367 
# Get a list with a node for each connected component

368 
component_nodes = [next(iter(x)) for x in 
369 
nx.connected_components(embedding)] 
370  
371 
# 1. Make graph a single component (add edge between components)

372 
for i in range(len(component_nodes)1): 
373 
v1 = component_nodes[i] 
374 
v2 = component_nodes[i+1]

375 
embedding.connect_components(v1, v2) 
376  
377 
# 2. Calculate faces, ensure 2connectedness and determine outer face

378 
outer_face = [] # A face with the most number of nodes

379 
face_list = [] 
380 
edges_visited = set() # Used to keep track of already visited faces 
381 
for v in embedding.nodes(): 
382 
for w in embedding.neighbors_cw_order(v): 
383 
new_face = make_bi_connected(embedding, v, w, edges_visited) 
384 
if new_face:

385 
# Found a new face

386 
face_list.append(new_face) 
387 
if len(new_face) > len(outer_face): 
388 
# The face is a candidate to be the outer face

389 
outer_face = new_face 
390  
391 
# 3. Triangulate (internal) faces

392 
for face in face_list: 
393 
if face is not outer_face or fully_triangulate: 
394 
# Triangulate this face

395 
triangulate_face(embedding, face[0], face[1]) 
396  
397 
if fully_triangulate:

398 
v1 = outer_face[0]

399 
v2 = outer_face[1]

400 
v3 = embedding[v2][v1]['ccw']

401 
outer_face = [v1, v2, v3] 
402  
403 
return embedding, outer_face

404  
405  
406 
def make_bi_connected(embedding, starting_node, outgoing_node, edges_counted): 
407 
"""Triangulate a face and make it 2connected

408 

409 
This method also adds all edges on the face to `edges_counted`.

410 

411 
Parameters

412 


413 
embedding: nx.PlanarEmbedding

414 
The embedding that defines the faces

415 
starting_node : node

416 
A node on the face

417 
outgoing_node : node

418 
A node such that the half edge (starting_node, outgoing_node) belongs

419 
to the face

420 
edges_counted: set

421 
Set of all halfedges that belong to a face that have been visited

422 

423 
Returns

424 


425 
face_nodes: list

426 
A list of all nodes at the border of this face

427 
"""

428  
429 
# Check if the face has already been calculated

430 
if (starting_node, outgoing_node) in edges_counted: 
431 
# This face was already counted

432 
return []

433 
edges_counted.add((starting_node, outgoing_node)) 
434  
435 
# Add all edges to edges_counted which have this face to their left

436 
v1 = starting_node 
437 
v2 = outgoing_node 
438 
face_list = [starting_node] # List of nodes around the face

439 
face_set = set(face_list) # Set for faster queries 
440 
_, v3 = embedding.next_face_half_edge(v1, v2) 
441  
442 
# Move the nodes v1, v2, v3 around the face:

443 
while v2 != starting_node or v3 != outgoing_node: 
444 
if v1 == v2:

445 
raise nx.NetworkXException("Invalid halfedge") 
446 
# cycle is not completed yet

447 
if v2 in face_set: 
448 
# v2 encountered twice: Add edge to ensure 2connectedness

449 
embedding.add_half_edge_cw(v1, v3, v2) 
450 
embedding.add_half_edge_ccw(v3, v1, v2) 
451 
edges_counted.add((v2, v3)) 
452 
edges_counted.add((v3, v1)) 
453 
v2 = v1 
454 
else:

455 
face_set.add(v2) 
456 
face_list.append(v2) 
457  
458 
# set next edge

459 
v1 = v2 
460 
v2, v3 = embedding.next_face_half_edge(v2, v3) 
461  
462 
# remember that this edge has been counted

463 
edges_counted.add((v1, v2)) 
464  
465 
return face_list
