quickstart.rst 28.7 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
197
198
199
200
201
202
203
204
205
206
207
208
.. 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:
   
   .. code::

       # '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
Tiago Peixoto's avatar
Tiago Peixoto committed
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
285
286
287

.. doctest::

   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

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

295
Iterating over the neighborhood of a vertex
296
297
""""""""""""""""""""""""""""""""""""""""""""

298
The out- and in-edges of a vertex, as well as the out- and in-neighbors can be
299
iterated through with the :meth:`~graph_tool.Vertex.out_edges`,
300
301
:meth:`~graph_tool.Vertex.in_edges`, :meth:`~graph_tool.Vertex.out_neighbors`
and :meth:`~graph_tool.Vertex.in_neighbors` methods, respectively.
302
303
304
305
306
307

.. doctest::

   from itertools import izip
   for v in g.vertices():
      for e in v.out_edges():
Tiago Peixoto's avatar
Tiago Peixoto committed
308
          print(e)
309
      for w in v.out_neighbors():
Tiago Peixoto's avatar
Tiago Peixoto committed
310
          print(w)
311

312
313
      # the edge and neighbors order always match
      for e, w in izip(v.out_edges(), v.out_neighbors()):
314
          assert e.target() == w
315

316
The code above will print the out-edges and out-neighbors of all
317
318
319
vertices in the graph.

.. warning::
320

321
322
323
324
325
   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
326
   happen.
327

328
329
330
331
332
333
334
335
336
337
338
339
340
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`,
341
342
:meth:`~graph_tool.Graph.get_out_neighbors`,
:meth:`~graph_tool.Graph.get_in_neighbors`,
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
: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::

   [1 0 1 0 0 0 0 0 0 0 0 0]

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
   
369
370
371
372
373
.. _sec_property_maps:

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

374
375
376
377
378
379
Property maps are a way of associating additional information to the
vertices, edges or to the graph itself. There are thus three types of
property maps: vertex, edge and graph. All of them are handled by the
same class, :class:`~graph_tool.PropertyMap`. Each created property map
has an associated *value type*, which must be chosen from the predefined
set:
380
381
382
383
384

.. tabularcolumns:: |l|l|

.. table::

Tiago Peixoto's avatar
Tiago Peixoto committed
385
386
387
388
    ========================     ======================
     Type name                   Alias
    ========================     ======================
    ``bool``                     ``uint8_t``
389
    ``int16_t``                  ``short``
Tiago Peixoto's avatar
Tiago Peixoto committed
390
391
392
    ``int32_t``                  ``int``
    ``int64_t``                  ``long``, ``long long``
    ``double``                   ``float``
Tiago Peixoto's avatar
Tiago Peixoto committed
393
394
    ``long double``
    ``string``
Tiago Peixoto's avatar
Tiago Peixoto committed
395
    ``vector<bool>``             ``vector<uint8_t>``
396
    ``vector<int16_t>``          ``vector<short>``
Tiago Peixoto's avatar
Tiago Peixoto committed
397
398
399
    ``vector<int32_t>``          ``vector<int>``
    ``vector<int64_t>``          ``vector<long>``, ``vector<long long>``
    ``vector<double>``           ``vector<float>``
400
401
    ``vector<long double>``
    ``vector<string>``
Tiago Peixoto's avatar
Tiago Peixoto committed
402
403
    ``python::object``           ``object``
    ========================     ======================
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420

New property maps can be created for a given graph by calling the
:meth:`~graph_tool.Graph.new_vertex_property`, :meth:`~graph_tool.Graph.new_edge_property`, or
:meth:`~graph_tool.Graph.new_graph_property`, for each map type. The values are then
accessed by vertex or edge descriptors, or the graph itself, as such:

.. doctest::

    from itertools import izip
    from numpy.random import randint

    g = Graph()
    g.add_vertex(100)
    # insert some random links
    for s,t in izip(randint(0, 100, 100), randint(0, 100, 100)):
        g.add_edge(g.vertex(s), g.vertex(t))

421
    vprop_double = g.new_vertex_property("double")            # Double-precision floating point
422
423
    vprop_double[g.vertex(10)] = 3.1416

424
    vprop_vint = g.new_vertex_property("vector<int>")         # Vector of ints
425
426
    vprop_vint[g.vertex(40)] = [1, 3, 42, 54]
    
427
428
    eprop_dict = g.new_edge_property("object")                # Arbitrary python object.
    eprop_dict[g.edges().next()] = {"foo": "bar", "gnu": 42}  # In this case, a dict.
429

Tiago Peixoto's avatar
Tiago Peixoto committed
430
    gprop_bool = g.new_graph_property("bool")                  # Boolean
431
432
    gprop_bool[g] = True

433
434
Property maps with scalar value types can also be accessed as a
:class:`numpy.ndarray`, with the
Tiago Peixoto's avatar
Tiago Peixoto committed
435
:meth:`~graph_tool.PropertyMap.get_array` method, or the
436
:attr:`~graph_tool.PropertyMap.a` attribute, i.e.,
437
438
439
440
441

.. doctest::

    from numpy.random import random

442
    # this assigns random values to the vertex properties
443
444
    vprop_double.get_array()[:] = random(g.num_vertices())

445
446
447
    # or more conveniently (this is equivalent to the above)
    vprop_double.a = random(g.num_vertices())

448
449
.. _sec_internal_props:

450
Internal property maps
451
^^^^^^^^^^^^^^^^^^^^^^
452

453
454
455
456
457
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`,
458
:attr:`~graph_tool.Graph.edge_properties` or
459
460
461
: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,
462
463
the property maps must have an unique name (between those of the same
type):
464
465
466
467
468
469
470
471

