Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / drawing / layout.py @ 5cef0f13

History | View | Annotate | Download (29.6 KB)

1
#    Copyright (C) 2004-2019 by
2
#    Aric Hagberg <hagberg@lanl.gov>
3
#    Dan Schult <dschult@colgate.edu>
4
#    Pieter Swart <swart@lanl.gov>
5
#    Richard Penney <rwpenney@users.sourceforge.net>
6
#    All rights reserved.
7
#    BSD license.
8
#
9
# Authors: Aric Hagberg <aric.hagberg@gmail.com>,
10
#          Dan Schult <dschult@colgate.edu>
11
"""
12
******
13
Layout
14
******
15

16
Node positioning algorithms for graph drawing.
17

18
For `random_layout()` the possible resulting shape
19
is a square of side [0, scale] (default: [0, 1])
20
Changing `center` shifts the layout by that amount.
21

22
For the other layout routines, the extent is
23
[center - scale, center + scale] (default: [-1, 1]).
24

25
Warning: Most layout routines have only been tested in 2-dimensions.
26

27
"""
28
from __future__ import division
29
import networkx as nx
30
from networkx.utils import random_state
31

    
32
__all__ = ['bipartite_layout',
33
           'circular_layout',
34
           'kamada_kawai_layout',
35
           'random_layout',
36
           'rescale_layout',
37
           'shell_layout',
38
           'spring_layout',
39
           'spectral_layout',
40
           'planar_layout',
41
           'fruchterman_reingold_layout']
42

    
43

    
44
def _process_params(G, center, dim):
45
    # Some boilerplate code.
46
    import numpy as np
47

    
48
    if not isinstance(G, nx.Graph):
49
        empty_graph = nx.Graph()
50
        empty_graph.add_nodes_from(G)
51
        G = empty_graph
52

    
53
    if center is None:
54
        center = np.zeros(dim)
55
    else:
56
        center = np.asarray(center)
57

    
58
    if len(center) != dim:
59
        msg = "length of center coordinates must match dimension of layout"
60
        raise ValueError(msg)
61

    
62
    return G, center
63

    
64

    
65
@random_state(3)
66
def random_layout(G, center=None, dim=2, seed=None):
67
    """Position nodes uniformly at random in the unit square.
68

69
    For every node, a position is generated by choosing each of dim
70
    coordinates uniformly at random on the interval [0.0, 1.0).
71

72
    NumPy (http://scipy.org) is required for this function.
73

74
    Parameters
75
    ----------
76
    G : NetworkX graph or list of nodes
77
        A position will be assigned to every node in G.
78

79
    center : array-like or None
80
        Coordinate pair around which to center the layout.
81

82
    dim : int
83
        Dimension of layout.
84

85
    seed : int, RandomState instance or None  optional (default=None)
86
        Set the random state for deterministic node layouts.
87
        If int, `seed` is the seed used by the random number generator,
88
        if numpy.random.RandomState instance, `seed` is the random
89
        number generator,
90
        if None, the random number generator is the RandomState instance used
91
        by numpy.random.
92

93
    Returns
94
    -------
95
    pos : dict
96
        A dictionary of positions keyed by node
97

98
    Examples
99
    --------
100
    >>> G = nx.lollipop_graph(4, 3)
101
    >>> pos = nx.random_layout(G)
102

103
    """
104
    import numpy as np
105

    
106
    G, center = _process_params(G, center, dim)
107
    pos = seed.rand(len(G), dim) + center
108
    pos = pos.astype(np.float32)
109
    pos = dict(zip(G, pos))
110

    
111
    return pos
112

    
113

    
114
def circular_layout(G, scale=1, center=None, dim=2):
115
    # dim=2 only
116
    """Position nodes on a circle.
117

118
    Parameters
119
    ----------
120
    G : NetworkX graph or list of nodes
121
        A position will be assigned to every node in G.
122

123
    scale : number (default: 1)
124
        Scale factor for positions.
125

126
    center : array-like or None
127
        Coordinate pair around which to center the layout.
128

129
    dim : int
130
        Dimension of layout.
131
        If dim>2, the remaining dimensions are set to zero
132
        in the returned positions.
133
        If dim<2, a ValueError is raised.
134

135
    Returns
136
    -------
137
    pos : dict
138
        A dictionary of positions keyed by node
139

140
    Raises
141
    -------
142
    ValueError
143
        If dim < 2
144

145
    Examples
146
    --------
147
    >>> G = nx.path_graph(4)
148
    >>> pos = nx.circular_layout(G)
149

150
    Notes
151
    -----
152
    This algorithm currently only works in two dimensions and does not
153
    try to minimize edge crossings.
154

155
    """
