quickstart.rst 29.1 KB
Newer Older
1 2 3
Quick start using `graph-tool`
==============================

4 5 6 7
The :mod:`graph_tool` module provides a :class:`~graph_tool.Graph` class
and several algorithms that operate on it. The internals of this class,
and of most algorithms, are written in C++ for performance, using the
`Boost Graph Library <http://www.boost.org>`_.
8

9 10 11
The module must be of course imported before it can be used. The package is
subdivided into several sub-modules. To import everything from all of them, one
can do:
12

13 14 15 16 17
.. testsetup::

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

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
.. doctest::

   >>> from graph_tool.all import *

In the following, it will always be assumed that the previous line was run.

Creating and manipulating graphs
--------------------------------

An empty graph can be created by instantiating a :class:`~graph_tool.Graph`
class:

.. doctest::

   >>> g = Graph()

By default, newly created graphs are always directed. To construct undirected
35
graphs, one must pass a value to the ``directed`` parameter:
36 37 38 39 40

.. doctest::

   >>> ug = Graph(directed=False)

41 42 43 44
A graph can always be switched *on-the-fly* from directed to undirected
(and vice versa), with the :meth:`~graph_tool.Graph.set_directed`
method. The "directedness" of the graph can be queried with the
:meth:`~graph_tool.Graph.is_directed` method,
45 46 47 48 49

.. doctest::

   >>> ug = Graph()
   >>> ug.set_directed(False)
50
   >>> assert ug.is_directed() == False
51

52 53 54
A graph can also be created by providing another graph, in which case
the entire graph (and its internal property maps, see
:ref:`sec_property_maps`) is copied:
55 56 57 58

.. doctest::

   >>> g1 = Graph()
59
   >>> # ... construct g1 ...
60 61
   >>> g2 = Graph(g1)                 # g1 and g2 are copies

62 63 64 65 66 67 68 69 70
Above, ``g2`` is a "deep" copy of ``g1``, i.e. any modification of
``g2`` will not affect ``g1``.

Once a graph is created, it can be populated with vertices and edges. A
vertex can be added with the :meth:`~graph_tool.Graph.add_vertex`
method, which returns an instance of a :class:`~graph_tool.Vertex`
class, also called a *vertex descriptor*. For instance, the following
code creates two vertices, and returns vertex descriptors stored in the
variables ``v1`` and ``v2``.
71 72 73

.. doctest::

74 75
   >>> v1 = g.add_vertex()
   >>> v2 = g.add_vertex()
76

77 78 79
Edges can be added in an analogous manner, by calling the
:meth:`~graph_tool.Graph.add_edge` method, which returns an edge
descriptor (an instance of the :class:`~graph_tool.Edge` class):
80 81 82

.. doctest::

83
   >>> e = g.add_edge(v1, v2)
84

85 86 87
The above code creates a directed edge from ``v1`` to ``v2``. We can
visualize the graph we created so far with the
:func:`~graph_tool.draw.graph_draw` function.
88 89 90

.. doctest::

91
   >>> graph_draw(g, vertex_text=g.vertex_index, vertex_font_size=18,
Tiago Peixoto's avatar
Tiago Peixoto committed
92
   ...            output_size=(200, 200), output="two-nodes.png")
93 94
   <...>

95 96 97 98
.. doctest::
   :hide:

   graph_draw(g, vertex_text=g.vertex_index, vertex_font_size=18,
Tiago Peixoto's avatar
Tiago Peixoto committed
99
              output_size=(200, 200), output="two-nodes.pdf")
100 101


102
.. figure:: two-nodes.*
103 104 105 106
   :align: center

   A simple directed graph with two vertices and one edge, created by
   the commands above.
107

108 109 110 111
With vertex and edge descriptors, one can examine and manipulate the
graph in an arbitrary manner. For instance, in order to obtain the
out-degree of a vertex, we can simply call the
:meth:`~graph_tool.Vertex.out_degree` method:
112 113 114

.. doctest::

Tiago Peixoto's avatar
Tiago Peixoto committed
115
   >>> print(v1.out_degree())
116 117 118 119
   1

Analogously, we could have used the :meth:`~graph_tool.Vertex.in_degree`
method to query the in-degree.
120

121 122 123 124
.. note::

   For undirected graphs, the "out-degree" is synonym for degree, and
   in this case the in-degree of a vertex is always zero.
125

126 127 128
Edge descriptors have two useful methods, :meth:`~graph_tool.Edge.source`
and :meth:`~graph_tool.Edge.target`, which return the source and target
vertex of an edge, respectively.
129 130 131

.. doctest::

Tiago Peixoto's avatar
Tiago Peixoto committed
132
   >>> print(e.source(), e.target())
133
   0 1
134

135 136
The :meth:`~graph_tool.Graph.add_vertex` method also accepts an optional
parameter which specifies the number of vertices to create. If this
137 138
value is greater than 1, it returns an iterator on the added vertex
descriptors:
139 140 141

