Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / 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 Linear-time 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
        - 2-connected
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.uni-wuerzburg.de/moodle/pluginfile.php/545727/mod_resource/content/0/vg-ss15-vl03-canonical-orders-druckversion.pdf
181
    .. [2] M. Chrobak and T.H. Payne:
182
        A Linear-time 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_(q-1)
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 half-edge (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 2-connected 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 2-connectedness 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 2-connected
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 half-edges 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 half-edge")
446
        # cycle is not completed yet
447
        if v2 in face_set:
448
            # v2 encountered twice: Add edge to ensure 2-connectedness
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