156
    import numpy as np
157

    
158
    if dim < 2:
159
        raise ValueError('cannot handle dimensions < 2')
160

    
161
    G, center = _process_params(G, center, dim)
162

    
163
    paddims = max(0, (dim - 2))
164

    
165
    if len(G) == 0:
166
        pos = {}
167
    elif len(G) == 1:
168
        pos = {nx.utils.arbitrary_element(G): center}
169
    else:
170
        # Discard the extra angle since it matches 0 radians.
171
        theta = np.linspace(0, 1, len(G) + 1)[:-1] * 2 * np.pi
172
        theta = theta.astype(np.float32)
173
        pos = np.column_stack([np.cos(theta), np.sin(theta),
174
                               np.zeros((len(G), paddims))])
175
        pos = rescale_layout(pos, scale=scale) + center
176
        pos = dict(zip(G, pos))
177

    
178
    return pos
179

    
180

    
181
def shell_layout(G, nlist=None, scale=1, center=None, dim=2):
182
    """Position nodes in concentric circles.
183

184
    Parameters
185
    ----------
186
    G : NetworkX graph or list of nodes
187
        A position will be assigned to every node in G.
188

189
    nlist : list of lists
190
       List of node lists for each shell.
191

192
    scale : number (default: 1)
193
        Scale factor for positions.
194

195
    center : array-like or None
196
        Coordinate pair around which to center the layout.
197

198
    dim : int
199
        Dimension of layout, currently only dim=2 is supported.
200
        Other dimension values result in a ValueError.
201

202
    Returns
203
    -------
204
    pos : dict
205
        A dictionary of positions keyed by node
206

207
    Raises
208
    -------
209
    ValueError
210
        If dim != 2
211

212
    Examples
213
    --------
214
    >>> G = nx.path_graph(4)
215
    >>> shells = [[0], [1, 2, 3]]
216
    >>> pos = nx.shell_layout(G, shells)
217

218
    Notes
219
    -----
220
    This algorithm currently only works in two dimensions and does not
221
    try to minimize edge crossings.
222

223
    """
224
    import numpy as np
225

    
226
    if dim != 2:
227
        raise ValueError('can only handle 2 dimensions')
228

    
229
    G, center = _process_params(G, center, dim)
230

    
231
    if len(G) == 0:
232
        return {}
233
    if len(G) == 1:
234
        return {nx.utils.arbitrary_element(G): center}
235

    
236
    if nlist is None:
237
        # draw the whole graph in one shell
238
        nlist = [list(G)]
239

    
240
    if len(nlist[0]) == 1:
241
        # single node at center
242
        radius = 0.0
243
    else:
244
        # else start at r=1
245
        radius = 1.0
246

    
247
    npos = {}
248
    for nodes in nlist:
249
        # Discard the extra angle since it matches 0 radians.
250
        theta = np.linspace(0, 1, len(nodes) + 1)[:-1] * 2 * np.pi
251
        theta = theta.astype(np.float32)
252
        pos = np.column_stack([np.cos(theta), np.sin(theta)])
253
        pos = rescale_layout(pos, scale=scale * radius / len(nlist)) + center
254
        npos.update(zip(nodes, pos))
255
        radius += 1.0
256

    
257
    return npos
258

    
259

    
260
def bipartite_layout(G, nodes, align='vertical',
261
                     scale=1, center=None, aspect_ratio=4/3):
262
    """Position nodes in two straight lines.
263

264
    Parameters
265
    ----------
266
    G : NetworkX graph or list of nodes
267
        A position will be assigned to every node in G.
268

269
    nodes : list or container
270
        Nodes in one node set of the bipartite graph.
271
        This set will be placed on left or top.
272

273
    align : string (default='vertical')
274
        The alignment of nodes. Vertical or horizontal.
275

276
    scale : number (default: 1)
277
        Scale factor for positions.
278

279
    center : array-like or None
280
        Coordinate pair around which to center the layout.
281

282
    aspect_ratio : number (default=4/3):
283
        The ratio of the width to the height of the layout.
284

285
    Returns
286
    -------
287
    pos : dict
288
        A dictionary of positions keyed by node.
289

290
    Examples
291
    --------
292
    >>> G = nx.bipartite.gnmk_random_graph(3, 5, 10, seed=123)
293
    >>> top = nx.bipartite.sets(G)[0]
294
    >>> pos = nx.bipartite_layout(G, top)
295

296
    Notes
297
    -----
298
    This algorithm currently only works in two dimensions and does not
299
    try to minimize edge crossings.
300

301
    """