.. doctest::

142
   >>> vlist = g.add_vertex(10)
143
   >>> print(len(list(vlist)))
144 145
   10

146
Each vertex in a graph has an unique index, which is *always* between
Tiago Peixoto's avatar
Tiago Peixoto committed
147
:math:`0` and :math:`N-1`, where :math:`N` is the number of
148 149 150 151 152 153 154 155 156
vertices. This index can be obtained by using the
:attr:`~graph_tool.Graph.vertex_index` attribute of the graph (which is
a *property map*, see :ref:`sec_property_maps`), or by converting the
vertex descriptor to an ``int``.

.. doctest::

   >>> v = g.add_vertex()
   >>> print(g.vertex_index[v])
Tiago Peixoto's avatar
Tiago Peixoto committed
157
   12
158
   >>> print(int(v))
Tiago Peixoto's avatar
Tiago Peixoto committed
159
   12
160 161

   
162 163 164 165 166 167 168 169
Edges and vertices can also be removed at any time with the
:meth:`~graph_tool.Graph.remove_vertex` and :meth:`~graph_tool.Graph.remove_edge` methods,

.. doctest::

   >>> g.remove_edge(e)                               # e no longer exists
   >>> g.remove_vertex(v2)                # the second vertex is also gone

170
   
171
.. note::
172

173 174 175 176 177 178 179
   Removing a vertex is typically an :math:`O(N)` operation. The
   vertices are internally stored in a `STL vector
   <http://en.wikipedia.org/wiki/Vector_%28STL%29>`_, so removing an
   element somewhere in the middle of the list requires the shifting of
   the rest of the list. Thus, fast :math:`O(1)` removals are only
   possible either if one can guarantee that only vertices in the end of
   the list are removed (the ones last added to the graph), or if the
Tiago Peixoto's avatar
Tiago Peixoto committed
180
   relative vertex ordering is invalidated. The latter behavior can be
181 182
   achieved by passing the option ``fast == True``, to
   :meth:`~graph_tool.Graph.remove_vertex`, which causes the vertex
Tiago Peixoto's avatar
Tiago Peixoto committed
183 184 185 186
   being deleted to be 'swapped' with the last vertex (i.e. with the
   largest index), which will in turn inherit the index of the vertex
   being deleted.

187 188 189 190 191 192 193 194 195 196
.. warning::

   Because of the above, removing a vertex with an index smaller than
   :math:`N-1` will **invalidate either the last** (``fast = True``)
   **or all** (``fast = False``) **descriptors pointing to vertices with
   higher index**.

   As a consequence, if more than one vertex is to be removed at a given
   time, they should **always** be removed in decreasing index order:
   
Tiago Peixoto's avatar
Tiago Peixoto committed
197
   .. code-block::
198 199 200 201 202 203 204 205 206 207 208

       # 'del_list' is a list of vertex descriptors
       for v in reversed(sorted(del_list)):
           g.remove_vertex(v)

   Alternatively (and preferably), a list (or any iterable) may be
   passed directly as the ``vertex`` parameter of the
   :meth:`~graph_tool.Graph.remove_vertex` function, and the above is
   performed internally (in C++).

   Note that property map values (see :ref:`sec_property_maps`) are
Tiago Peixoto's avatar
Tiago Peixoto committed
209 210
   unaffected by the index changes due to vertex removal, as they are
   modified accordingly by the library.
211 212

.. note::
213

214
   Removing an edge is an :math:`O(k_{s} + k_{t})` operation, where
215
   :math:`k_{s}` is the out-degree of the source vertex, and
Tiago Peixoto's avatar
Tiago Peixoto committed
216 217 218 219
   :math:`k_{t}` is the in-degree of the target vertex. This can be made
   faster by setting :meth:`~graph_tool.Graph.set_fast_edge_removal` to
   `True`, in which case it becomes :math:`O(1)`, at the expense of
   additional data of size :math:`O(E)`.
220

Tiago Peixoto's avatar
Tiago Peixoto committed
221 222
   No edge descriptors are ever invalidated after edge removal, with the
   exception of the edge being removed.
223 224 225

Since vertices are uniquely identifiable by their indexes, there is no
need to keep the vertex descriptor lying around to access them at a
Tiago Peixoto's avatar
Tiago Peixoto committed
226
later point. If we know its index, we can obtain the descriptor of a
227 228 229 230 231 232 233 234 235
vertex with a given index using the :meth:`~graph_tool.Graph.vertex`
method,

.. doctest::

   >>> v = g.vertex(8)

which takes an index, and returns a vertex descriptor. Edges cannot be
directly obtained by its index, but if the source and target vertices of
Tiago Peixoto's avatar
Tiago Peixoto committed
236
a given edge are known, it can be retrieved with the
237 238 239 240 241 242 243 244 245 246 247 248 249 250 251
:meth:`~graph_tool.Graph.edge` method

