__init__.py 28 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-2016 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
38
   random_layout
39
   get_hierarchy_control_points
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

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

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

.. autosummary::
   :nosignatures:

   cairo_draw
   interactive_window
   GraphWidget
   GraphWindow

64
65
Contents
++++++++
66
67
"""

68
69
from __future__ import division, absolute_import, print_function

Tiago Peixoto's avatar
Tiago Peixoto committed
70
from .. import GraphView, _check_prop_vector, group_vector_property, \
71
     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
    label_components, pseudo_diameter, shortest_distance
Tiago Peixoto's avatar
Tiago Peixoto committed
74
from .. stats import label_parallel_edges
75
from .. generation import predecessor_tree, condensation_graph
Tiago Peixoto's avatar
Tiago Peixoto committed
76
77
import numpy.random
from numpy import sqrt
78
import sys
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
85
86
__all__ = ["graph_draw", "graphviz_draw", "fruchterman_reingold_layout",
           "arf_layout", "sfdp_layout", "random_layout", "radial_tree_layout",
           "cairo_draw", "prop_to_size", "get_hierarchy_control_points",
87
           "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.PropertyMap` (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
110
111
    pos : :class:`~graph_tool.PropertyMap`
        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
129
    array([ 68.72700594,   1.03142919,   2.56812658])
Tiago Peixoto's avatar
Tiago Peixoto committed
130

131
132
    """

133
    if pos == 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 == 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

159
160
161
162
163
164
165
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
    ----------
166
    g : :class:`~graph_tool.Graph`
167
        Graph to be used.
168
    weight : :class:`PropertyMap` (optional, default: ``None``)
169
170
171
172
173
174
175
        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).
176
177
    circular : bool (optional, default: ``False``)
        If ``True``, the layout will have a circular shape. Otherwise the shape
178
        will be a square.
179
180
    grid : bool (optional, default: ``True``)
        If ``True``, the repulsive forces will only act on vertices which are on
181
        the same site on a grid. Otherwise they will act on all vertex pairs.
182
    t_range : tuple of floats (optional, default: ``(scale / 10, scale / 1000)``)
183
184
        Temperature range used in annealing. The temperature limits the
        displacement at each iteration.
185
    n_iter : int (optional, default: ``100``)
186
        Total number of iterations.
187
    pos : :class:`PropertyMap` (optional, default: ``None``)
188
189
190
191
192
193
        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
    -------
194
195
196
    pos : :class:`~graph_tool.PropertyMap`
        A vector-valued vertex property map with the coordinates of the
        vertices.
197
198
199
200

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

    Examples
    --------
206
207
208
209
210
211
    .. testcode::
       :hide:

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

212
213
    >>> g = gt.price_network(300)
    >>> pos = gt.fruchterman_reingold_layout(g, n_iter=1000)
214
    >>> gt.graph_draw(g, pos=pos, output="graph-draw-fr.pdf")
215
216
    <...>

217
218
219
220
221
    .. testcode::
       :hide:

       gt.graph_draw(g, pos=pos, output="graph-draw-fr.png")

222
    .. figure:: graph-draw-fr.*
223
224
225
226
227
228
229
        :align: center

        Fruchterman-Reingold layout of a Price network.

    References
    ----------
    .. [fruchterman-reingold] Fruchterman, Thomas M. J.; Reingold, Edward M.
230
231
       "Graph Drawing by Force-Directed Placement". Software - Practice & Experience
       (Wiley) 21 (11): 1129-1164. (1991) :doi:`10.1002/spe.4380211102`
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
    """

    if pos == None:
        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,
258
               max_iter=1000, pos=None, dim=2):
259
260
    r"""Calculate the ARF spring-block layout of the graph.

Tiago Peixoto's avatar
Tiago Peixoto committed
261
262
263
264
    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Graph to be used.
Tiago Peixoto's avatar
Tiago Peixoto committed
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
    weight : :class:`~graph_tool.PropertyMap` (optional, default: ``None``)
        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.
    pos : :class:`~graph_tool.PropertyMap` (optional, default: ``None``)
        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
282
283
284
285
286
287
288
289
290
291
292
293
294
295

    Returns
    -------
    pos : :class:`~graph_tool.PropertyMap`
        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
    --------