302

    
303
    import numpy as np
304

    
305
    G, center = _process_params(G, center=center, dim=2)
306
    if len(G) == 0:
307
        return {}
308

    
309
    height = 1
310
    width = aspect_ratio * height
311
    offset = (width/2, height/2)
312

    
313
    top = set(nodes)
314
    bottom = set(G) - top
315
    nodes = list(top) + list(bottom)
316

    
317
    if align == 'vertical':
318
        left_xs = np.repeat(0, len(top))
319
        right_xs = np.repeat(width, len(bottom))
320
        left_ys = np.linspace(0, height, len(top))
321
        right_ys = np.linspace(0, height, len(bottom))
322

    
323
        top_pos = np.column_stack([left_xs, left_ys]) - offset
324
        bottom_pos = np.column_stack([right_xs, right_ys]) - offset
325

    
326
        pos = np.concatenate([top_pos, bottom_pos])
327
        pos = rescale_layout(pos, scale=scale) + center
328
        pos = dict(zip(nodes, pos))
329
        return pos
330

    
331
    if align == 'horizontal':
332
        top_ys = np.repeat(height, len(top))
333
        bottom_ys = np.repeat(0, len(bottom))
334
        top_xs = np.linspace(0, width, len(top))
335
        bottom_xs = np.linspace(0, width, len(bottom))
336

    
337
        top_pos = np.column_stack([top_xs, top_ys]) - offset
338
        bottom_pos = np.column_stack([bottom_xs, bottom_ys]) - offset
339

    
340
        pos = np.concatenate([top_pos, bottom_pos])
341
        pos = rescale_layout(pos, scale=scale) + center
342
        pos = dict(zip(nodes, pos))
343
        return pos
344

    
345
    msg = 'align must be either vertical or horizontal.'
346
    raise ValueError(msg)
347

    
348

    
349
@random_state(10)
350
def fruchterman_reingold_layout(G,
351
                                k=None,
352
                                pos=None,
353
                                fixed=None,
354
                                iterations=50,
355
                                threshold=1e-4,
356
                                weight='weight',
357
                                scale=1,
358
                                center=None,
359
                                dim=2,
360
                                seed=None):
361
    """Position nodes using Fruchterman-Reingold force-directed algorithm.
362

363
    Parameters
364
    ----------
365
    G : NetworkX graph or list of nodes
366
        A position will be assigned to every node in G.
367

368
    k : float (default=None)
369
        Optimal distance between nodes.  If None the distance is set to
370
        1/sqrt(n) where n is the number of nodes.  Increase this value
371
        to move nodes farther apart.
372

373
    pos : dict or None  optional (default=None)
374
        Initial positions for nodes as a dictionary with node as keys
375
        and values as a coordinate list or tuple.  If None, then use
376
        random initial positions.
377

378
    fixed : list or None  optional (default=None)
379
        Nodes to keep fixed at initial position.
380
        ValueError raised if `fixed` specified and `pos` not.
381

382
    iterations : int  optional (default=50)
383
        Maximum number of iterations taken
384

385
    threshold: float optional (default = 1e-4)
386
        Threshold for relative error in node position changes.
387
        The iteration stops if the error is below this threshold.
388

389
    weight : string or None   optional (default='weight')
390
        The edge attribute that holds the numerical value used for
391
        the edge weight.  If None, then all edge weights are 1.
392

393
    scale : number (default: 1)
394
        Scale factor for positions. Not used unless `fixed is None`.
395

396
    center : array-like or None
397
        Coordinate pair around which to center the layout.
398
        Not used unless `fixed is None`.
399

400
    dim : int
401
        Dimension of layout.
402

403
    seed : int, RandomState instance or None  optional (default=None)
404
        Set the random state for deterministic node layouts.
405
        If int, `seed` is the seed used by the random number generator,
406
        if numpy.random.RandomState instance, `seed` is the random
407
        number generator,
408
        if None, the random number generator is the RandomState instance used
409
        by numpy.random.
410

411
    Returns
412
    -------
413
    pos : dict
414
        A dictionary of positions keyed by node
415

416
    Examples
417
    --------
418
    >>> G = nx.path_graph(4)
419
    >>> pos = nx.spring_layout(G)
420

421
    # The same using longer but equivalent function name
422
    >>> pos = nx.fruchterman_reingold_layout(G)
423
    """