.. doctest::

   >>> g.add_edge(g.vertex(2), g.vertex(3))
   <...>
   >>> e = g.edge(2, 3)


Another way to obtain edge or vertex descriptors is to *iterate* through
them, as described in section :ref:`sec_iteration`. This is in fact the
most useful way of obtaining vertex and edge descriptors.

Like vertices, edges also have unique indexes, which are given by the
:attr:`~graph_tool.Graph.edge_index` property:
252 253 254 255

.. doctest::

   >>> e = g.add_edge(g.vertex(0), g.vertex(1))
Tiago Peixoto's avatar
Tiago Peixoto committed
256
   >>> print(g.edge_index[e])
257 258 259 260 261 262 263
   1

Differently from vertices, edge indexes do not necessarily conform to
any specific range. If no edges are ever removed, the indexes will be in
the range :math:`[0, E-1]`, where :math:`E` is the number of edges, and
edges added earlier have lower indexes. However if an edge is removed,
its index will be "vacant", and the remaining indexes will be left
Tiago Peixoto's avatar
Tiago Peixoto committed
264 265
unmodified, and thus will not all lie in the range :math:`[0, E-1]`.  If
a new edge is added, it will reuse old indexes, in an increasing order.
266

267

268 269 270
.. _sec_iteration:

Iterating over vertices and edges
271
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
272

273 274 275 276
Algorithms must often iterate through vertices, edges, out-edges of a
vertex, etc. The :class:`~graph_tool.Graph` and
:class:`~graph_tool.Vertex` classes provide different types of iterators
for doing so. The iterators always point to edge or vertex descriptors.
277

278 279 280 281 282 283
Iterating over all vertices or edges
""""""""""""""""""""""""""""""""""""

In order to iterate through all the vertices or edges of a graph, the
:meth:`~graph_tool.Graph.vertices` and :meth:`~graph_tool.Graph.edges`
methods should be used:
284

Tiago Peixoto's avatar
Tiago Peixoto committed
285
.. testcode::
286 287

   for v in g.vertices():
Tiago Peixoto's avatar
Tiago Peixoto committed
288
       print(v)
Tiago Peixoto's avatar
Tiago Peixoto committed
289
   for e in g.edges():
Tiago Peixoto's avatar
Tiago Peixoto committed
290
       print(e)
291

292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309
.. testoutput::
   :hide:

   0
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   (0, 1)
   (2, 3)

310 311 312
The code above will print the vertices and edges of the graph in the order they
are found.

313
Iterating over the neighborhood of a vertex
314 315
""""""""""""""""""""""""""""""""""""""""""""

316
The out- and in-edges of a vertex, as well as the out- and in-neighbors can be
317
iterated through with the :meth:`~graph_tool.Vertex.out_edges`,
318 319
:meth:`~graph_tool.Vertex.in_edges`, :meth:`~graph_tool.Vertex.out_neighbors`
and :meth:`~graph_tool.Vertex.in_neighbors` methods, respectively.
320

Tiago Peixoto's avatar
Tiago Peixoto committed
321
.. testcode::
322 323 324

   for v in g.vertices():
      for e in v.out_edges():
Tiago Peixoto's avatar
Tiago Peixoto committed
325
          print(e)
326
      for w in v.out_neighbors():
Tiago Peixoto's avatar
Tiago Peixoto committed
327
          print(w)
328

329
      # the edge and neighbors order always match
330
      for e, w in zip(v.out_edges(), v.out_neighbors()):
331
          assert e.target() == w
332

333 334 335 336 337 338 339 340
.. testoutput::
   :hide:

   (0, 1)
   1
   (2, 3)
   3

341
The code above will print the out-edges and out-neighbors of all
342 343 344
vertices in the graph.

.. warning::
345

346 347 348 349 350
   You should never remove vertex or edge descriptors when iterating
   over them, since this invalidates the iterators. If you plan to
   remove vertices or edges during iteration, you must first store them
   somewhere (such as in a list) and remove them only after no iterator
   is being used. Removal during iteration will cause bad things to
351
   happen.
352

353 354 355 356 357 358 359 360 361 362 363 364 365
Fast iteration over vertices and edges
""""""""""""""""""""""""""""""""""""""

While convenient, looping over the graph as described in the previous
section is not the most efficient approach. This is because the loops
are performed in pure Python, and hence it undermines the main feature
of the library, which is the offloading of loops from Python to
C++. Following the :mod:`numpy` philosophy, :mod:`graph_tool` also
provides an array-based interface that avoids loops in Python. This is
done with the :meth:`~graph_tool.Graph.get_vertices`,
:meth:`~graph_tool.Graph.get_edges`,
:meth:`~graph_tool.Graph.get_out_edges`,
:meth:`~graph_tool.Graph.get_in_edges`,
366 367
:meth:`~graph_tool.Graph.get_out_neighbors`,
:meth:`~graph_tool.Graph.get_in_neighbors`,
368 369 370 371 372 373 374 375 376 377 378 379
:meth:`~graph_tool.Graph.get_out_degrees` and
:meth:`~graph_tool.Graph.get_in_degrees` methods, which return
:class:`numpy.ndarray` instances instead of iterators.