.. doctest::

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

472
473
474
475
476
477
478
479
480
481
482
483
484
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

485
486
487
488
489
For convenience, the internal property maps can also be accessed via
attributes:

.. doctest::

Tiago Peixoto's avatar
Tiago Peixoto committed
490
491
492
493
494
495
    >>> 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
496

497
.. _sec_graph_io:
498
499
500
501

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

502
Graphs can be saved and loaded in four formats: `graphml
503
<http://graphml.graphdrawing.org/>`_, `dot
504
505
<http://www.graphviz.org/doc/info/lang.html>`_, `gml
<http://www.fim.uni-passau.de/en/fim/faculty/chairs/theoretische-informatik/projects.html>`_
506
507
508
509
and a custom binary format ``gt`` (see :ref:`sec_gt_format`). 

.. warning::

Tiago Peixoto's avatar
Tiago Peixoto committed
510
511
512
513
    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.
514
515
516
517
518
519
520
521
522

    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``.
523
524
525

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
526
file-like object. A graph can also be loaded from disc with the
527
528
529
530
531
532
533
534
:func:`~graph_tool.load_graph` function, as such:

.. doctest::

    g = Graph()
    #  ... fill the graph ...
    g.save("my_graph.xml.gz")    
    g2 = load_graph("my_graph.xml.gz")
535
    # g and g2 should be copies of each other
536
537
538
539
540
541
542

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


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

543
544
A Price network is the first known model of a "scale-free" graph,
invented in 1976 by `de Solla Price
545
<http://en.wikipedia.org/wiki/Derek_J._de_Solla_Price>`_. It is defined
546
547
548
549
550
551
552
553
554
555
556
557
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
   python. The code below is merely a demonstration on how to use the
   library.
558

559
560
561
.. literalinclude:: price.py
   :linenos:

562
563
The following is what should happen when the program is run.