424
    import numpy as np
425

    
426
    G, center = _process_params(G, center, dim)
427

    
428
    if fixed is not None:
429
        if pos is None:
430
            raise ValueError('nodes are fixed without positions given')
431
        for node in fixed:
432
            if node not in pos:
433
                raise ValueError('nodes are fixed without positions given')
434
        nfixed = {node: i for i, node in enumerate(G)}
435
        fixed = np.asarray([nfixed[node] for node in fixed])
436

    
437
    if pos is not None:
438
        # Determine size of existing domain to adjust initial positions
439
        dom_size = max(coord for pos_tup in pos.values() for coord in pos_tup)
440
        if dom_size == 0:
441
            dom_size = 1
442
        pos_arr = seed.rand(len(G), dim) * dom_size + center
443

    
444
        for i, n in enumerate(G):
445
            if n in pos:
446
                pos_arr[i] = np.asarray(pos[n])
447
    else:
448
        pos_arr = None
449
        dom_size = 1
450

    
451
    if len(G) == 0:
452
        return {}
453
    if len(G) == 1:
454
        return {nx.utils.arbitrary_element(G.nodes()): center}
455

    
456
    try:
457
        # Sparse matrix
458
        if len(G) < 500:  # sparse solver for large graphs
459
            raise ValueError
460
        A = nx.to_scipy_sparse_matrix(G, weight=weight, dtype='f')
461
        if k is None and fixed is not None:
462
            # We must adjust k by domain size for layouts not near 1x1
463
            nnodes, _ = A.shape
464
            k = dom_size / np.sqrt(nnodes)
465
        pos = _sparse_fruchterman_reingold(A, k, pos_arr, fixed,
466
                                           iterations, threshold,
467
                                           dim, seed)
468
    except:
469
        A = nx.to_numpy_array(G, weight=weight)
470
        if k is None and fixed is not None:
471
            # We must adjust k by domain size for layouts not near 1x1
472
            nnodes, _ = A.shape
473
            k = dom_size / np.sqrt(nnodes)
474
        pos = _fruchterman_reingold(A, k, pos_arr, fixed, iterations,
475
                                    threshold, dim, seed)
476
    if fixed is None:
477
        pos = rescale_layout(pos, scale=scale) + center
478
    pos = dict(zip(G, pos))
479
    return pos
480

    
481

    
482
spring_layout = fruchterman_reingold_layout
483

    
484

    
485
@random_state(7)
486
def _fruchterman_reingold(A, k=None, pos=None, fixed=None, iterations=50,
487
                          threshold=1e-4, dim=2, seed=None):
488
    # Position nodes in adjacency matrix A using Fruchterman-Reingold
489
    # Entry point for NetworkX graph is fruchterman_reingold_layout()
490
    import numpy as np
491

    
492
    try:
493
        nnodes, _ = A.shape
494
    except AttributeError:
495
        msg = "fruchterman_reingold() takes an adjacency matrix as input"
496
        raise nx.NetworkXError(msg)
497

    
498
    if pos is None:
499
        # random initial positions
500
        pos = np.asarray(seed.rand(nnodes, dim), dtype=A.dtype)
501
    else:
502
        # make sure positions are of same type as matrix
503
        pos = pos.astype(A.dtype)
504

    
505
    # optimal distance between nodes
506
    if k is None:
507
        k = np.sqrt(1.0 / nnodes)
508
    # the initial "temperature"  is about .1 of domain area (=1x1)
509
    # this is the largest step allowed in the dynamics.
510
    # We need to calculate this in case our fixed positions force our domain
511
    # to be much bigger than 1x1
512
    t = max(max(pos.T[0]) - min(pos.T[0]), max(pos.T[1]) - min(pos.T[1])) * 0.1
513
    # simple cooling scheme.
514
    # linearly step down by dt on each iteration so last iteration is size dt.
515
    dt = t / float(iterations + 1)
516
    delta = np.zeros((pos.shape[0], pos.shape[0], pos.shape[1]), dtype=A.dtype)