For example, using this interface we can get the out-degree of each node via:

.. testcode::

   print(g.get_out_degrees(g.get_vertices()))

.. testoutput::

380
   [0 1 0 1 0 0 0 0 0 0 0 0]
381 382 383 384 385 386 387 388 389 390 391 392 393

or the sum of the product of the in and out-degrees of the endpoints of
each edge with:

.. testcode::

   edges = g.get_edges()
   print((edges[:,0] * edges[:,1]).sum())

.. testoutput::

   6
   
394 395 396 397 398
.. _sec_property_maps:

Property maps
-------------

399 400
Property maps are a way of associating additional information to the
vertices, edges or to the graph itself. There are thus three types of
401 402 403 404 405
property maps: vertex, edge and graph. They are handled by the
classes :class:`~graph_tool.VertexPropertyMap`,
:class:`~graph_tool.EdgePropertyMap`, and
:class:`~graph_tool.GraphPropertyMap`. Each created property map has an
associated *value type*, which must be chosen from the predefined set:
406 407 408 409 410

.. tabularcolumns:: |l|l|

.. table::

Tiago Peixoto's avatar
Tiago Peixoto committed
411 412 413 414
    ========================     ======================
     Type name                   Alias
    ========================     ======================
    ``bool``                     ``uint8_t``
415
    ``int16_t``                  ``short``
Tiago Peixoto's avatar
Tiago Peixoto committed
416 417 418
    ``int32_t``                  ``int``
    ``int64_t``                  ``long``, ``long long``
    ``double``                   ``float``
Tiago Peixoto's avatar
Tiago Peixoto committed
419 420
    ``long double``
    ``string``
Tiago Peixoto's avatar
Tiago Peixoto committed
421
    ``vector<bool>``             ``vector<uint8_t>``
422
    ``vector<int16_t>``          ``vector<short>``
Tiago Peixoto's avatar
Tiago Peixoto committed
423 424 425
    ``vector<int32_t>``          ``vector<int>``
    ``vector<int64_t>``          ``vector<long>``, ``vector<long long>``
    ``vector<double>``           ``vector<float>``
426 427
    ``vector<long double>``
    ``vector<string>``
Tiago Peixoto's avatar
Tiago Peixoto committed
428 429
    ``python::object``           ``object``
    ========================     ======================
430

431 432 433 434 435 436 437 438 439
New property maps can be created for a given graph by calling one of the
methods :meth:`~graph_tool.Graph.new_vertex_property` (alias
:meth:`~graph_tool.Graph.new_vp`),
:meth:`~graph_tool.Graph.new_edge_property` (alias
:meth:`~graph_tool.Graph.new_ep`), or
:meth:`~graph_tool.Graph.new_graph_property` (alias
:meth:`~graph_tool.Graph.new_gp`), for each map type. The values are
then accessed by vertex or edge descriptors, or the graph itself, as
such:
440

Tiago Peixoto's avatar
Tiago Peixoto committed
441
.. testcode::
442 443 444 445 446

    from numpy.random import randint

    g = Graph()
    g.add_vertex(100)
447

448
    # insert some random links
449
    for s,t in zip(randint(0, 100, 100), randint(0, 100, 100)):
450 451
        g.add_edge(g.vertex(s), g.vertex(t))

452
    vprop_double = g.new_vertex_property("double")            # Double-precision floating point
453 454
    v = g.vertex(10)
    vprop_double[v] = 3.1416
455

456
    vprop_vint = g.new_vertex_property("vector<int>")         # Vector of ints
457 458
    v = g.vertex(40)
    vprop_vint[v] = [1, 3, 42, 54]
459
    
Tiago Peixoto's avatar
Tiago Peixoto committed
460
    eprop_dict = g.new_edge_property("object")                # Arbitrary Python object.
461 462
    e = g.edges().next()
    eprop_dict[e] = {"foo": "bar", "gnu": 42}                 # In this case, a dict.
463

464
    gprop_bool = g.new_graph_property("bool")                 # Boolean
465 466
    gprop_bool[g] = True

467 468
Property maps with scalar value types can also be accessed as a
:class:`numpy.ndarray`, with the
Tiago Peixoto's avatar
Tiago Peixoto committed
469
:meth:`~graph_tool.PropertyMap.get_array` method, or the
470
:attr:`~graph_tool.PropertyMap.a` attribute, e.g.,
471

