__init__.py 30.4 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
#! /usr/bin/env python
2
# -*- coding: utf-8 -*-
Tiago Peixoto's avatar
Tiago Peixoto committed
3
#
4
5
# graph_tool -- a general graph manipulation python module
#
Tiago Peixoto's avatar
Tiago Peixoto committed
6
# Copyright (C) 2006-2020 Tiago de Paula Peixoto <tiago@skewed.de>
Tiago Peixoto's avatar
Tiago Peixoto committed
7
#
8
9
10
11
# This program is free software; you can redistribute it and/or modify it under
# the terms of the GNU Lesser General Public License as published by the Free
# Software Foundation; either version 3 of the License, or (at your option) any
# later version.
Tiago Peixoto's avatar
Tiago Peixoto committed
12
#
13
14
15
16
# This program is distributed in the hope that it will be useful, but WITHOUT
# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
# FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
# details.
Tiago Peixoto's avatar
Tiago Peixoto committed
17
#
18
19
# You should have received a copy of the GNU Lesser General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
Tiago Peixoto's avatar
Tiago Peixoto committed
20

21
"""
22
23
``graph_tool.draw`` - Graph drawing and layout
----------------------------------------------
24
25
26
27

Summary
+++++++

28
29
30
Layout algorithms
=================

31
32
33
.. autosummary::
   :nosignatures:

Tiago Peixoto's avatar
Tiago Peixoto committed
34
   sfdp_layout
35
   fruchterman_reingold_layout
36
   arf_layout
Tiago Peixoto's avatar
Tiago Peixoto committed
37
   radial_tree_layout
Tiago Peixoto's avatar
Tiago Peixoto committed
38
   planar_layout
39
   random_layout
40
41
42
43
44
45
46
47

Graph drawing
=============

.. autosummary::
   :nosignatures:

   graph_draw
48
   draw_hierarchy
Tiago Peixoto's avatar
Tiago Peixoto committed
49
   graphviz_draw
50
   prop_to_size
51
   get_hierarchy_control_points
52

53
54
55
56
57
58
59
60
61
62
63
64

Low-level graph drawing
^^^^^^^^^^^^^^^^^^^^^^^

.. autosummary::
   :nosignatures:

   cairo_draw
   interactive_window
   GraphWidget
   GraphWindow

65
66
Contents
++++++++
67
68
"""

69
70
71
from .. import Graph, GraphView, _check_prop_vector, _check_prop_scalar, \
    group_vector_property, ungroup_vector_property, infect_vertex_property, \
    _prop, _get_rng
Tiago Peixoto's avatar
Tiago Peixoto committed
72
from .. topology import max_cardinality_matching, max_independent_vertex_set, \
Alex Henrie's avatar
Alex Henrie committed
73
    label_components, shortest_distance, make_maximal_planar, is_planar
74
from .. generation import predecessor_tree, condensation_graph
Tiago Peixoto's avatar
Tiago Peixoto committed
75
76
import numpy.random
from numpy import sqrt
77
78

from .. dl_import import dl_import
79
dl_import("from . import libgraph_tool_layout")
80

81

Tiago Peixoto's avatar
Tiago Peixoto committed
82
__all__ = ["graph_draw", "graphviz_draw", "fruchterman_reingold_layout",
Tiago Peixoto's avatar
Tiago Peixoto committed
83
84
           "arf_layout", "sfdp_layout", "planar_layout", "random_layout",
           "radial_tree_layout", "cairo_draw", "prop_to_size",
85
           "get_hierarchy_control_points", "default_cm", "default_clrs"]
86

Tiago Peixoto's avatar
Tiago Peixoto committed
87

88
def random_layout(g, shape=None, pos=None, dim=2):
89
90
91
92
    r"""Performs a random layout of the graph.

    Parameters
    ----------
93
    g : :class:`~graph_tool.Graph`
94
        Graph to be used.
95
    shape : tuple or list (optional, default: ``None``)
Tiago Peixoto's avatar
Tiago Peixoto committed
96
97
98
99
        Rectangular shape of the bounding area. The size of this parameter must
        match `dim`, and each element can be either a pair specifying a range,
        or a single value specifying a range starting from zero. If None is
        passed, a square of linear size :math:`\sqrt{N}` is used.
100
    pos : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
101
        Vector vertex property maps where the coordinates should be stored.
102
    dim : int (optional, default: ``2``)
103
104
105
106
        Number of coordinates per vertex.

    Returns
    -------
107
    pos : :class:`~graph_tool.VertexPropertyMap`
108
109
        A vector-valued vertex property map with the coordinates of the
        vertices.
110
111
112
113

    Notes
    -----
    This algorithm has complexity :math:`O(V)`.
Tiago Peixoto's avatar
Tiago Peixoto committed
114
115
116

    Examples
    --------
117
118
119
120
121
122
    .. testcode::
       :hide:

       np.random.seed(42)
       gt.seed_rng(42)

Tiago Peixoto's avatar
Tiago Peixoto committed
123
124
125
126
    >>> g = gt.random_graph(100, lambda: (3, 3))
    >>> shape = [[50, 100], [1, 2], 4]
    >>> pos = gt.random_layout(g, shape=shape, dim=3)
    >>> pos[g.vertex(0)].a
Tiago Peixoto's avatar
Tiago Peixoto committed
127
    array([68.72700594,  1.03142919,  2.56812658])
Tiago Peixoto's avatar
Tiago Peixoto committed
128

129
130
    """