296
297
298
299
300
301
    .. testcode::
       :hide:

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

Tiago Peixoto's avatar
Tiago Peixoto committed
302
303
    >>> g = gt.price_network(300)
    >>> pos = gt.arf_layout(g, max_iter=0)
304
    >>> gt.graph_draw(g, pos=pos, output="graph-draw-arf.pdf")
Tiago Peixoto's avatar
Tiago Peixoto committed
305
306
    <...>

307
308
309
310
311
    .. testcode::
       :hide:

       gt.graph_draw(g, pos=pos, output="graph-draw-arf.png")

Tiago Peixoto's avatar
Tiago Peixoto committed
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
    .. figure:: graph-draw-arf.*
        :align: center

        ARF layout of a Price network.

    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:
327
        pos = random_layout(g, dim=dim)
Tiago Peixoto's avatar
Tiago Peixoto committed
328
329
330
331
332
333
334
335
336
    _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


337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
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,
                                         minimize=False)
            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
357
358
    else:
        mivs = None
359
        c = groups
360
    cg, cc, vcount, ecount = condensation_graph(g, c, vweight, eweight)[:4]
Tiago Peixoto's avatar
Tiago Peixoto committed
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
    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,
376
                                       _get_rng())
377

Tiago Peixoto's avatar
Tiago Peixoto committed
378
379
380
381
382
383
384
    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),
385
                                                    delta, _get_rng())
Tiago Peixoto's avatar
Tiago Peixoto committed
386
387
388
389
390
391
        except ValueError:
            graph_draw(u, mivs, vertex_fillcolor=mivs)
    return pos


def _avg_edge_distance(g, pos):
392
    libgraph_tool_layout.sanitize_pos(g._Graph__graph, _prop("v", g, pos))
393
    ad = libgraph_tool_layout.avg_dist(g._Graph__graph, _prop("v", g, pos))
394
    if numpy.isnan(ad) or ad == 0:
395
396
        ad = 1.
    return ad
Tiago Peixoto's avatar
Tiago Peixoto committed
397
398
399


def coarse_graphs(g, method="hybrid", mivs_thres=0.9, ec_thres=0.75,
400
                  weighted_coarse=False, eweight=None, vweight=None,
401
                  groups=None, verbose=False):
Tiago Peixoto's avatar
Tiago Peixoto committed
402
    cg = [[g, None, None, None, None, None]]
403
404
    if weighted_coarse:
        cg[-1][2], cg[-1][3] = vweight, eweight
Tiago Peixoto's avatar
Tiago Peixoto committed
405
406
    mivs = not (method in ["hybrid", "ec"])
    while True:
407
408
        u = _coarse_graph(cg[-1][0], cg[-1][2], cg[-1][3], mivs, groups)
        groups = None
409
410
411
        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
412
413
414
415
416
417
418
                mivs = True
            else:
                break
        if u[0].num_vertices() <= 2:
            break
        cg.append(u)
        if verbose:
419
420
421
            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
422
423
424
    cg.reverse()
    Ks = []
    pos = random_layout(cg[0][0], dim=2)
425
    for i in range(len(cg)):
Tiago Peixoto's avatar
Tiago Peixoto committed
426
427
428
        if i == 0:
            u = cg[i][0]
            K = _avg_edge_distance(u, pos)
429
430
            if K == 0:
                K = 1.
Tiago Peixoto's avatar
Tiago Peixoto committed
431
432
433
434
435
436
437
438
439
440
441
442
443
            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)

444
    for i in range(len(cg)):
Tiago Peixoto's avatar
Tiago Peixoto committed
445
446
447
448
        u, cc, vcount, ecount, c, mivs = cg[i]
        yield u, pos, Ks[i], vcount, ecount

        if verbose:
449
            print("avg edge distance:", _avg_edge_distance(u, pos))
Tiago Peixoto's avatar
Tiago Peixoto committed
450
451
452

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

458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
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
507

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

516
517
    Parameters
    ----------
518
    g : :class:`~graph_tool.Graph`
519
        Graph to be used.
520
521
522
    vweight : :class:`~graph_tool.PropertyMap` (optional, default: ``None``)
        A vertex property map with the respective weights.
    eweight : :class:`~graph_tool.PropertyMap` (optional, default: ``None``)