Tiago Peixoto's avatar
Tiago Peixoto committed
472
.. testcode::
473 474 475

    from numpy.random import random

476
    # this assigns random values to the vertex properties
477 478
    vprop_double.get_array()[:] = random(g.num_vertices())

479 480 481
    # or more conveniently (this is equivalent to the above)
    vprop_double.a = random(g.num_vertices())

482 483
.. _sec_internal_props:

484
Internal property maps
485
^^^^^^^^^^^^^^^^^^^^^^
486

487 488 489 490 491
Any created property map can be made "internal" to the corresponding
graph. This means that it will be copied and saved to a file together
with the graph. Properties are internalized by including them in the
graph's dictionary-like attributes
:attr:`~graph_tool.Graph.vertex_properties`,
492
:attr:`~graph_tool.Graph.edge_properties` or
493 494 495
:attr:`~graph_tool.Graph.graph_properties` (or their aliases,
:attr:`~graph_tool.Graph.vp`, :attr:`~graph_tool.Graph.ep` or
:attr:`~graph_tool.Graph.gp`, respectively). When inserted in the graph,
496 497
the property maps must have an unique name (between those of the same
type):
498 499 500 501 502 503 504 505

.. doctest::

    >>> eprop = g.new_edge_property("string")
    >>> g.edge_properties["some name"] = eprop
    >>> g.list_properties()
    some name      (edge)    (type: string)

506 507 508 509 510 511 512 513 514 515 516 517 518
Internal graph property maps behave slightly differently. Instead of
returning the property map object, the value itself is returned from the
dictionaries:

.. doctest::

    >>> gprop = g.new_graph_property("int")
    >>> g.graph_properties["foo"] = gprop   # this sets the actual property map
    >>> g.graph_properties["foo"] = 42      # this sets its value
    >>> print(g.graph_properties["foo"])
    42
    >>> del g.graph_properties["foo"]       # the property map entry is deleted from the dictionary

519 520 521 522 523
For convenience, the internal property maps can also be accessed via
attributes:

.. doctest::

Tiago Peixoto's avatar
Tiago Peixoto committed
524 525 526 527 528 529
    >>> vprop = g.new_vertex_property("double")
    >>> g.vp.foo = vprop                        # equivalent to g.vertex_properties["foo"] = vprop
    >>> v = g.vertex(0)
    >>> g.vp.foo[v] = 3.14
    >>> print(g.vp.foo[v])
    3.14
530

531
.. _sec_graph_io:
532 533 534 535

Graph I/O
---------

536
Graphs can be saved and loaded in four formats: `graphml
537
<http://graphml.graphdrawing.org/>`_, `dot
538 539
<http://www.graphviz.org/doc/info/lang.html>`_, `gml
<http://www.fim.uni-passau.de/en/fim/faculty/chairs/theoretische-informatik/projects.html>`_
540 541 542 543
and a custom binary format ``gt`` (see :ref:`sec_gt_format`). 

.. warning::

Tiago Peixoto's avatar
Tiago Peixoto committed
544 545 546 547
    The binary format ``gt`` and the text-based ``graphml`` are the
    preferred formats, since they are by far the most complete. Both
    these formats are equally complete, but the ``gt`` format is faster
    and requires less storage.
548 549 550 551 552 553 554 555 556

    The ``dot`` and ``gml`` formats are fully supported, but since they
    contain no precise type information, all properties are read as
    strings (or also as double, in the case of ``gml``), and must be
    converted by hand to the desired type. Therefore you should always
    use either ``gt`` or ``graphml``, since they implement an exact
    bit-for-bit representation of all supported :ref:`sec_property_maps`
    types, except when interfacing with other software, or existing
    data, which uses ``dot`` or ``gml``.
557 558 559

A graph can be saved or loaded to a file with the :attr:`~graph_tool.Graph.save`
and :attr:`~graph_tool.Graph.load` methods, which take either a file name or a
560
file-like object. A graph can also be loaded from disc with the
561 562
:func:`~graph_tool.load_graph` function, as such:

Tiago Peixoto's avatar
Tiago Peixoto committed
563
.. testcode::
564 565 566 567 568

    g = Graph()
    #  ... fill the graph ...
    g.save("my_graph.xml.gz")    
    g2 = load_graph("my_graph.xml.gz")
569
    # g and g2 should be copies of each other
570 571 572 573 574 575 576

Graph classes can also be pickled with the :mod:`pickle` module.


An Example: Building a Price Network
------------------------------------

577 578
A Price network is the first known model of a "scale-free" graph,
invented in 1976 by `de Solla Price
579
<http://en.wikipedia.org/wiki/Derek_J._de_Solla_Price>`_. It is defined
580 581 582 583 584 585 586 587 588 589
dynamically, where at each time step a new vertex is added to the graph,
and connected to an old vertex, with probability proportional to its
in-degree. The following program implements this construction using
``graph-tool``.