131
    if pos is None:
Tiago Peixoto's avatar
Tiago Peixoto committed
132
133
        pos = g.new_vertex_property("vector<double>")
    _check_prop_vector(pos, name="pos")
134

135
    pos = ungroup_vector_property(pos, list(range(0, dim)))
136

137
    if shape is None:
Tiago Peixoto's avatar
Tiago Peixoto committed
138
        shape = [sqrt(g.num_vertices())] * dim
139

140
    for i in range(dim):
Tiago Peixoto's avatar
Tiago Peixoto committed
141
142
143
144
145
146
147
        if hasattr(shape[i], "__len__"):
            if len(shape[i]) != 2:
                raise ValueError("The elements of 'shape' must have size 2.")
            r = [min(shape[i]), max(shape[i])]
        else:
            r = [min(shape[i], 0), max(shape[i], 0)]
        d = r[1] - r[0]
148
149

        # deal with filtering
150
151
        p = pos[i].fa
        pos[i].fa = numpy.random.random(len(p)) * d + r[0]
152

Tiago Peixoto's avatar
Tiago Peixoto committed
153
    pos = group_vector_property(pos)
154
155
    return pos

Tiago Peixoto's avatar
Tiago Peixoto committed
156

Tiago Peixoto's avatar
Tiago Peixoto committed
157
158
159
160
161
162
163
def planar_layout(g, pos=None):
    r"""Performs a canonical layout of a planar graph.

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Planar graph to be used.
164
    pos : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
Tiago Peixoto's avatar
Tiago Peixoto committed
165
166
167
168
        Vector vertex property maps where the coordinates should be stored.

    Returns
    -------
169
    pos : :class:`~graph_tool.VertexPropertyMap`
Tiago Peixoto's avatar
Tiago Peixoto committed
170
171
172
173
174
175
176
177
178
179
180
181
182
183
        A vector-valued vertex property map with the coordinates of the
        vertices.

    Notes
    -----
    This algorithm has complexity :math:`O(V + E)`.

    Examples
    --------
    >>> g = gt.lattice([10, 10])
    >>> pos = gt.planar_layout(g)
    >>> gt.graph_draw(g, pos=pos, output="lattice-planar.pdf")
    <...>

Tiago Peixoto's avatar
Tiago Peixoto committed
184
    .. testcleanup::
Tiago Peixoto's avatar
Tiago Peixoto committed
185

Tiago Peixoto's avatar
Tiago Peixoto committed
186
       conv_png("lattice-planar.pdf")
Tiago Peixoto's avatar
Tiago Peixoto committed
187

Tiago Peixoto's avatar
Tiago Peixoto committed
188
189

    .. figure:: lattice-planar.png
Tiago Peixoto's avatar
Tiago Peixoto committed
190
        :align: center
Tiago Peixoto's avatar
Tiago Peixoto committed
191
        :width: 60%
Tiago Peixoto's avatar
Tiago Peixoto committed
192
193
194
195
196

        Straight-line drawing of planar graph (a 2D square lattice).

    References
    ----------
197
    .. [straight-line-boost] http://www.boost.org/doc/libs/release/libs/graph/doc/straight_line_drawing.html
Tiago Peixoto's avatar
Tiago Peixoto committed
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
    .. [chrobak-linear-1995] M. Chrobak, T. Payne, "A Linear-time Algorithm for
       Drawing a Planar Graph on the Grid", Information Processing Letters 54:
       241-246, (1995), :doi:`10.1016/0020-0190(95)00020-D`
    """

    if g.num_vertices() < 3:
        raise ValueError("Graph must have at least 3 vertices.")
    if not is_planar(g):
        raise ValueError("Graph is not planar.")
    u = Graph(GraphView(g, directed=False, skip_properties=True))
    make_maximal_planar(u)
    embed = is_planar(u, embedding=True)[1]
    if pos is None:
        pos = u.new_vp("vector<double>")
    make_maximal_planar(u)
    libgraph_tool_layout.planar_layout(u._Graph__graph,
                                       _prop("v", u, embed),
                                       _prop("v", u, pos))
    pos = g.own_property(pos)
    return pos