523
        An edge property map with the respective weights.
524
    pin : :class:`~graph_tool.PropertyMap` (optional, default: ``None``)
525
526
527
528
529
        A vertex property map with boolean values, which, if given,
        specify the vertices which will not have their positions modified.
    groups : :class:`~graph_tool.PropertyMap` (optional, default: ``None``)
        A vertex property map with group assignments. Vertices belonging to the
        same group will be put close together.
530
531
532
533
534
535
536
537
    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``)
538
        Quadtree opening parameter, a.k.a. Barnes-Hut opening criterion.
539
    max_level : int (optional, default: ``15``)
540
541
        Maximum quadtree level.
    gamma : float (optional, default: ``1.0``)
542
543
544
545
546
547
548
549
        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.
550
551
    init_step : float (optional, default: ``None``)
        Initial update step. If not provided, it will be chosen automatically.
552
    cooling_step : float (optional, default: ``0.95``)
553
554
555
        Cooling update step.
    adaptive_cooling : bool (optional, default: ``True``)
        Use an adaptive cooling scheme.
556
    epsilon : float (optional, default: ``0.01``)
557
558
        Relative convergence criterion.
    max_iter : int (optional, default: ``0``)
559
        Maximum number of iterations. If this value is ``0``, it runs until
560
        convergence.
561
    pos : :class:`~graph_tool.PropertyMap` (optional, default: ``None``)
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
        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.
579
580
581

    Returns
    -------
582
583
584
    pos : :class:`~graph_tool.PropertyMap`
        A vector-valued vertex property map with the coordinates of the
        vertices.
585
586
587

    Notes
    -----
588
589
    This algorithm is defined in [hu-multilevel-2005]_, and has
    complexity :math:`O(V\log V)`.
590
591
592

    Examples
    --------
593
594
595
596
597
598
    .. testcode::
       :hide:

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

599
600
601
    >>> g = gt.price_network(3000)
    >>> pos = gt.sfdp_layout(g)
    >>> gt.graph_draw(g, pos=pos, output="graph-draw-sfdp.pdf")
602
603
    <...>

604
605
606
607
608
    .. testcode::
       :hide:

       gt.graph_draw(g, pos=pos, output="graph-draw-sfdp.png")

609
    .. figure:: graph-draw-sfdp.*
610
611
        :align: center

612
        SFDP layout of a Price network.
613
614
615

    References
    ----------