.. note::

   Note that it would be much faster just to use the
   :func:`~graph_tool.generation.price_network` function, which is
   implemented in C++, as opposed to the script below which is in pure
Tiago Peixoto's avatar
Tiago Peixoto committed
590
   Python. The code below is merely a demonstration on how to use the
591
   library.
592

593 594 595
.. literalinclude:: price.py
   :linenos:

596 597
The following is what should happen when the program is run.

598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617
.. testcode::
   :hide:

   from price import *
   clf()

.. testoutput::

    vertex: 36063 in-degree: 0 out-degree: 1 age: 36063
    vertex: 9075 in-degree: 4 out-degree: 1 age: 9075
    vertex: 5967 in-degree: 3 out-degree: 1 age: 5967
    vertex: 1113 in-degree: 7 out-degree: 1 age: 1113
    vertex: 25 in-degree: 84 out-degree: 1 age: 25
    vertex: 10 in-degree: 541 out-degree: 1 age: 10
    vertex: 5 in-degree: 140 out-degree: 1 age: 5
    vertex: 2 in-degree: 459 out-degree: 1 age: 2
    vertex: 1 in-degree: 520 out-degree: 1 age: 1
    vertex: 0 in-degree: 210 out-degree: 0 age: 0
    Nowhere else to go... We found the main hub!

Tiago Peixoto's avatar
Tiago Peixoto committed
618 619 620
Below is the degree distribution, with :math:`10^5` nodes (in order to
the asymptotic behavior to be even clearer, the number of vertices needs
to be increased to something like :math:`10^6` or :math:`10^7`).
621

Tiago Peixoto's avatar
Tiago Peixoto committed
622
.. figure:: price-deg-dist.*
623
   :align: center
624

Tiago Peixoto's avatar
Tiago Peixoto committed
625
   In-degree distribution of a price network with :math:`10^5` nodes.
626

627 628 629 630 631 632 633

We can draw the graph to see some other features of its topology. For that we
use the :func:`~graph_tool.draw.graph_draw` function.

.. testcode::

   g = load_graph("price.xml.gz")
634
   age = g.vertex_properties["age"]
635

636 637
   pos = sfdp_layout(g)
   graph_draw(g, pos, output_size=(1000, 1000), vertex_color=[1,1,1,0],
638
              vertex_fill_color=age, vertex_size=1, edge_pen_width=1.2,
639
              vcmap=matplotlib.cm.gist_heat_r, output="price.png")
640

641
.. figure:: price.*
642 643
   :align: center

644
   A Price network with :math:`10^5` nodes. The vertex colors represent
645
   the age of the vertex, from older (red) to newer (black).
646

647 648
.. _sec_graph_filtering:

649 650 651
Graph filtering
---------------

652 653 654 655
One of the very nice features of ``graph-tool`` is the "on-the-fly" filtering of
edges and/or vertices. Filtering means the temporary masking of vertices/edges,
which are in fact not really removed, and can be easily recovered. Vertices or
edges which are to be filtered should be marked with a
656 657 658 659 660 661 662 663
:class:`~graph_tool.PropertyMap` with value type ``bool``, and then set with
:meth:`~graph_tool.Graph.set_vertex_filter` or
:meth:`~graph_tool.Graph.set_edge_filter` methods. By default, vertex or edges
with value "1" are `kept` in the graphs, and those with value "0" are filtered
out. This behaviour can be modified with the ``inverted`` parameter of the
respective functions. All manipulation functions and algorithms will work as if
the marked edges or vertices were removed from the graph, with minimum overhead.

Tiago Peixoto's avatar
Tiago Peixoto committed
664 665 666 667 668 669
.. note::

    It is important to emphasize that the filtering functionality does not add
    any overhead when the graph is not being filtered. In this case, the
    algorithms run just as fast as if the filtering functionality didn't exist.

670 671
Here is an example which obtains the minimum spanning tree of a graph,
using the function :func:`~graph_tool.topology.min_spanning_tree` and
672 673 674 675 676
edge filtering.

.. testcode::
   :hide:

677
   from numpy.random import *
678 679 680 681
   seed(42)

.. testcode::

682
   g, pos = triangulation(random((500, 2)) * 4, type="delaunay")
683
   tree = min_spanning_tree(g)
Tiago Peixoto's avatar
Tiago Peixoto committed
684
   graph_draw(g, pos=pos, edge_color=tree, output="min_tree.svg")
685 686 687 688

.. testcode::
   :hide:

689
   graph_draw(g, pos=pos, edge_color=tree, output_size=(400, 400),
Tiago Peixoto's avatar
Tiago Peixoto committed
690
              output="min_tree.pdf")
691

692 693 694 695 696

The ``tree`` property map has a bool type, with value "1" if the edge belongs to
the tree, and "0" otherwise. Below is an image of the original graph, with the
marked edges.