220
221
222
223
224
225
226
def fruchterman_reingold_layout(g, weight=None, a=None, r=1., scale=None,
                                circular=False, grid=True, t_range=None,
                                n_iter=100, pos=None):
    r"""Calculate the Fruchterman-Reingold spring-block layout of the graph.

    Parameters
    ----------
227
    g : :class:`~graph_tool.Graph`
228
        Graph to be used.
229
    weight : :class:`~graph_tool.EdgePropertyMap` (optional, default: ``None``)
230
231
232
233
234
235
236
        An edge property map with the respective weights.
    a : float (optional, default: :math:`V`)
        Attracting force between adjacent vertices.
    r : float (optional, default: 1.0)
        Repulsive force between vertices.
    scale : float (optional, default: :math:`\sqrt{V}`)
        Total scale of the layout (either square side or radius).
237
238
    circular : bool (optional, default: ``False``)
        If ``True``, the layout will have a circular shape. Otherwise the shape
239
        will be a square.
240
241
    grid : bool (optional, default: ``True``)
        If ``True``, the repulsive forces will only act on vertices which are on
242
        the same site on a grid. Otherwise they will act on all vertex pairs.
243
    t_range : tuple of floats (optional, default: ``(scale / 10, scale / 1000)``)
244
245
        Temperature range used in annealing. The temperature limits the
        displacement at each iteration.
246
    n_iter : int (optional, default: ``100``)
247
        Total number of iterations.
248
    pos : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
249
250
251
252
253
254
        Vector vertex property maps where the coordinates should be stored. If
        provided, this will also be used as the initial position of the
        vertices.

    Returns
    -------
255
    pos : :class:`~graph_tool.VertexPropertyMap`
256
257
        A vector-valued vertex property map with the coordinates of the
        vertices.
258
259
260
261

    Notes
    -----
    This algorithm is defined in [fruchterman-reingold]_, and has
Tiago Peixoto's avatar
Tiago Peixoto committed
262
263
    complexity :math:`O(\text{n-iter}\times V^2)` if `grid=False` or
    :math:`O(\text{n-iter}\times (V + E))` otherwise.
264
265
266

    Examples
    --------
267
268
269
270
271
272
    .. testcode::
       :hide:

       np.random.seed(42)
       gt.seed_rng(42)

273
274
    >>> g = gt.price_network(300)
    >>> pos = gt.fruchterman_reingold_layout(g, n_iter=1000)
275
    >>> gt.graph_draw(g, pos=pos, output="graph-draw-fr.pdf")
276
277
    <...>

Tiago Peixoto's avatar
Tiago Peixoto committed
278
    .. testcleanup::
279

Tiago Peixoto's avatar
Tiago Peixoto committed
280
       conv_png("graph-draw-fr.pdf")
281

Tiago Peixoto's avatar
Tiago Peixoto committed
282
283
284
    .. figure:: graph-draw-fr.png
       :align: center
       :width: 60%
285

Tiago Peixoto's avatar
Tiago Peixoto committed
286
       Fruchterman-Reingold layout of a Price network.
287
288
289
290

    References
    ----------
    .. [fruchterman-reingold] Fruchterman, Thomas M. J.; Reingold, Edward M.
291
292
       "Graph Drawing by Force-Directed Placement". Software - Practice & Experience
       (Wiley) 21 (11): 1129-1164. (1991) :doi:`10.1002/spe.4380211102`
293
294
    """

295
    if pos is None:
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
        pos = random_layout(g, dim=2)
    _check_prop_vector(pos, name="pos", floating=True)

    if a is None:
        a = float(g.num_vertices())

    if scale is None:
        scale = sqrt(g.num_vertices())

    if t_range is None:
        t_range = (scale / 10, scale / 1000)

    ug = GraphView(g, directed=False)
    libgraph_tool_layout.fruchterman_reingold_layout(ug._Graph__graph,
                                                     _prop("v", g, pos),
                                                     _prop("e", g, weight),
                                                     a, r, not circular, scale,
                                                     grid, t_range[0],
                                                     t_range[1], n_iter)
    return pos


def arf_layout(g, weight=None, d=0.5, a=10, dt=0.001, epsilon=1e-6,
319
               max_iter=1000, pos=None, dim=2):