517
    # the inscrutable (but fast) version
518
    # this is still O(V^2)
519
    # could use multilevel methods to speed this up significantly
520
    for iteration in range(iterations):
521
        # matrix of difference between points
522
        delta = pos[:, np.newaxis, :] - pos[np.newaxis, :, :]
523
        # distance between points
524
        distance = np.linalg.norm(delta, axis=-1)
525
        # enforce minimum distance of 0.01
526
        np.clip(distance, 0.01, None, out=distance)
527
        # displacement "force"
528
        displacement = np.einsum('ijk,ij->ik',
529
                                 delta,
530
                                 (k * k / distance**2 - A * distance / k))
531
        # update positions
532
        length = np.linalg.norm(displacement, axis=-1)
533
        length = np.where(length < 0.01, 0.1, length)
534
        delta_pos = np.einsum('ij,i->ij', displacement, t / length)
535
        if fixed is not None:
536
            # don't change positions of fixed nodes
537
            delta_pos[fixed] = 0.0
538
        pos += delta_pos
539
        # cool temperature
540
        t -= dt
541
        err = np.linalg.norm(delta_pos) / nnodes
542
        if err < threshold:
543
            break
544
    return pos
545

    
546

    
547
@random_state(7)
548
def _sparse_fruchterman_reingold(A, k=None, pos=None, fixed=None,
549
                                 iterations=50, threshold=1e-4, dim=2,
550
                                 seed=None):
551
    # Position nodes in adjacency matrix A using Fruchterman-Reingold
552
    # Entry point for NetworkX graph is fruchterman_reingold_layout()
553
    # Sparse version
554
    import numpy as np
555

    
556
    try:
557
        nnodes, _ = A.shape
558
    except AttributeError:
559
        msg = "fruchterman_reingold() takes an adjacency matrix as input"
560
        raise nx.NetworkXError(msg)
561
    try:
562
        from scipy.sparse import spdiags, coo_matrix
563
    except ImportError:
564
        msg = "_sparse_fruchterman_reingold() scipy numpy: http://scipy.org/ "
565
        raise ImportError(msg)
566
    # make sure we have a LIst of Lists representation
567
    try:
568
        A = A.tolil()
569
    except:
570
        A = (coo_matrix(A)).tolil()
571

    
572
    if pos is None:
573
        # random initial positions
574
        pos = np.asarray(seed.rand(nnodes, dim), dtype=A.dtype)
575
    else:
576
        # make sure positions are of same type as matrix
577
        pos = pos.astype(A.dtype)
578

    
579
    # no fixed nodes
580
    if fixed is None:
581
        fixed = []
582

    
583
    # optimal distance between nodes
584
    if k is None:
585
        k = np.sqrt(1.0 / nnodes)
586
    # the initial "temperature"  is about .1 of domain area (=1x1)
587
    # this is the largest step allowed in the dynamics.
588
    t = max(max(pos.T[0]) - min(pos.T[0]), max(pos.T[1]) - min(pos.T[1])) * 0.1
589
    # simple cooling scheme.
590
    # linearly step down by dt on each iteration so last iteration is size dt.
591
    dt = t / float(iterations + 1)
592

    
593
    displacement = np.zeros((dim, nnodes))
594
    for iteration in range(iterations):
595
        displacement *= 0
596
        # loop over rows
597
        for i in range(A.shape[0]):
598
            if i in fixed:
599
                continue
600
            # difference between this row's node position and all others
601
            delta = (pos[i] - pos).T
602
            # distance between points
603
            distance = np.sqrt((delta**2).sum(axis=0))
604
            # enforce minimum distance of 0.01
605
            distance = np.where(distance < 0.01, 0.01, distance)
606
            # the adjacency matrix row
607
            Ai = np.asarray(A.getrowview(i).toarray())
608
            # displacement "force"
609
            displacement[:, i] +=\
610
                (delta * (k * k / distance**2 - Ai * distance / k)).sum(axis=1)
611
        # update positions
612
        length = np.sqrt((displacement**2).sum(axis=0))
613
        length = np.where(length < 0.01, 0.1, length)
614
        delta_pos = (displacement * t / length).T
615
        pos += delta_pos
616
        # cool temperature
617
        t -= dt
618
        err = np.linalg.norm(delta_pos) / nnodes
619
        if err < threshold:
620
            break
621
    return pos
