__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
12
13
14
15
16
17
18
19
20
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# 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 General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

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, \
Tiago Peixoto's avatar
Tiago Peixoto committed
73
74
    label_components, pseudo_diameter, shortest_distance, make_maximal_planar, \
    is_planar
Tiago Peixoto's avatar
Tiago Peixoto committed
75
from .. stats import label_parallel_edges
76
from .. generation import predecessor_tree, condensation_graph
Tiago Peixoto's avatar
Tiago Peixoto committed
77
78
import numpy.random
from numpy import sqrt
79
80

from .. dl_import import dl_import
81
dl_import("from . import libgraph_tool_layout")
82

83

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

Tiago Peixoto's avatar
Tiago Peixoto committed
89

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

    Parameters
    ----------
95
    g : :class:`~graph_tool.Graph`
96
        Graph to be used.
97
    shape : tuple or list (optional, default: ``None``)
Tiago Peixoto's avatar
Tiago Peixoto committed
98
99
100
101
        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.
102
    pos : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
103
        Vector vertex property maps where the coordinates should be stored.
104
    dim : int (optional, default: ``2``)
105
106
107
108
        Number of coordinates per vertex.

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

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

    Examples
    --------
119
120
121
122
123
124
    .. testcode::
       :hide:

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

Tiago Peixoto's avatar
Tiago Peixoto committed
125
126
127
128
    >>> 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
129
    array([68.72700594,  1.03142919,  2.56812658])
Tiago Peixoto's avatar
Tiago Peixoto committed
130

131
132
    """

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

137
    pos = ungroup_vector_property(pos, list(range(0, dim)))
138

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

142
    for i in range(dim):
Tiago Peixoto's avatar
Tiago Peixoto committed
143
144
145
146
147
148
149
        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]
150
151

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

Tiago Peixoto's avatar
Tiago Peixoto committed
155
    pos = group_vector_property(pos)
156
157
    return pos

Tiago Peixoto's avatar
Tiago Peixoto committed
158

Tiago Peixoto's avatar
Tiago Peixoto committed
159
160
161
162
163
164
165
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.
166
    pos : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
Tiago Peixoto's avatar
Tiago Peixoto committed
167
168
169
170
        Vector vertex property maps where the coordinates should be stored.

    Returns
    -------
171
    pos : :class:`~graph_tool.VertexPropertyMap`
Tiago Peixoto's avatar
Tiago Peixoto committed
172
173
174
175
176
177
178
179
180
181
182
183
184
185
        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
186
    .. testcleanup::
Tiago Peixoto's avatar
Tiago Peixoto committed
187

Tiago Peixoto's avatar
Tiago Peixoto committed
188
       conv_png("lattice-planar.pdf")
Tiago Peixoto's avatar
Tiago Peixoto committed
189

Tiago Peixoto's avatar
Tiago Peixoto committed
190
191

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

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

    References
    ----------
199
    .. [straight-line-boost] http://www.boost.org/doc/libs/release/libs/graph/doc/straight_line_drawing.html
Tiago Peixoto's avatar
Tiago Peixoto committed
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
    .. [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


222
223
224
225
226
227
228
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
    ----------
229
    g : :class:`~graph_tool.Graph`
230
        Graph to be used.
231
    weight : :class:`~graph_tool.EdgePropertyMap` (optional, default: ``None``)
232
233
234
235
236
237
238
        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).
239
240
    circular : bool (optional, default: ``False``)
        If ``True``, the layout will have a circular shape. Otherwise the shape
241
        will be a square.
242
243
    grid : bool (optional, default: ``True``)
        If ``True``, the repulsive forces will only act on vertices which are on
244
        the same site on a grid. Otherwise they will act on all vertex pairs.
245
    t_range : tuple of floats (optional, default: ``(scale / 10, scale / 1000)``)
246
247
        Temperature range used in annealing. The temperature limits the
        displacement at each iteration.
248
    n_iter : int (optional, default: ``100``)
249
        Total number of iterations.
250
    pos : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
251
252
253
254
255
256
        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
    -------
257
    pos : :class:`~graph_tool.VertexPropertyMap`
258
259
        A vector-valued vertex property map with the coordinates of the
        vertices.
260
261
262
263

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

    Examples
    --------
269
270
271
272
273
274
    .. testcode::
       :hide:

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

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

Tiago Peixoto's avatar
Tiago Peixoto committed
280
    .. testcleanup::
281

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

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

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

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

297
    if pos is None:
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
        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,
321
               max_iter=1000, pos=None, dim=2):
322
323
    r"""Calculate the ARF spring-block layout of the graph.

Tiago Peixoto's avatar
Tiago Peixoto committed
324
325
326
327
    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.
328
    weight : :class:`~graph_tool.EdgePropertyMap` (optional, default: ``None``)