320
321
    r"""Calculate the ARF spring-block layout of the graph.

Tiago Peixoto's avatar
Tiago Peixoto committed
322
323
324
325
    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.
326
    weight : :class:`~graph_tool.EdgePropertyMap` (optional, default: ``None``)
Tiago Peixoto's avatar
Tiago Peixoto committed
327
328
329
330
331
332
333
334
335
336
337
338
        An edge property map with the respective weights.
    d : float (optional, default: ``0.5``)
        Opposing force between vertices.
    a : float (optional, default: ``10``)
        Attracting force between adjacent vertices.
    dt : float (optional, default: ``0.001``)
        Iteration step size.
    epsilon : float (optional, default: ``1e-6``)
        Convergence criterion.
    max_iter : int (optional, default: ``1000``)
        Maximum number of iterations. If this value is ``0``, it runs until
        convergence.
339
    pos : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
Tiago Peixoto's avatar
Tiago Peixoto committed
340
341
342
        Vector vertex property maps where the coordinates should be stored.
    dim : int (optional, default: ``2``)
        Number of coordinates per vertex.
Tiago Peixoto's avatar
Tiago Peixoto committed
343
344
345

    Returns
    -------
346
    pos : :class:`~graph_tool.VertexPropertyMap`
Tiago Peixoto's avatar
Tiago Peixoto committed
347
348
349
350
351
352
353
354
355
356
        A vector-valued vertex property map with the coordinates of the
        vertices.

    Notes
    -----
    This algorithm is defined in [geipel-self-organization-2007]_, and has
    complexity :math:`O(V^2)`.

    Examples
    --------
357
358
359
360
361
362
    .. testcode::
       :hide:

       np.random.seed(42)
       gt.seed_rng(42)

Tiago Peixoto's avatar
Tiago Peixoto committed
363
364
    >>> g = gt.price_network(300)
    >>> pos = gt.arf_layout(g, max_iter=0)
365
    >>> gt.graph_draw(g, pos=pos, output="graph-draw-arf.pdf")
Tiago Peixoto's avatar
Tiago Peixoto committed
366
367
    <...>

Tiago Peixoto's avatar
Tiago Peixoto committed
368
    .. testcleanup::
369

Tiago Peixoto's avatar
Tiago Peixoto committed
370
       conv_png("graph-draw-arf.pdf")
371

Tiago Peixoto's avatar
Tiago Peixoto committed
372
373
374
    .. figure:: graph-draw-arf.png
       :align: center
       :width: 60%
Tiago Peixoto's avatar
Tiago Peixoto committed
375

Tiago Peixoto's avatar
Tiago Peixoto committed
376
       ARF layout of a Price network.
Tiago Peixoto's avatar
Tiago Peixoto committed
377
378
379
380
381
382
383
384
385
386
387

    References
    ----------
    .. [geipel-self-organization-2007] Markus M. Geipel, "Self-Organization
       applied to Dynamic Network Layout", International Journal of Modern
       Physics C vol. 18, no. 10 (2007), pp. 1537-1549,
       :doi:`10.1142/S0129183107011558`, :arxiv:`0704.1748v5`
    .. _arf: http://www.sg.ethz.ch/research/graphlayout
    """

    if pos is None:
388
        pos = random_layout(g, dim=dim)
Tiago Peixoto's avatar
Tiago Peixoto committed
389
390
391
392
393
394
395
396
397
    _check_prop_vector(pos, name="pos", floating=True)

    ug = GraphView(g, directed=False)
    libgraph_tool_layout.arf_layout(ug._Graph__graph, _prop("v", g, pos),
                                    _prop("e", g, weight), d, a, dt, max_iter,
                                    epsilon, dim)
    return pos


398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
def _coarse_graph(g, vweight, eweight, mivs=False, groups=None):
    if groups is None:
        if mivs:
            mivs = max_independent_vertex_set(g, high_deg=True)
            u = GraphView(g, vfilt=mivs, directed=False)
            c = label_components(u)[0]
            c.fa += 1
            u = GraphView(g, directed=False)
            infect_vertex_property(u, c,
                                   list(range(1, c.fa.max() + 1)))
            c = g.own_property(c)
        else:
            mivs = None
            m = max_cardinality_matching(GraphView(g, directed=False),
                                         heuristic=True, weight=eweight,
413
                                         minimize=False, edges=True)
414
415
416
417
            u = GraphView(g, efilt=m, directed=False)
            c = label_components(u)[0]
            c = g.own_property(c)
            u = GraphView(g, directed=False)
Tiago Peixoto's avatar
Tiago Peixoto committed
418
419
    else:
        mivs = None
420
        c = groups
421
    cg, cc, vcount, ecount = condensation_graph(g, c, vweight, eweight)[:4]
Tiago Peixoto's avatar
Tiago Peixoto committed
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
    return cg, cc, vcount, ecount, c, mivs


def _propagate_pos(g, cg, c, cc, cpos, delta, mivs):
    pos = g.new_vertex_property(cpos.value_type())

    if mivs is not None:
        g = GraphView(g, vfilt=mivs)
    libgraph_tool_layout.propagate_pos(g._Graph__graph,
                                       cg._Graph__graph,
                                       _prop("v", g, c),
                                       _prop("v", cg, cc),
                                       _prop("v", g, pos),
                                       _prop("v", cg, cpos),
                                       delta if mivs is None else 0,
437
                                       _get_rng())
438

Tiago Peixoto's avatar
Tiago Peixoto committed
439
440
441
442
443
444
445
    if mivs is not None:
        g = g.base
        u = GraphView(g, directed=False)
        try:
            libgraph_tool_layout.propagate_pos_mivs(u._Graph__graph,
                                                    _prop("v", u, mivs),
                                                    _prop("v", u, pos),
446
                                                    delta, _get_rng())
Tiago Peixoto's avatar
Tiago Peixoto committed
447
448
449
450
451
452
        except ValueError:
            graph_draw(u, mivs, vertex_fillcolor=mivs)
    return pos


def _avg_edge_distance(g, pos):
453
    libgraph_tool_layout.sanitize_pos(g._Graph__graph, _prop("v", g, pos))
454
    ad = libgraph_tool_layout.avg_dist(g._Graph__graph, _prop("v", g, pos))
455
    if numpy.isnan(ad) or ad == 0:
456
457
        ad = 1.
    return ad