622

    
623

    
624
def kamada_kawai_layout(G, dist=None,
625
                        pos=None,
626
                        weight='weight',
627
                        scale=1,
628
                        center=None,
629
                        dim=2):
630
    """Position nodes using Kamada-Kawai path-length cost-function.
631

632
    Parameters
633
    ----------
634
    G : NetworkX graph or list of nodes
635
        A position will be assigned to every node in G.
636

637
    dist : float (default=None)
638
        A two-level dictionary of optimal distances between nodes,
639
        indexed by source and destination node.
640
        If None, the distance is computed using shortest_path_length().
641

642
    pos : dict or None  optional (default=None)
643
        Initial positions for nodes as a dictionary with node as keys
644
        and values as a coordinate list or tuple.  If None, then use
645
        circular_layout() for dim >= 2 and a linear layout for dim == 1.
646

647
    weight : string or None   optional (default='weight')
648
        The edge attribute that holds the numerical value used for
649
        the edge weight.  If None, then all edge weights are 1.
650

651
    scale : number (default: 1)
652
        Scale factor for positions.
653

654
    center : array-like or None
655
        Coordinate pair around which to center the layout.
656

657
    dim : int
658
        Dimension of layout.
659

660
    Returns
661
    -------
662
    pos : dict
663
        A dictionary of positions keyed by node
664

665
    Examples
666
    --------
667
    >>> G = nx.path_graph(4)
668
    >>> pos = nx.kamada_kawai_layout(G)
669
    """
670
    import numpy as np
671

    
672
    G, center = _process_params(G, center, dim)
673
    nNodes = len(G)
674

    
675
    if dist is None:
676
        dist = dict(nx.shortest_path_length(G, weight=weight))
677
    dist_mtx = 1e6 * np.ones((nNodes, nNodes))
678
    for row, nr in enumerate(G):
679
        if nr not in dist:
680
            continue
681
        rdist = dist[nr]
682
        for col, nc in enumerate(G):
683
            if nc not in rdist:
684
                continue
685
            dist_mtx[row][col] = rdist[nc]
686

    
687
    if pos is None:
688
        if dim >= 2:
689
            pos = circular_layout(G, dim=dim)
690
        else:
691
            pos = {n: pt for n, pt in zip(G, np.linspace(0, 1, len(G)))}
692
    pos_arr = np.array([pos[n] for n in G])
693

    
694
    pos = _kamada_kawai_solve(dist_mtx, pos_arr, dim)
695

    
696
    pos = rescale_layout(pos, scale=scale) + center
697
    return dict(zip(G, pos))
698

    
699

    
700
def _kamada_kawai_solve(dist_mtx, pos_arr, dim):
701
    # Anneal node locations based on the Kamada-Kawai cost-function,
702
    # using the supplied matrix of preferred inter-node distances,
703
    # and starting locations.
704

    
705
    import numpy as np
706
    from scipy.optimize import minimize
707

    
708
    meanwt = 1e-3
709
    costargs = (np, 1 / (dist_mtx + np.eye(dist_mtx.shape[0]) * 1e-3),
710
                meanwt, dim)
711

    
712
    optresult = minimize(_kamada_kawai_costfn, pos_arr.ravel(),
713
                         method='L-BFGS-B', args=costargs, jac=True)
714

    
715
    return optresult.x.reshape((-1, dim))
716

    
717

    
718
def _kamada_kawai_costfn(pos_vec, np, invdist, meanweight, dim):
719
    # Cost-function and gradient for Kamada-Kawai layout algorithm
720
    nNodes = invdist.shape[0]
721
    pos_arr = pos_vec.reshape((nNodes, dim))
722

    
723
    delta = pos_arr[:, np.newaxis, :] - pos_arr[np.newaxis, :, :]
724
    nodesep = np.linalg.norm(delta, axis=-1)
725
    direction = np.einsum('ijk,ij->ijk',
726
                          delta,
727
                          1 / (nodesep + np.eye(nNodes) * 1e-3))
728

    
729
    offset = nodesep * invdist - 1.0
730
    offset[np.diag_indices(nNodes)] = 0
731

    
732
    cost = 0.5 * np.sum(offset ** 2)
733
    grad = (np.einsum('ij,ij,ijk->ik', invdist, offset, direction) -
734
            np.einsum('ij,ij,ijk->jk', invdist, offset, direction))