564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
.. 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
584
585
586
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`).
587

Tiago Peixoto's avatar
Tiago Peixoto committed
588
.. figure:: price-deg-dist.*
589
   :align: center
590

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

593
594
595
596
597
598
599

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")
600
   age = g.vertex_properties["age"]
601

602
603
   pos = sfdp_layout(g)
   graph_draw(g, pos, output_size=(1000, 1000), vertex_color=[1,1,1,0],
604
              vertex_fill_color=age, vertex_size=1, edge_pen_width=1.2,
605
              vcmap=matplotlib.cm.gist_heat_r, output="price.png")
606

607
.. figure:: price.*
608
609
   :align: center

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

613
614
.. _sec_graph_filtering:

615
616
617
Graph filtering
---------------

618
619
620
621
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
622
623
624
625
626
627
628
629
: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
630
631
632
633
634
635
.. 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.

636
637
Here is an example which obtains the minimum spanning tree of a graph,
using the function :func:`~graph_tool.topology.min_spanning_tree` and
638
639
640
641
642
edge filtering.

.. testcode::
   :hide:

643
   from numpy.random import *
644
645
646
647
   seed(42)

.. testcode::

648
   g, pos = triangulation(random((500, 2)) * 4, type="delaunay")
649
   tree = min_spanning_tree(g)
Tiago Peixoto's avatar
Tiago Peixoto committed
650
   graph_draw(g, pos=pos, edge_color=tree, output="min_tree.svg")
651
652
653
654

.. testcode::
   :hide:

655
   graph_draw(g, pos=pos, edge_color=tree, output_size=(400, 400),
Tiago Peixoto's avatar
Tiago Peixoto committed
656
              output="min_tree.pdf")
657

658
659
660
661
662

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.

663
.. figure:: min_tree.*
664
   :align: center
Tiago Peixoto's avatar
Tiago Peixoto committed
665
   :figwidth: 400
666
667
668
669
670

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

.. testcode::

671
   g.set_edge_filter(tree)
Tiago Peixoto's avatar
Tiago Peixoto committed
672
   graph_draw(g, pos=pos, output="min_tree_filtered.svg")
673
674
675
676

.. testcode::
   :hide:

Tiago Peixoto's avatar
Tiago Peixoto committed
677
   graph_draw(g, pos=pos, output_size=(400, 400), output="min_tree_filtered.pdf")
678
679
680

This is how the graph looks when filtered:

681
.. figure:: min_tree_filtered.*
682
   :align: center
Tiago Peixoto's avatar
Tiago Peixoto committed
683
   :figwidth: 400
684
685

Everything should work transparently on the filtered graph, simply as if the
Tiago Peixoto's avatar
Tiago Peixoto committed
686
687
688
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.
689
690
691

.. testcode::

Tiago Peixoto's avatar
Tiago Peixoto committed
692
    bv, be = betweenness(g)
693
694
    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
695
               output="filtered-bt.svg")
696
697
698
699
700

.. testcode::
   :hide:

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

703
.. figure:: filtered-bt.*
Tiago Peixoto's avatar
Tiago Peixoto committed
704
   :align: center
Tiago Peixoto's avatar
Tiago Peixoto committed
705
   :figwidth: 400
706
707
708
709
710
711
712


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
713
    bv, be = betweenness(g)
714
715
    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
716
               output="nonfiltered-bt.svg")
717
718
719
720
721

.. testcode::
   :hide:

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

724
.. figure:: nonfiltered-bt.*
Tiago Peixoto's avatar
Tiago Peixoto committed
725
   :align: center
Tiago Peixoto's avatar
Tiago Peixoto committed
726
   :figwidth: 400
727
728
729
730
731
732
733
734

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
735
736
"on-the-fly" with the :meth:`~graph_tool.Graph.set_directed` method.

737
738
.. _sec_graph_views:

739
740
741
742
743
744
745
746
747
748
749
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
750
751
filter parameters. For example, to create a directed view of the graph
``g`` constructed above, one should do:
752
753
754
755
756
757
758
759
760
761

.. 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
762
"efilt" parameter:
763
764
765
766
767
768
769
770
771
772
773
774
775
776

.. 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)
777
778
    >>> be.a /= be.a.max() / 5
    >>> graph_draw(tv, pos=pos, vertex_fill_color=bv,
Tiago Peixoto's avatar
Tiago Peixoto committed
779
    ...            edge_pen_width=be, output="mst-view.svg")
780
781
    <...>

782
783
784
785
786
.. 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
787
              output="mst-view.pdf")
788

789
.. figure:: mst-view.*
790
   :align: center
Tiago Peixoto's avatar
Tiago Peixoto committed
791
   :figwidth: 400
792
793
794
795
796
797
798
799
800
801
802
803
804

   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
805
   :class:`~graph_tool.GraphView` object, and vice versa.
806
807
808
809
810
811
812
813
814
815

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)
816
    >>> u = GraphView(g, efilt=lambda e: be[e] > be.a.max() / 2)
817
818

This creates a graph view ``u`` which contains only the edges of ``g``
819
820
821
822
823
824
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.
825
826
827
828
829

The graph view constructed above can be visualized as

.. doctest::

830
    >>> be.a /= be.a.max() / 5
Tiago Peixoto's avatar
Tiago Peixoto committed
831
    >>> graph_draw(u, pos=pos, vertex_fill_color=bv, output="central-edges-view.svg")
832
833
    <...>

834
835
836
837
.. testcode::
   :hide:

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


841
.. figure:: central-edges-view.*
842
   :align: center
Tiago Peixoto's avatar
Tiago Peixoto committed
843
   :figwidth: 400
844
845
846
847
848
849
850
851

   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
852
853
854
855
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:
856
857
858
859
860
861
862
863
864
865


    >>> 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
866
    >>> graph_draw(u, pos=pos, output="composed-filter.svg")
867
868
    <...>

869
870
871
.. testcode::
   :hide:

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

874
.. figure:: composed-filter.*
875
   :align: center
Tiago Peixoto's avatar
Tiago Peixoto committed
876
   :figwidth: 400
877
878
879

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