Tiago Peixoto's avatar
Tiago Peixoto committed
458
459
460


def coarse_graphs(g, method="hybrid", mivs_thres=0.9, ec_thres=0.75,
461
                  weighted_coarse=False, eweight=None, vweight=None,
462
                  groups=None, verbose=False):
Tiago Peixoto's avatar
Tiago Peixoto committed
463
    cg = [[g, None, None, None, None, None]]
464
465
    if weighted_coarse:
        cg[-1][2], cg[-1][3] = vweight, eweight
Tiago Peixoto's avatar
Tiago Peixoto committed
466
467
    mivs = not (method in ["hybrid", "ec"])
    while True:
468
469
        u = _coarse_graph(cg[-1][0], cg[-1][2], cg[-1][3], mivs, groups)
        groups = None
470
471
472
        thres = mivs_thres if mivs else ec_thres
        if u[0].num_vertices() >= thres * cg[-1][0].num_vertices():
            if method == "hybrid" and not mivs:
Tiago Peixoto's avatar
Tiago Peixoto committed
473
474
475
476
477
478
479
                mivs = True
            else:
                break
        if u[0].num_vertices() <= 2:
            break
        cg.append(u)
        if verbose:
480
481
482
            print("Coarse level (%s):" % ("MIVS" if mivs else "EC"), end=' ')
            print(len(cg), " num vertices:", end=' ')
            print(u[0].num_vertices())
Tiago Peixoto's avatar
Tiago Peixoto committed
483
484
485
    cg.reverse()
    Ks = []
    pos = random_layout(cg[0][0], dim=2)
486
    for i in range(len(cg)):
Tiago Peixoto's avatar
Tiago Peixoto committed
487
488
489
        if i == 0:
            u = cg[i][0]
            K = _avg_edge_distance(u, pos)
490
491
            if K == 0:
                K = 1.
Tiago Peixoto's avatar
Tiago Peixoto committed
492
493
494
495
496
497
498
499
500
501
502
503
504
            Ks.append(K)
            continue
        if weighted_coarse:
            gamma = 1.
        else:
            #u = cg[i - 1][0]
            #w = cg[i][0]
            #du = pseudo_diameter(u)[0]
            #dw = pseudo_diameter(w)[0]
            #gamma = du / float(max(dw, du))
            gamma = 0.75
        Ks.append(Ks[-1] * gamma)

505
    for i in range(len(cg)):
Tiago Peixoto's avatar
Tiago Peixoto committed
506
507
508
509
        u, cc, vcount, ecount, c, mivs = cg[i]
        yield u, pos, Ks[i], vcount, ecount

        if verbose:
510
            print("avg edge distance:", _avg_edge_distance(u, pos))
Tiago Peixoto's avatar
Tiago Peixoto committed
511
512
513

        if i < len(cg) - 1:
            if verbose:
514
515
                print("propagating...", end=' ')
                print(mivs.a.sum() if mivs is not None else "")
Tiago Peixoto's avatar
Tiago Peixoto committed
516
            pos = _propagate_pos(cg[i + 1][0], u, c, cc, pos,
517
                                 Ks[i] / 1000., mivs)
Tiago Peixoto's avatar
Tiago Peixoto committed
518

519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
def coarse_graph_stack(g, c, coarse_stack, eweight=None, vweight=None,
                       weighted_coarse=True, verbose=False):
    cg = [[g, c, None, None]]
    if weighted_coarse:
        cg[-1][2], cg[-1][3] = vweight, eweight
    for u in coarse_stack:
        c = u.vp["b"]
        vcount = u.vp["count"]
        ecount = u.ep["count"]
        cg.append((u, c, vcount, ecount))
        if verbose:
            print("Coarse level:", end=' ')
            print(len(cg), " num vertices:", end=' ')
            print(u.num_vertices())
    cg.reverse()
    Ks = []
    pos = random_layout(cg[0][0], dim=2)
    for i in range(len(cg)):
        if i == 0:
            u = cg[i][0]
            K = _avg_edge_distance(u, pos)
            if K == 0:
                K = 1.
            Ks.append(K)
            continue
        if weighted_coarse:
            gamma = 1.
        else:
            #u = cg[i - 1][0]
            #w = cg[i][0]
            #du = pseudo_diameter(u)[0]
            #dw = pseudo_diameter(w)[0]
            #gamma = du / float(max(dw, du))
            gamma = 0.75
        Ks.append(Ks[-1] * gamma)

    for i in range(len(cg)):
        u, c, vcount, ecount = cg[i]
        yield u, pos, Ks[i], vcount, ecount

        if verbose:
            print("avg edge distance:", _avg_edge_distance(u, pos))

        if i < len(cg) - 1:
            if verbose:
                print("propagating...")
            pos = _propagate_pos(cg[i + 1][0], u, c, u.vertex_index.copy("int"),
                                 pos, Ks[i] / 1000., None)

Tiago Peixoto's avatar
Tiago Peixoto committed
568