735

    
736
    # Additional parabolic term to encourage mean position to be near origin:
737
    sumpos = np.sum(pos_arr, axis=0)
738
    cost += 0.5 * meanweight * np.sum(sumpos ** 2)
739
    grad += meanweight * sumpos
740

    
741
    return (cost, grad.ravel())
742

    
743

    
744
def spectral_layout(G, weight='weight', scale=1, center=None, dim=2):
745
    """Position nodes using the eigenvectors of the graph Laplacian.
746

747
    Using the unnormalized Laplacion, the layout shows possible clusters of
748
    nodes which are an approximation of the ratio cut. If dim is the number of
749
    dimensions then the positions are the entries of the dim eigenvectors
750
    corresponding to the ascending eigenvalues starting from the second one.
751

752
    Parameters
753
    ----------
754
    G : NetworkX graph or list of nodes
755
        A position will be assigned to every node in G.
756

757
    weight : string or None   optional (default='weight')
758
        The edge attribute that holds the numerical value used for
759
        the edge weight.  If None, then all edge weights are 1.
760

761
    scale : number (default: 1)
762
        Scale factor for positions.
763

764
    center : array-like or None
765
        Coordinate pair around which to center the layout.
766

767
    dim : int
768
        Dimension of layout.
769

770
    Returns
771
    -------
772
    pos : dict
773
        A dictionary of positions keyed by node
774

775
    Examples
776
    --------
777
    >>> G = nx.path_graph(4)
778
    >>> pos = nx.spectral_layout(G)
779

780
    Notes
781
    -----
782
    Directed graphs will be considered as undirected graphs when
783
    positioning the nodes.
784

785
    For larger graphs (>500 nodes) this will use the SciPy sparse
786
    eigenvalue solver (ARPACK).
787
    """
788
    # handle some special cases that break the eigensolvers
789
    import numpy as np
790

    
791
    G, center = _process_params(G, center, dim)
792

    
793
    if len(G) <= 2:
794
        if len(G) == 0:
795
            pos = np.array([])
796
        elif len(G) == 1:
797
            pos = np.array([center])
798
        else:
799
            pos = np.array([np.zeros(dim), np.array(center) * 2.0])
800
        return dict(zip(G, pos))
801
    try:
802
        # Sparse matrix
803
        if len(G) < 500:  # dense solver is faster for small graphs
804
            raise ValueError
805
        A = nx.to_scipy_sparse_matrix(G, weight=weight, dtype='d')
806
        # Symmetrize directed graphs
807
        if G.is_directed():
808
            A = A + np.transpose(A)
809
        pos = _sparse_spectral(A, dim)
810
    except (ImportError, ValueError):
811
        # Dense matrix
812
        A = nx.to_numpy_array(G, weight=weight)
813
        # Symmetrize directed graphs
814
        if G.is_directed():
815
            A += A.T
816
        pos = _spectral(A, dim)
817

    
818
    pos = rescale_layout(pos, scale) + center
819
    pos = dict(zip(G, pos))
820
    return pos
821

    
822

    
823
def _spectral(A, dim=2):
824
    # Input adjacency matrix A
825
    # Uses dense eigenvalue solver from numpy
826
    import numpy as np
827

    
828
    try:
829
        nnodes, _ = A.shape
830
    except AttributeError:
831
        msg = "spectral() takes an adjacency matrix as input"
832
        raise nx.NetworkXError(msg)
833

    
834
    # form Laplacian matrix
835
    I = np.identity(nnodes, dtype=A.dtype)
836
    D = I * np.sum(A, axis=1)  # diagonal of degrees
837
    L = D - A
838

    
839
    eigenvalues, eigenvectors = np.linalg.eig(L)
840
    # sort and keep smallest nonzero
841
    index = np.argsort(eigenvalues)[1:dim + 1]  # 0 index is zero eigenvalue
842
    return np.real(eigenvectors[:, index])
843

    
844

    
845
def _sparse_spectral(A, dim=2):
846
    # Input adjacency matrix A
847
    # Uses sparse eigenvalue solver from scipy
848
    # Could use multilevel methods here, see Koren "On spectral graph drawing"
849
    import numpy as np
850
    from scipy.sparse import spdiags
851
    from scipy.sparse.linalg.eigen import eigsh
852

    
853
    try:
854
        nnodes, _ = A.shape
855
    except AttributeError:
856
        msg = "sparse_spectral() takes an adjacency matrix as input"