Tiago Peixoto's avatar
Tiago Peixoto committed
329
330
331
332
333
334
335
336
337
338
339
340
        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.
341
    pos : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
Tiago Peixoto's avatar
Tiago Peixoto committed
342
343
344
        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
345
346
347

    Returns
    -------
348
    pos : :class:`~graph_tool.VertexPropertyMap`
Tiago Peixoto's avatar
Tiago Peixoto committed
349
350
351
352
353
354
355
356
357
358
        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
    --------
359
360
361
362
363
364
    .. testcode::
       :hide:

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

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

Tiago Peixoto's avatar
Tiago Peixoto committed
370
    .. testcleanup::
371

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

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

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

    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:
390
        pos = random_layout(g, dim=dim)
Tiago Peixoto's avatar
Tiago Peixoto committed
391
392
393
394
395
396
397
398
399
    _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


400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
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,
415
                                         minimize=False, edges=True)
416
417
418
419
            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
420
421
    else:
        mivs = None
422
        c = groups
423
    cg, cc, vcount, ecount = condensation_graph(g, c, vweight, eweight)[:4]
Tiago Peixoto's avatar
Tiago Peixoto committed
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
    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,
439
                                       _get_rng())
440

Tiago Peixoto's avatar
Tiago Peixoto committed
441
442
443
444
445
446
447
    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),
448
                                                    delta, _get_rng())
Tiago Peixoto's avatar
Tiago Peixoto committed
449
450
451
452
453
454
        except ValueError:
            graph_draw(u, mivs, vertex_fillcolor=mivs)
    return pos


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


def coarse_graphs(g, method="hybrid", mivs_thres=0.9, ec_thres=0.75,
463
                  weighted_coarse=False, eweight=None, vweight=None,
464
                  groups=None, verbose=False):
Tiago Peixoto's avatar
Tiago Peixoto committed
465
    cg = [[g, None, None, None, None, None]]
466
467
    if weighted_coarse:
        cg[-1][2], cg[-1][3] = vweight, eweight
Tiago Peixoto's avatar
Tiago Peixoto committed
468
469
    mivs = not (method in ["hybrid", "ec"])
    while True:
470
471
        u = _coarse_graph(cg[-1][0], cg[-1][2], cg[-1][3], mivs, groups)
        groups = None
472
473
474
        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
475
476
477
478
479
480
481
                mivs = True
            else:
                break
        if u[0].num_vertices() <= 2:
            break
        cg.append(u)
        if verbose:
482
483
484
            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
485
486
487
    cg.reverse()
    Ks = []
    pos = random_layout(cg[0][0], dim=2)
488
    for i in range(len(cg)):
Tiago Peixoto's avatar
Tiago Peixoto committed
489
490
491
        if i == 0:
            u = cg[i][0]
            K = _avg_edge_distance(u, pos)
492
493
            if K == 0:
                K = 1.
Tiago Peixoto's avatar
Tiago Peixoto committed
494
495
496
497
498
499
500
501
502
503
504
505
506
            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)

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

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

        if i < len(cg) - 1:
            if verbose:
516
517
                print("propagating...", end=' ')
                print(mivs.a.sum() if mivs is not None else "")
Tiago Peixoto's avatar
Tiago Peixoto committed
518
            pos = _propagate_pos(cg[i + 1][0], u, c, cc, pos,
519
                                 Ks[i] / 1000., mivs)
Tiago Peixoto's avatar
Tiago Peixoto committed
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
568
569
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
570

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

579
580
    Parameters
    ----------
581
    g : :class:`~graph_tool.Graph`
582
        Graph to be used.
583
    vweight : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
584
        A vertex property map with the respective weights.
585
    eweight : :class:`~graph_tool.EdgePropertyMap` (optional, default: ``None``)
586
        An edge property map with the respective weights.
587
    pin : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
588
589
        A vertex property map with boolean values, which, if given,
        specify the vertices which will not have their positions modified.
590
    groups : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
591
592
        A vertex property map with group assignments. Vertices belonging to the
        same group will be put close together.
593
594
595
596
597
598
599
600
    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``)
601
        Quadtree opening parameter, a.k.a. Barnes-Hut opening criterion.
602
    max_level : int (optional, default: ``15``)
603
604
        Maximum quadtree level.
    gamma : float (optional, default: ``1.0``)
605
606
607
608
609
610
611
612
        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.
613
614
    init_step : float (optional, default: ``None``)
        Initial update step. If not provided, it will be chosen automatically.
615
    cooling_step : float (optional, default: ``0.95``)
616
617
618
        Cooling update step.
    adaptive_cooling : bool (optional, default: ``True``)
        Use an adaptive cooling scheme.
619
    epsilon : float (optional, default: ``0.01``)
620
621
        Relative convergence criterion.
    max_iter : int (optional, default: ``0``)