569
def sfdp_layout(g, vweight=None, eweight=None, pin=None, groups=None, C=0.2,
570
                K=None, p=2., theta=0.6, max_level=15, gamma=1., mu=0., mu_p=1.,
571
                init_step=None, cooling_step=0.95, adaptive_cooling=True,
572
                epsilon=1e-2, max_iter=0, pos=None, multilevel=None,
573
574
                coarse_method="hybrid", mivs_thres=0.9, ec_thres=0.75,
                coarse_stack=None, weighted_coarse=False, verbose=False):
575
    r"""Obtain the SFDP spring-block layout of the graph.
Tiago Peixoto's avatar
Tiago Peixoto committed
576

577
578
    Parameters
    ----------
579
    g : :class:`~graph_tool.Graph`
580
        Graph to be used.
581
    vweight : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
582
        A vertex property map with the respective weights.
583
    eweight : :class:`~graph_tool.EdgePropertyMap` (optional, default: ``None``)
584
        An edge property map with the respective weights.
585
    pin : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
586
587
        A vertex property map with boolean values, which, if given,
        specify the vertices which will not have their positions modified.
588
    groups : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
589
590
        A vertex property map with group assignments. Vertices belonging to the
        same group will be put close together.
591
592
593
594
595
596
597
598
    C : float (optional, default: ``0.2``)
        Relative strength of repulsive forces.
    K : float (optional, default: ``None``)
        Optimal edge length. If not provided, it will be taken to be the average
        edge distance in the initial layout.
    p : float (optional, default: ``2``)
        Repulsive force exponent.
    theta : float (optional, default: ``0.6``)
599
        Quadtree opening parameter, a.k.a. Barnes-Hut opening criterion.
600
    max_level : int (optional, default: ``15``)
601
602
        Maximum quadtree level.
    gamma : float (optional, default: ``1.0``)
603
604
605
606
607
608
609
610
        Strength of the attractive force between connected components, or group
        assignments.
    mu : float (optional, default: ``0.0``)
        Strength of the attractive force between vertices of the same connected
        component, or group assignment.
    mu_p : float (optional, default: ``1.0``)
        Scaling exponent of the attractive force between vertices of the same
        connected component, or group assignment.
611
612
    init_step : float (optional, default: ``None``)
        Initial update step. If not provided, it will be chosen automatically.
613
    cooling_step : float (optional, default: ``0.95``)
614
615
616
        Cooling update step.
    adaptive_cooling : bool (optional, default: ``True``)
        Use an adaptive cooling scheme.
617
    epsilon : float (optional, default: ``0.01``)
618
619
        Relative convergence criterion.
    max_iter : int (optional, default: ``0``)
620
        Maximum number of iterations. If this value is ``0``, it runs until
621
        convergence.
622
    pos : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
        Initial vertex layout. If not provided, it will be randomly chosen.
    multilevel : bool (optional, default: ``None``)
        Use a multilevel layout algorithm. If ``None`` is given, it will be
        activated based on the size of the graph.
    coarse_method : str (optional, default: ``"hybrid"``)
        Coarsening method used if ``multilevel == True``. Allowed methods are
        ``"hybrid"``, ``"mivs"`` and ``"ec"``.
    mivs_thres : float (optional, default: ``0.9``)
        If the relative size of the MIVS coarse graph is above this value, the
        coarsening stops.
    ec_thres : float (optional, default: ``0.75``)
        If the relative size of the EC coarse graph is above this value, the
        coarsening stops.
    weighted_coarse : bool (optional, default: ``False``)
        Use weighted coarse graphs.
    verbose : bool (optional, default: ``False``)
        Provide verbose information.
640
641
642

    Returns
    -------
643
    pos : :class:`~graph_tool.VertexPropertyMap`
644
645
        A vector-valued vertex property map with the coordinates of the
        vertices.
646
647
648

    Notes
    -----
649
650
    This algorithm is defined in [hu-multilevel-2005]_, and has
    complexity :math:`O(V\log V)`.
651
652
653

    Examples
    --------
654
655
656
657
658
659
    .. testcode::
       :hide:

       np.random.seed(42)
       gt.seed_rng(42)

660
661
662
    >>> g = gt.price_network(3000)
    >>> pos = gt.sfdp_layout(g)
    >>> gt.graph_draw(g, pos=pos, output="graph-draw-sfdp.pdf")
663
664
    <...>

Tiago Peixoto's avatar
Tiago Peixoto committed
665
    .. testcleanup::
666

Tiago Peixoto's avatar
Tiago Peixoto committed
667
       conv_png("graph-draw-sfdp.pdf")
668

Tiago Peixoto's avatar
Tiago Peixoto committed
669
670
671
    .. figure:: graph-draw-sfdp.png
       :align: center
       :width: 60%
672

Tiago Peixoto's avatar
Tiago Peixoto committed
673
       SFDP layout of a Price network.
674
675
676

    References
    ----------
677
678
679
    .. [hu-multilevel-2005] Yifan Hu, "Efficient and High Quality Force-Directed
       Graph", Mathematica Journal, vol. 10, Issue 1, pp. 37-71, (2005)
       http://www.mathematica-journal.com/issue/v10i1/graph_draw.html
680
681
    """