697
.. figure:: min_tree.*
698
   :align: center
Tiago Peixoto's avatar
Tiago Peixoto committed
699
   :figwidth: 400
700 701 702 703 704

We can now filter out the edges which don't belong to the minimum spanning tree.

.. testcode::

705
   g.set_edge_filter(tree)
Tiago Peixoto's avatar
Tiago Peixoto committed
706
   graph_draw(g, pos=pos, output="min_tree_filtered.svg")
707 708 709 710

.. testcode::
   :hide:

Tiago Peixoto's avatar
Tiago Peixoto committed
711
   graph_draw(g, pos=pos, output_size=(400, 400), output="min_tree_filtered.pdf")
712 713 714

This is how the graph looks when filtered:

715
.. figure:: min_tree_filtered.*
716
   :align: center
Tiago Peixoto's avatar
Tiago Peixoto committed
717
   :figwidth: 400
718 719

Everything should work transparently on the filtered graph, simply as if the
Tiago Peixoto's avatar
Tiago Peixoto committed
720 721 722
masked edges were removed. For instance, the following code will calculate the
:func:`~graph_tool.centrality.betweenness` centrality of the edges and vertices,
and draws them as colors and line thickness in the graph.
723 724 725

.. testcode::

Tiago Peixoto's avatar
Tiago Peixoto committed
726
    bv, be = betweenness(g)
727 728
    be.a /= be.a.max() / 5
    graph_draw(g, pos=pos, vertex_fill_color=bv, edge_pen_width=be,
Tiago Peixoto's avatar
Tiago Peixoto committed
729
               output="filtered-bt.svg")
730 731 732 733 734

.. testcode::
   :hide:

   graph_draw(g, pos=pos, vertex_fill_color=bv, edge_pen_width=be,
Tiago Peixoto's avatar
Tiago Peixoto committed
735
              output_size=(400, 400), output="filtered-bt.pdf")
736

737
.. figure:: filtered-bt.*
Tiago Peixoto's avatar
Tiago Peixoto committed
738
   :align: center
Tiago Peixoto's avatar
Tiago Peixoto committed
739
   :figwidth: 400
740 741 742 743 744 745 746


The original graph can be recovered by setting the edge filter to ``None``.

.. testcode::

    g.set_edge_filter(None)
Tiago Peixoto's avatar
Tiago Peixoto committed
747
    bv, be = betweenness(g)
748 749
    be.a /= be.a.max() / 5
    graph_draw(g, pos=pos, vertex_fill_color=bv, edge_pen_width=be,
Tiago Peixoto's avatar
Tiago Peixoto committed
750
               output="nonfiltered-bt.svg")
751 752 753 754 755

.. testcode::
   :hide:

   graph_draw(g, pos=pos, vertex_fill_color=bv, edge_pen_width=be,
Tiago Peixoto's avatar
Tiago Peixoto committed
756
              output_size=(400, 400), output="nonfiltered-bt.pdf")
757

758
.. figure:: nonfiltered-bt.*
Tiago Peixoto's avatar
Tiago Peixoto committed
759
   :align: center
Tiago Peixoto's avatar
Tiago Peixoto committed
760
   :figwidth: 400
761 762 763 764 765 766 767 768

Everything works in analogous fashion with vertex filtering.

Additionally, the graph can also have its edges reversed with the
:meth:`~graph_tool.Graph.set_reversed` method. This is also an :math:`O(1)`
operation, which does not really modify the graph.

As mentioned previously, the directedness of the graph can also be changed
769 770
"on-the-fly" with the :meth:`~graph_tool.Graph.set_directed` method.

771 772
.. _sec_graph_views:

773 774 775 776 777 778 779 780 781 782 783
Graph views
^^^^^^^^^^^

It is often desired to work with filtered and unfiltered graphs
simultaneously, or to temporarily create a filtered version of graph for
some specific task. For these purposes, graph-tool provides a
:class:`~graph_tool.GraphView` class, which represents a filtered "view"
of a graph, and behaves as an independent graph object, which shares the
underlying data with the original graph. Graph views are constructed by
instantiating a :class:`~graph_tool.GraphView` class, and passing a
graph object which is supposed to be filtered, together with the desired
Tiago Peixoto's avatar
Tiago Peixoto committed
784 785
filter parameters. For example, to create a directed view of the graph
``g`` constructed above, one should do:
786 787 788 789 790 791 792 793 794 795

.. doctest::

    >>> ug = GraphView(g, directed=True)
    >>> ug.is_directed()
    True

Graph views also provide a much more direct and convenient approach to
vertex/edge filtering: To construct a filtered minimum spanning tree
like in the example above, one must only pass the filter property as the
796
"efilt" parameter:
797 798 799 800 801 802 803 804 805 806 807 808 809 810