622
        Maximum number of iterations. If this value is ``0``, it runs until
623
        convergence.
624
    pos : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
        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.
642
643
644

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

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

    Examples
    --------
656
657
658
659
660
661
    .. testcode::
       :hide:

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

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

Tiago Peixoto's avatar
Tiago Peixoto committed
667
    .. testcleanup::
668

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

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

Tiago Peixoto's avatar
Tiago Peixoto committed
675
       SFDP layout of a Price network.
676
677
678

    References
    ----------
679
680
681
    .. [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
682
683
    """

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

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

693
694
695
696
697
    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
698
699

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

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

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

    if multilevel:
709
710
        if eweight is not None or vweight is not None:
            weighted_coarse = True
711
712
713
714
715
716
717
718
719
720
721
722
723
        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)
724
        for count, (u, pos, K, vcount, ecount) in enumerate(cgs):
Tiago Peixoto's avatar
Tiago Peixoto committed
725
            if verbose:
726
727
                print("Positioning level:", count, u.num_vertices(), end=' ')
                print("with K =", K, "...")
Tiago Peixoto's avatar
Tiago Peixoto committed
728
729
730
731
                count += 1
            pos = sfdp_layout(u, pos=pos,
                              vweight=vcount if weighted_coarse else None,
                              eweight=ecount if weighted_coarse else None,
732
                              groups=None if u.num_vertices() < g.num_vertices() else groups,
Tiago Peixoto's avatar
Tiago Peixoto committed
733
                              C=C, K=K, p=p,
734
735
                              theta=theta, gamma=gamma, mu=mu, mu_p=mu_p,
                              epsilon=epsilon,
Tiago Peixoto's avatar
Tiago Peixoto committed
736
737
738
                              max_iter=max_iter,
                              cooling_step=cooling_step,
                              adaptive_cooling=False,
739
740
                              # init_step=max(2 * K,
                              #               _avg_edge_distance(u, pos)),
Tiago Peixoto's avatar
Tiago Peixoto committed
741
742
                              multilevel=False,
                              verbose=False)
743
        pos = g_.own_property(pos)
Tiago Peixoto's avatar
Tiago Peixoto committed
744
745
746
747
748
749
750
751
752
753
754
        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
755
756
757
758
    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'.")
759
    libgraph_tool_layout.sanitize_pos(g._Graph__graph, _prop("v", g, pos))
Tiago Peixoto's avatar
Tiago Peixoto committed
760
761
762
    libgraph_tool_layout.sfdp_layout(g._Graph__graph, _prop("v", g, pos),
                                     _prop("v", g, vweight),
                                     _prop("e", g, eweight),
763
                                     _prop("v", g, pin),
764
                                     (C, K, p, gamma, mu, mu_p, _prop("v", g, groups)),
765
                                     theta, init_step, cooling_step, max_level,
Tiago Peixoto's avatar
Tiago Peixoto committed
766
                                     epsilon, max_iter, not adaptive_cooling,
767
                                     verbose, _get_rng())
768
    pos = g_.own_property(pos)
769
    return pos
Tiago Peixoto's avatar
Tiago Peixoto committed
770

771
772
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
773
774
775
776
777
778
779
780
781
    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.
782
    rel_order : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
783
        Relative order of the nodes at each respective branch.
784
785
786
    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
787
788
789
    weighted : ``bool`` (optional, default: ``False``)
        If true, the angle between the child branches will be computed according
        to weight of the entire sub-branches.
790
    node_weight : :class:`~graph_tool.VertexPropertyMap` (optional, default: ``None``)
791
792
        If given, the relative spacing between leafs will correspond to the node
        weights.
Tiago Peixoto's avatar
Tiago Peixoto committed
793
794
795
796
797
    r : ``float`` (optional, default: ``1.``)
        Layer spacing.

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

    Notes
    -----
804
805
    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
806
807
808
809
810
811
812
813
814
815
816
817
818
819

    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
820
    .. testcleanup::
Tiago Peixoto's avatar
Tiago Peixoto committed
821

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

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

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

    """

    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)
837
838
    if rel_order is None:
        rel_order = g.vertex_index.copy("int")
839
840
841
842
    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
843
    libgraph_tool_layout.get_radial(t._Graph__graph,
844
845
                                    _prop("v", t, pos),
                                    _prop("v", t, levels),
846
                                    _prop("v", g, rel_order),
847
                                    _prop("v", g, node_weight),
848
849
                                    int(root), weighted, r,
                                    rel_order_leaf)
Tiago Peixoto's avatar
Tiago Peixoto committed
850
851
    return g.own_property(pos)

852
853
854
855
856
857
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::

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

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

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

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

try:
876
    from . cairo_draw import graph_draw, cairo_draw, get_hierarchy_control_points, default_cm
877
878
879
880
except ImportError:
    pass

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

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