857
        raise nx.NetworkXError(msg)
858

    
859
    # form Laplacian matrix
860
    data = np.asarray(A.sum(axis=1).T)
861
    D = spdiags(data, 0, nnodes, nnodes)
862
    L = D - A
863

    
864
    k = dim + 1
865
    # number of Lanczos vectors for ARPACK solver.What is the right scaling?
866
    ncv = max(2 * k + 1, int(np.sqrt(nnodes)))
867
    # return smallest k eigenvalues and eigenvectors
868
    eigenvalues, eigenvectors = eigsh(L, k, which='SM', ncv=ncv)
869
    index = np.argsort(eigenvalues)[1:k]  # 0 index is zero eigenvalue
870
    return np.real(eigenvectors[:, index])
871

    
872

    
873
def planar_layout(G, scale=1, center=None, dim=2):
874
    """Position nodes without edge intersections.
875

876
    Parameters
877
    ----------
878
    G : NetworkX graph or list of nodes
879
        A position will be assigned to every node in G. If G is of type
880
        PlanarEmbedding, the positions are selected accordingly.
881

882
    Parameters
883
    ----------
884
    G : NetworkX graph or list of nodes
885
        A position will be assigned to every node in G. If G is of type
886
        nx.PlanarEmbedding, the positions are selected accordingly.
887

888
    scale : number (default: 1)
889
        Scale factor for positions.
890

891
    center : array-like or None
892
        Coordinate pair around which to center the layout.
893

894
    dim : int
895
        Dimension of layout.
896

897
    Returns
898
    -------
899
    pos : dict
900
        A dictionary of positions keyed by node
901

902
    Raises
903
    ------
904
    nx.NetworkXException
905
        If G is not planar
906

907
    Examples
908
    --------
909
    >>> G = nx.path_graph(4)
910
    >>> pos = nx.planar_layout(G)
911
    """
912
    import numpy as np
913

    
914
    if dim != 2:
915
        raise ValueError('can only handle 2 dimensions')
916

    
917
    G, center = _process_params(G, center, dim)
918

    
919
    if len(G) == 0:
920
        return {}
921

    
922
    if isinstance(G, nx.PlanarEmbedding):
923
        embedding = G
924
    else:
925
        is_planar, embedding = nx.check_planarity(G)
926
        if not is_planar:
927
            raise nx.NetworkXException("G is not planar.")
928
    pos = nx.combinatorial_embedding_to_pos(embedding)
929
    node_list = list(embedding)
930
    pos = np.row_stack((pos[x] for x in node_list))
931
    pos = pos.astype(np.float64)
932
    pos = rescale_layout(pos, scale=scale) + center
933
    return dict(zip(node_list, pos))
934

    
935

    
936
def rescale_layout(pos, scale=1):
937
    """Returns scaled position array to (-scale, scale) in all axes.
938

939
    The function acts on NumPy arrays which hold position information.
940
    Each position is one row of the array. The dimension of the space
941
    equals the number of columns. Each coordinate in one column.
942

943
    To rescale, the mean (center) is subtracted from each axis separately.
944
    Then all values are scaled so that the largest magnitude value
945
    from all axes equals `scale` (thus, the aspect ratio is preserved).
946
    The resulting NumPy Array is returned (order of rows unchanged).
947

948
    Parameters
949
    ----------
950
    pos : numpy array
951
        positions to be scaled. Each row is a position.
952

953
    scale : number (default: 1)
954
        The size of the resulting extent in all directions.
955

956
    Returns
957
    -------
958
    pos : numpy array
959
        scaled positions. Each row is a position.
960

961
    """
962
    # Find max length over all dimensions
963
    lim = 0  # max coordinate for all axes
964
    for i in range(pos.shape[1]):
965
        pos[:, i] -= pos[:, i].mean()
966
        lim = max(abs(pos[:, i]).max(), lim)
967
    # rescale to (-scale, scale) in all directions, preserves aspect
968
    if lim > 0:
969
        for i in range(pos.shape[1]):
970
            pos[:, i] *= scale / lim
971
    return pos
972

    
973

    
974
# fixture for nose tests
975
def setup_module(module):
976
    from nose import SkipTest
977
    try:
978
        import numpy
979
    except:
980
        raise SkipTest("NumPy not available")
981
    try:
982
        import scipy
983
    except:
984
        raise SkipTest("SciPy not available")