__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-2018 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
37
   radial_tree_layout
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
from __future__ import division, absolute_import, print_function

71
from .. import Graph, GraphView, _check_prop_vector, group_vector_property, \
72
     ungroup_vector_property, infect_vertex_property, _prop, _get_rng
Tiago Peixoto's avatar
Tiago Peixoto committed
73
from .. topology import max_cardinality_matching, max_independent_vertex_set, \
74 75
    label_components, pseudo_diameter, shortest_distance, make_maximal_planar, \
    is_planar
Tiago Peixoto's avatar
Tiago Peixoto committed
76
from .. stats import label_parallel_edges
77
from .. generation import predecessor_tree, condensation_graph
Tiago Peixoto's avatar
Tiago Peixoto committed
78 79
import numpy.random
from numpy import sqrt
80
import sys
81 82

from .. dl_import import dl_import
83
dl_import("from . import libgraph_tool_layout")
84

85

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

Tiago Peixoto's avatar
Tiago Peixoto committed
91

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

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

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

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

    Examples
    --------
121 122 123 124 125 126
    .. testcode::
       :hide:

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

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

133 134
    """

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

139
    pos = ungroup_vector_property(pos, list(range(0, dim)))
140

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

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

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

Tiago Peixoto's avatar
Tiago Peixoto committed
157
    pos = group_vector_property(pos)
158 159
    return pos

Tiago Peixoto's avatar
Tiago Peixoto committed
160

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

    Returns
    -------
173
    pos : :class:`~graph_tool.VertexPropertyMap`
174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199
        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")
    <...>

    .. testcode::
       :hide:

       gt.graph_draw(g, pos=pos, output="lattice-planar.png")

    .. figure:: lattice-planar.*
        :align: center

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

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


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

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

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

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

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

281 282 283 284 285
    .. testcode::
       :hide:

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

286
    .. figure:: graph-draw-fr.*
287 288 289 290 291 292 293
        :align: center

        Fruchterman-Reingold layout of a Price network.

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

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

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

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

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

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

371 372 373 374 375
    .. testcode::
       :hide:

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

Tiago Peixoto's avatar
Tiago Peixoto committed
376 377 378 379 380 381 382 383 384 385 386 387 388 389 390
    .. 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:
391
        pos = random_layout(g, dim=dim)
Tiago Peixoto's avatar
Tiago Peixoto committed
392 393 394 395 396 397 398 399 400
    _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


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

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


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


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

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

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

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

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

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

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

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

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

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

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

668 669 670 671 672
    .. testcode::
       :hide:

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

673
    .. figure:: graph-draw-sfdp.*
674 675
        :align: center

676
        SFDP layout of a Price network.
677 678 679

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

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

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

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

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

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

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

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

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

    Returns
    -------
797
    pos : :class:`~graph_tool.VertexPropertyMap`
798 799 800 801 802
        A vector-valued vertex property map with the coordinates of the
        vertices.

    Notes
    -----
803 804
    This algorithm has complexity :math:`O(V + E)`, or :math:`O(V\log V + E)` if
    ``rel_order`` is given.
805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835

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

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

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

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

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

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

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

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

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