616
617
618
    .. [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
619
620
    """

621
    if pos is None:
Tiago Peixoto's avatar
Tiago Peixoto committed
622
        pos = random_layout(g, dim=2)
623
624
    _check_prop_vector(pos, name="pos", floating=True)

Tiago Peixoto's avatar
Tiago Peixoto committed
625
626
    g = GraphView(g, directed=False)

627
628
629
630
631
    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
632
633

    if K is None:
Tiago Peixoto's avatar
Tiago Peixoto committed
634
        K = _avg_edge_distance(g, pos)
Tiago Peixoto's avatar
Tiago Peixoto committed
635
636

    if init_step is None:
637
        init_step = 2 * max(_avg_edge_distance(g, pos), K)
Tiago Peixoto's avatar
Tiago Peixoto committed
638
639
640
641
642

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

    if multilevel:
643
644
        if eweight is not None or vweight is not None:
            weighted_coarse = True
645
646
647
648
649
650
651
652
653
654
655
656
657
        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)
658
        for count, (u, pos, K, vcount, ecount) in enumerate(cgs):
Tiago Peixoto's avatar
Tiago Peixoto committed
659
            if verbose:
660
661
                print("Positioning level:", count, u.num_vertices(), end=' ')
                print("with K =", K, "...")
Tiago Peixoto's avatar
Tiago Peixoto committed
662
663
664
665
666
                count += 1
            #graph_draw(u, pos)
            pos = sfdp_layout(u, pos=pos,
                              vweight=vcount if weighted_coarse else None,
                              eweight=ecount if weighted_coarse else None,
667
                              groups=None if u.num_vertices() < g.num_vertices() else groups,
Tiago Peixoto's avatar
Tiago Peixoto committed
668
                              C=C, K=K, p=p,
669
670
                              theta=theta, gamma=gamma, mu=mu, mu_p=mu_p,
                              epsilon=epsilon,
Tiago Peixoto's avatar
Tiago Peixoto committed
671
672
673
                              max_iter=max_iter,
                              cooling_step=cooling_step,
                              adaptive_cooling=False,
674
675
                              # init_step=max(2 * K,
                              #               _avg_edge_distance(u, pos)),
Tiago Peixoto's avatar
Tiago Peixoto committed
676
677
678
679
680
681
682
683
684
685
686
687
688
689
                              multilevel=False,
                              verbose=False)
            #graph_draw(u, pos)
        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
690
691
692
693
    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'.")
694
    libgraph_tool_layout.sanitize_pos(g._Graph__graph, _prop("v", g, pos))
Tiago Peixoto's avatar
Tiago Peixoto committed
695
696
697
    libgraph_tool_layout.sfdp_layout(g._Graph__graph, _prop("v", g, pos),
                                     _prop("v", g, vweight),
                                     _prop("e", g, eweight),
698
                                     _prop("v", g, pin),
699
                                     (C, K, p, gamma, mu, mu_p, _prop("v", g, groups)),
700
                                     theta, init_step, cooling_step, max_level,
Tiago Peixoto's avatar
Tiago Peixoto committed
701
                                     epsilon, max_iter, not adaptive_cooling,
702
                                     verbose, _get_rng())
703
    return pos
Tiago Peixoto's avatar
Tiago Peixoto committed
704

705
706
def radial_tree_layout(g, root, rel_order=None, weighted=False,
                       node_weight=None, r=1.):
Tiago Peixoto's avatar
Tiago Peixoto committed
707
708
709
710
711
712
713
714
715
    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.
716
    rel_order : :class:`~graph_tool.PropertyMap` (optional, default: ``None``)
717
        Relative order of the nodes at each respective branch.
Tiago Peixoto's avatar
Tiago Peixoto committed
718
719
720
    weighted : ``bool`` (optional, default: ``False``)
        If true, the angle between the child branches will be computed according
        to weight of the entire sub-branches.
721
722
723
    node_weight : :class:`~graph_tool.PropertyMap` (optional, default: ``None``)
        If given, the relative spacing between leafs will correspond to the node
        weights.
Tiago Peixoto's avatar
Tiago Peixoto committed
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
    r : ``float`` (optional, default: ``1.``)
        Layer spacing.

    Returns
    -------
    pos : :class:`~graph_tool.PropertyMap`
        A vector-valued vertex property map with the coordinates of the
        vertices.

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

    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")
    <...>

    .. testcode::
       :hide:

       gt.graph_draw(g, pos=pos, output="graph-draw-radial.png")

    .. figure:: graph-draw-radial.*
        :align: center

        Radial tree layout of a Price network.

    """

    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)
767
768
    if rel_order is None:
        rel_order = g.vertex_index.copy("int")
769
770
771
772
    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
773
774
775
    libgraph_tool_layout.get_radial(t._Graph__graph,
                                    _prop("v", g, pos),
                                    _prop("v", g, levels),
776
                                    _prop("v", g, rel_order),
777
                                    _prop("v", g, node_weight),
Tiago Peixoto's avatar
Tiago Peixoto committed
778
779
780
                                    int(root), weighted, r)
    return g.own_property(pos)

781
782
783
784
785
786
787
788
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::

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

Tiago Peixoto's avatar
Tiago Peixoto committed
789
    If `log=True`, the natural logarithm of the property values is used instead.
790
791
792
793
794
795
796
797

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

798
    delta = vals.max() - vals.min()
799
800
801
802
    if delta == 0:
        delta = 1
    prop.fa = mi + (ma - mi) * ((vals - vals.min()) / delta) ** power
    return prop
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819

try:
    from .cairo_draw import graph_draw, cairo_draw, get_hierarchy_control_points, default_cm
except ImportError:
    pass

try:
    from .cairo_draw import GraphWidget, GraphWindow, \
        interactive_window, draw_hierarchy
    __all__ += ["interactive_window", "GraphWidget", "GraphWindow", "draw_hierarchy"]
except ImportError:
    pass

try:
   from .graphviz_draw import graphviz_draw
except ImportError:
   pass