682
    if pos is None:
Tiago Peixoto's avatar
Tiago Peixoto committed
683
        pos = random_layout(g, dim=2)
684
    _check_prop_vector(pos, name="pos", floating=True)
685
686
    if groups is not None:
        _check_prop_scalar(groups, name="groups", floating=False)
687

688
    g_ = g
Tiago Peixoto's avatar
Tiago Peixoto committed
689
690
    g = GraphView(g, directed=False)

691
692
693
694
695
    if pin is not None:
        if pin.value_type() != "bool":
            raise ValueError("'pin' property must be of type 'bool'.")
    else:
        pin = g.new_vertex_property("bool")
Tiago Peixoto's avatar
Tiago Peixoto committed
696
697

    if K is None:
Tiago Peixoto's avatar
Tiago Peixoto committed
698
        K = _avg_edge_distance(g, pos)
Tiago Peixoto's avatar
Tiago Peixoto committed
699
700

    if init_step is None:
701
        init_step = 2 * max(_avg_edge_distance(g, pos), K)
Tiago Peixoto's avatar
Tiago Peixoto committed
702
703
704
705
706

    if multilevel is None:
        multilevel = g.num_vertices() > 1000

    if multilevel:
707
708
        if eweight is not None or vweight is not None:
            weighted_coarse = True
709
710
711
712
713
714
715
716
717
718
719
720
721
        if coarse_stack is None:
            cgs = coarse_graphs(g, method=coarse_method,
                                mivs_thres=mivs_thres,
                                ec_thres=ec_thres,
                                weighted_coarse=weighted_coarse,
                                eweight=eweight,
                                vweight=vweight,
                                groups=groups,
                                verbose=verbose)
        else:
            cgs = coarse_graph_stack(g, coarse_stack[0], coarse_stack[1],
                                     eweight=eweight, vweight=vweight,
                                     verbose=verbose)
722
        for count, (u, pos, K, vcount, ecount) in enumerate(cgs):
Tiago Peixoto's avatar
Tiago Peixoto committed
723
            if verbose:
724
725
                print("Positioning level:", count, u.num_vertices(), end=' ')
                print("with K =", K, "...")
Tiago Peixoto's avatar
Tiago Peixoto committed
726
727
728
729
                count += 1
            pos = sfdp_layout(u, pos=pos,
                              vweight=vcount if weighted_coarse else None,
                              eweight=ecount if weighted_coarse else None,
730
                              groups=None if u.num_vertices() < g.num_vertices() else groups,
Tiago Peixoto's avatar
Tiago Peixoto committed
731
                              C=C, K=K, p=p,
732
733
                              theta=theta, gamma=gamma, mu=mu, mu_p=mu_p,
                              epsilon=epsilon,
Tiago Peixoto's avatar
Tiago Peixoto committed
734
735
736
                              max_iter=max_iter,
                              cooling_step=cooling_step,
                              adaptive_cooling=False,
737
738
                              # init_step=max(2 * K,
                              #               _avg_edge_distance(u, pos)),
Tiago Peixoto's avatar
Tiago Peixoto committed
739
740
                              multilevel=False,
                              verbose=False)
741
        pos = g_.own_property(pos)
Tiago Peixoto's avatar
Tiago Peixoto committed
742
743
744
745
746
747
748
749
750
751
752
        return pos

    if g.num_vertices() <= 1:
        return pos
    if g.num_vertices() == 2:
        vs = [g.vertex(0, False), g.vertex(1, False)]
        pos[vs[0]] = [0, 0]
        pos[vs[1]] = [1, 1]
        return pos
    if g.num_vertices() <= 50:
        max_level = 0
753
754
755
756
    if groups is None:
        groups = label_components(g)[0]
    elif groups.value_type() != "int32_t":
        raise ValueError("'groups' property must be of type 'int32_t'.")
757
    libgraph_tool_layout.sanitize_pos(g._Graph__graph, _prop("v", g, pos))
Tiago Peixoto's avatar
Tiago Peixoto committed
758
759
760
    libgraph_tool_layout.sfdp_layout(g._Graph__graph, _prop("v", g, pos),
                                     _prop("v", g, vweight),
                                     _prop("e", g, eweight),
761
                                     _prop("v", g, pin),
762
                                     (C, K, p, gamma, mu, mu_p, _prop("v", g, groups)),
763
                                     theta, init_step, cooling_step, max_level,
Tiago Peixoto's avatar
Tiago Peixoto committed
764
                                     epsilon, max_iter, not adaptive_cooling,
765
                                     verbose, _get_rng())
766
    pos = g_.own_property(pos)
767
    return pos
Tiago Peixoto's avatar
Tiago Peixoto committed
768

769
770
def radial_tree_layout(g, root, rel_order=None, rel_order_leaf=False,
                       weighted=False, node_weight=None, r=1.):