.. doctest::

    >>> tv = GraphView(g, efilt=tree)

Note that this is an :math:`O(1)` operation, since it is equivalent (in
speed) to setting the filter in graph ``g`` directly, but in this case
the object ``g`` remains unmodified.

Like above, the result should be the isolated minimum spanning tree:

.. doctest::

    >>> bv, be = betweenness(tv)
811 812
    >>> be.a /= be.a.max() / 5
    >>> graph_draw(tv, pos=pos, vertex_fill_color=bv,
Tiago Peixoto's avatar
Tiago Peixoto committed
813
    ...            edge_pen_width=be, output="mst-view.svg")
814 815
    <...>

816 817 818 819 820
.. testcode::
   :hide:

   graph_draw(tv, pos=pos, vertex_fill_color=bv,
              edge_pen_width=be, output_size=(400, 400),
Tiago Peixoto's avatar
Tiago Peixoto committed
821
              output="mst-view.pdf")
822

823
.. figure:: mst-view.*
824
   :align: center
Tiago Peixoto's avatar
Tiago Peixoto committed
825
   :figwidth: 400
826 827 828 829 830 831 832 833 834 835 836 837 838

   A view of the Delaunay graph, isolating only the minimum spanning tree.

.. note::

   :class:`~graph_tool.GraphView` objects behave *exactly* like regular
   :class:`~graph_tool.Graph` objects. In fact,
   :class:`~graph_tool.GraphView` is a subclass of
   :class:`~graph_tool.Graph`. The only difference is that a
   :class:`~graph_tool.GraphView` object shares its internal data with
   its parent :class:`~graph_tool.Graph` class. Therefore, if the
   original :class:`~graph_tool.Graph` object is modified, this
   modification will be reflected immediately in the
839
   :class:`~graph_tool.GraphView` object, and vice versa.
840 841 842 843 844 845 846 847 848 849

For even more convenience, one can supply a function as filter
parameter, which takes a vertex or an edge as single parameter, and
returns ``True`` if the vertex/edge should be kept and ``False``
otherwise. For instance, if we want to keep only the most "central"
edges, we can do:

.. doctest::

    >>> bv, be = betweenness(g)
850
    >>> u = GraphView(g, efilt=lambda e: be[e] > be.a.max() / 2)
851 852

This creates a graph view ``u`` which contains only the edges of ``g``
853 854 855 856 857 858
which have a normalized betweenness centrality larger than half of the
maximum value. Note that, differently from the case above, this is an
:math:`O(E)` operation, where :math:`E` is the number of edges, since
the supplied function must be called :math:`E` times to construct a
filter property map. Thus, supplying a constructed filter map is always
faster, but supplying a function can be more convenient.
859 860 861 862 863

The graph view constructed above can be visualized as

.. doctest::

864
    >>> be.a /= be.a.max() / 5
Tiago Peixoto's avatar
Tiago Peixoto committed
865
    >>> graph_draw(u, pos=pos, vertex_fill_color=bv, output="central-edges-view.svg")
866 867
    <...>

868 869 870 871
.. testcode::
   :hide:

   graph_draw(u, pos=pos, vertex_fill_color=bv, output_size=(400, 400),
Tiago Peixoto's avatar
Tiago Peixoto committed
872
              output="central-edges-view.pdf")
873 874


875
.. figure:: central-edges-view.*
876
   :align: center
Tiago Peixoto's avatar
Tiago Peixoto committed
877
   :figwidth: 400
878 879 880 881 882 883 884 885

   A view of the Delaunay graph, isolating only the edges with
   normalized betweenness centrality larger than 0.01.

Composing graph views
"""""""""""""""""""""

Since graph views are regular graphs, one can just as easily create
886 887 888 889
graph views `of graph views`. This provides a convenient way of
composing filters. For instance, in order to isolate the minimum
spanning tree of all vertices of the example above which have a degree
larger than four, one can do:
890 891 892 893 894 895 896 897 898 899


    >>> u = GraphView(g, vfilt=lambda v: v.out_degree() > 4)
    >>> tree = min_spanning_tree(u)
    >>> u = GraphView(u, efilt=tree)

The resulting graph view can be visualized as

.. doctest::

Tiago Peixoto's avatar
Tiago Peixoto committed
900
    >>> graph_draw(u, pos=pos, output="composed-filter.svg")
901 902
    <...>

903 904 905
.. testcode::
   :hide:

Tiago Peixoto's avatar
Tiago Peixoto committed
906
   graph_draw(u, pos=pos, output_size=(400, 400), output="composed-filter.pdf")
907

908
.. figure:: composed-filter.*
909
   :align: center
Tiago Peixoto's avatar
Tiago Peixoto committed
910
   :figwidth: 400
911 912 913

   A composed view, obtained as the minimum spanning tree of all vertices
   in the graph which have a degree larger than four.