Tiago Peixoto's avatar
Tiago Peixoto committed
771
772
773
774
775
776
777
778
779
    r"""Computes a radial layout of the graph according to the minimum spanning
    tree centered at the ``root`` vertex.

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.
    root : :class:`~graph_tool.Vertex` or ``int``
        The root of the radial tree.
780
    rel_order : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
781
        Relative order of the nodes at each respective branch.
782
783
784
    rel_order_leaf : ``bool`` (optional, default: ``False``)
        If ``True``, the relative order of the leafs will propagate to the
        root. Otherwise they will propagate in the opposite direction.
Tiago Peixoto's avatar
Tiago Peixoto committed
785
786
787
    weighted : ``bool`` (optional, default: ``False``)
        If true, the angle between the child branches will be computed according
        to weight of the entire sub-branches.
788
    node_weight : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
789
790
        If given, the relative spacing between leafs will correspond to the node
        weights.
Tiago Peixoto's avatar
Tiago Peixoto committed
791
792
793
794
795
    r : ``float`` (optional, default: ``1.``)
        Layer spacing.

    Returns
    -------
796
    pos : :class:`~graph_tool.VertexPropertyMap`
Tiago Peixoto's avatar
Tiago Peixoto committed
797
798
799
800
801
        A vector-valued vertex property map with the coordinates of the
        vertices.

    Notes
    -----
802
803
    This algorithm has complexity :math:`O(V + E)`, or :math:`O(V\log V + E)` if
    ``rel_order`` is given.
Tiago Peixoto's avatar
Tiago Peixoto committed
804
805
806
807
808
809
810
811
812
813
814
815
816
817

    Examples
    --------
    .. testcode::
       :hide:

       np.random.seed(42)
       gt.seed_rng(42)

    >>> g = gt.price_network(1000)
    >>> pos = gt.radial_tree_layout(g, g.vertex(0))
    >>> gt.graph_draw(g, pos=pos, output="graph-draw-radial.pdf")
    <...>

Tiago Peixoto's avatar
Tiago Peixoto committed
818
    .. testcleanup::
Tiago Peixoto's avatar
Tiago Peixoto committed
819

Tiago Peixoto's avatar
Tiago Peixoto committed
820
       conv_png("graph-draw-radial.pdf")
Tiago Peixoto's avatar
Tiago Peixoto committed
821

Tiago Peixoto's avatar
Tiago Peixoto committed
822
823
824
    .. figure:: graph-draw-radial.png
       :align: center
       :width: 60%
Tiago Peixoto's avatar
Tiago Peixoto committed
825

Tiago Peixoto's avatar
Tiago Peixoto committed
826
       Radial tree layout of a Price network.
Tiago Peixoto's avatar
Tiago Peixoto committed
827
828
829
830
831
832
833
834

    """

    levels, pred_map = shortest_distance(GraphView(g, directed=False), root,
                                         pred_map=True)
    t = predecessor_tree(g, pred_map)
    pos = t.new_vertex_property("vector<double>")
    levels = t.own_property(levels)
835
836
    if rel_order is None:
        rel_order = g.vertex_index.copy("int")
837
838
839
840
    if node_weight is None:
        node_weight = g.new_vertex_property("double", 1)
    elif node_weight.value_type() != "double":
        node_weight = node_weight.copy("double")
Tiago Peixoto's avatar
Tiago Peixoto committed
841
    libgraph_tool_layout.get_radial(t._Graph__graph,
842
843
                                    _prop("v", t, pos),
                                    _prop("v", t, levels),
844
                                    _prop("v", g, rel_order),
845
                                    _prop("v", g, node_weight),
846
847
                                    int(root), weighted, r,
                                    rel_order_leaf)
Tiago Peixoto's avatar
Tiago Peixoto committed
848
849
    return g.own_property(pos)

850
851
852
853
854
855
def prop_to_size(prop, mi=0, ma=5, log=False, power=0.5):
    r"""Convert property map values to be more useful as a vertex size, or edge
    width. The new values are taken to be

    .. math::

856
        y = mi + (ma - mi) \left(\frac{x_i - \min(x)} {\max(x) - \min(x)}\right)^\text{power}
857

858
    If ``log=True``, the natural logarithm of the property values is used instead.
859
860
861
862
863
864
865
866

    """
    prop = prop.copy(value_type="double")
    if log:
        vals = numpy.log(prop.fa)
    else:
        vals = prop.fa

867
    delta = vals.max() - vals.min()
868
869
870
871
    if delta == 0:
        delta = 1
    prop.fa = mi + (ma - mi) * ((vals - vals.min()) / delta) ** power
    return prop
872
873

try:
874
    from . cairo_draw import graph_draw, cairo_draw, \
875
876
        get_hierarchy_control_points, default_cm, default_clrs, draw_hierarchy
    __all__ += ["draw_hierarchy"]
877
878
879
880
except ImportError:
    pass

try:
881
    from . cairo_draw import GraphWidget, GraphWindow, \
882
883
        interactive_window
    __all__ += ["interactive_window", "GraphWidget", "GraphWindow"]
884
885
886
887
except ImportError:
    pass

try:
888
   from . graphviz_draw import graphviz_draw
889
890
except ImportError:
   pass