quickstart.rst 24 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
18
19
20
21
22
23
24
25
26
27
28
29
.. 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
30
graphs, one must pass a value to the ``directed`` parameter:
31
32
33
34
35

.. doctest::

   >>> ug = Graph(directed=False)

36
37
38
39
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,
40
41
42
43
44
45
46

.. doctest::

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

47
48
49
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:
50
51
52
53

.. doctest::

   >>> g1 = Graph()
54
   >>> # ... construct g1 ...
55
56
   >>> g2 = Graph(g1)                 # g1 and g2 are copies

57
58
59
60
61
62
63
64
65
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``.
66
67
68

.. doctest::

69
70
   >>> v1 = g.add_vertex()
   >>> v2 = g.add_vertex()
71

72
73
74
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):
75
76
77

.. doctest::

78
   >>> e = g.add_edge(v1, v2)
79

80
81
82
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.
83
84
85

.. doctest::

86
87
   >>> graph_draw(g, vertex_text=g.vertex_index, vertex_font_size=18,
   ...            output_size=(200, 200), output="two-nodes.pdf")
88
89
   <...>

90
.. figure:: two-nodes.*
91
92
93
94
   :align: center

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

96
97
98
99
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:
100
101
102

.. doctest::

103
104
105
106
107
   >>> print v1.out_degree()
   1

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

109
110
111
112
.. note::

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

114
115
116
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.
117
118
119

.. doctest::

120
121
   >>> print e.source(), e.target()
   0 1
122

123
124
125
The :meth:`~graph_tool.Graph.add_vertex` method also accepts an optional
parameter which specifies the number of vertices to create. If this
value is greater than 1, it returns a list of vertex descriptors:
126
127
128

.. doctest::

129
130
131
132
133
134
135
136
137
138
139
140
141
   >>> vlist = g.add_vertex(10)
   >>> print len(vlist)
   10

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

.. note::
142

143
   Removing a vertex is an :math:`O(N)` operation. The vertices are
144
145
146
147
148
   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 if one can guarantee that only vertices in
   the end of the list are removed (the ones last added to the graph).
149

150
   Removing an edge is an :math:`O(k_{s} + k_{t})` operation, where
Tiago Peixoto's avatar
Tiago Peixoto committed
151
152
   :math:`k_{s}` is the out-degree of the source vertex, and
   :math:`k_{t}` is the in-degree of the target vertex.
153
154
155
156
157
158

Each vertex in a graph has an unique index, which is numbered from 0 to
N-1, where N is the number of 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``.
159
160
161

.. doctest::

162
163
164
165
166
   >>> v = g.add_vertex()
   >>> print g.vertex_index[v]
   11
   >>> print int(v)
   11
167

168
169
170
171
172
173
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
200
201
202
.. note::

   Removing a vertex will cause the index of any vertex with a larger
   index to be changed, so that the indexes *always* conform to the
   :math:`[0, N-1]` range. However, property map values (see
   :ref:`sec_property_maps`) are unaffected.

Since vertices are uniquely identifiable by their indexes, there is no
need to keep the vertex descriptor lying around to access them at a
later point. If we know its index, one can obtain the descriptor of a
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
a given edge is known, it can be obtained with the
: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:
203
204
205
206

.. doctest::

   >>> e = g.add_edge(g.vertex(0), g.vertex(1))
207
208
209
210
211
212
213
214
215
216
   >>> print g.edge_index[e]
   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
unmodified, and thus will not lie in the range :math:`[0, E-1]`.  If a
new edge is added, it will reuse old indexes, in an increasing order.
217
218
219
220

.. _sec_iteration:

Iterating over vertices and edges
221
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
222

223
224
225
226
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.
227

228
229
230
231
232
233
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:
234
235
236
237
238

.. doctest::

   for v in g.vertices():
       print v
Tiago Peixoto's avatar
Tiago Peixoto committed
239
   for e in e.edges():
240
241
242
243
244
       print e

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

245
246
247
Iterating over the neighbourhood of a vertex
""""""""""""""""""""""""""""""""""""""""""""

248
249
250
The out- and in-edges of a vertex, as well as the out- and in-neighbours can be
iterated through with the :meth:`~graph_tool.Vertex.out_edges`,
:meth:`~graph_tool.Vertex.in_edges`, :meth:`~graph_tool.Vertex.out_neighbours`
251
and :meth:`~graph_tool.Vertex.in_neighbours` methods, respectively.
252
253
254
255
256
257
258

.. doctest::

   from itertools import izip
   for v in g.vertices():
      for e in v.out_edges():
          print e
259
260
      for w in v.out_neighbours():
          print w
261
262
263
264
265

      # the edge and neighbours order always match
      for e,w in izip(v.out_edges(), v.out_neighbours()):
          assert(e.target() == w)

266
267
268
269
270
271
272
273
274
275
276
277
278
The code above will print the out-edges and out-neighbours of all
vertices in the graph.

.. note::

   The ordering of the vertices and edges visited by the iterators is
   always the same as the order in which they were added to the graph
   (with the exception of the iterator returned by
   :meth:`~graph_tool.Graph.edges`). Usually, algorithms do not care
   about this order, but if it is ever needed, this inherent ordering
   can be relied upon.

.. warning::
279

280
281
282
283
284
   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
285
286
   happen.

287

288
289
290
291
292
.. _sec_property_maps:

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

293
294
295
296
297
298
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:
299
300
301
302
303

.. tabularcolumns:: |l|l|

.. table::

Tiago Peixoto's avatar
Tiago Peixoto committed
304
305
306
307
308
309
310
    ========================     ======================
     Type name                   Alias
    ========================     ======================
    ``bool``                     ``uint8_t``
    ``int32_t``                  ``int``
    ``int64_t``                  ``long``, ``long long``
    ``double``                   ``float``
Tiago Peixoto's avatar
Tiago Peixoto committed
311
312
    ``long double``
    ``string``
Tiago Peixoto's avatar
Tiago Peixoto committed
313
314
315
316
    ``vector<bool>``             ``vector<uint8_t>``
    ``vector<int32_t>``          ``vector<int>``
    ``vector<int64_t>``          ``vector<long>``, ``vector<long long>``
    ``vector<double>``           ``vector<float>``
317
318
    ``vector<long double>``
    ``vector<string>``
Tiago Peixoto's avatar
Tiago Peixoto committed
319
320
    ``python::object``           ``object``
    ========================     ======================
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337

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

338
    vprop_double = g.new_vertex_property("double")            # Double-precision floating point
339
340
    vprop_double[g.vertex(10)] = 3.1416

341
    vprop_vint = g.new_vertex_property("vector<int>")         # Vector of ints
342
343
    vprop_vint[g.vertex(40)] = [1, 3, 42, 54]
    
344
345
    eprop_dict = g.new_edge_property("object")                # Arbitrary python object. In this case, a dictionary.
    eprop_dict[g.edges().next()] = {"foo": "bar", "gnu": 42}
346

347
    gprop_bool = g.new_edge_property("bool")                  # Boolean
348
349
    gprop_bool[g] = True

350
351
Property maps with scalar value types can also be accessed as a
:class:`numpy.ndarray`, with the
Tiago Peixoto's avatar
Tiago Peixoto committed
352
:meth:`~graph_tool.PropertyMap.get_array` method, or the
353
:attr:`~graph_tool.PropertyMap.a` attribute, i.e.,
354
355
356
357
358

.. doctest::

    from numpy.random import random

359
    # this assigns random values to the vertex properties
360
361
    vprop_double.get_array()[:] = random(g.num_vertices())

362
363
364
    # or more conveniently (this is equivalent to the above)
    vprop_double.a = random(g.num_vertices())

365
366
.. _sec_internal_props:

367
Internal property maps
368
^^^^^^^^^^^^^^^^^^^^^^
369

370
371
372
373
374
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`,
375
:attr:`~graph_tool.Graph.edge_properties` or
376
377
378
:attr:`~graph_tool.Graph.graph_properties`. When inserted in the graph,
the property maps must have an unique name (between those of the same
type):
379
380
381
382
383
384
385
386

.. doctest::

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

387
.. _sec_graph_io:
388
389
390
391

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

392
393
394
Graphs can be saved and loaded in three formats: `graphml
<http://graphml.graphdrawing.org/>`_, `dot
<http://www.graphviz.org/doc/info/lang.html>`_ and
Tiago Peixoto's avatar
Tiago Peixoto committed
395
396
397
398
399
400
401
402
`gml <http://www.fim.uni-passau.de/en/fim/faculty/chairs/theoretische-informatik/projects.html>`_.
``Graphml`` is the default and preferred format, since it is by far the
most complete. 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 per hand. Therefore you should always use graphml, except when
interfacing with other software, or existing data, which uses ``dot`` or
``gml``.
403
404
405
406
407
408
409
410
411
412
413
414

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
file-like object. A graph can also be loaded from disk with the
: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")
415
    # g and g2 should be copies of each other
416
417
418
419
420
421
422

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


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

423
424
425
A Price network is the first known model of a "scale-free" graph, invented in
1976 by `de Solla Price
<http://en.wikipedia.org/wiki/Derek_J._de_Solla_Price>`_. It is defined
426
dynamically, where at each time step a new vertex is added to the graph, and
427
connected to an old vertex, with probability proportional to its in-degree. The
428
following program implements this construction using ``graph-tool``.
429

430
431
432
.. literalinclude:: price.py
   :linenos:

433
434
The following is what should happen when the program is run.

435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
.. 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!

455
This is the degree distribution, with 100000 nodes. If you want to see a broader
456
457
power law, try to increase the number of vertices to something like :math:`10^6`
or :math:`10^7`.
458

459
460
.. plot::
   :context:
461
   :align: center
462

463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
   #from pyenv import *
   from pylab import *
   import graph_tool.all as gt

   g = gt.load_graph("price.xml.gz")

   in_hist = gt.vertex_hist(g, "in")

   figure()
   y = in_hist[0]
   err = sqrt(in_hist[0])
   err[err >= y] = y[err >= y] - 1e-2
   errorbar(in_hist[1][:-1], in_hist[0], fmt="o", yerr=err,
            label="in")
   gca().set_yscale("log")
   gca().set_xscale("log")
   gca().set_ylim(1e-1, 1e5)
   gca().set_xlim(0.8, 1e3)
   subplots_adjust(left=0.2, bottom=0.2)
   xlabel("$k_{in}$")
   ylabel("$NP(k_{in})$")
   Title ("In-degree distribution of a price network with $10^5$ nodes.")
   tight_layout()
   show()

488
489
490
491
492
493
494

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")
495
   age = g.vertex_properties["age"]
496
497
498
   graph_draw(g, output_size=(1000, 1000), vertex_color=age,
              vertex_fill_color=age, vertex_size=2.5, edge_pen_width=1.5,
              output="price.png")
499

500
.. figure:: price.*
501
502
   :align: center

503
504
   A Price network with :math:`10^5` nodes. The vertex colors represent
   the age of the vertex, from older (red) to newer (blue).
505

506
507
.. _sec_graph_filtering:

508
509
510
Graph filtering
---------------

511
512
513
514
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
515
516
517
518
519
520
521
522
: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
523
524
525
526
527
528
.. 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.

529
530
Here is an example which obtains the minimum spanning tree of a graph,
using the function :func:`~graph_tool.topology.min_spanning_tree` and
531
532
533
534
535
edge filtering.

.. testcode::
   :hide:

536
   from numpy.random import *
537
538
539
540
   seed(42)

.. testcode::

541
   g, pos = triangulation(random((500, 2)) * 4, type="delaunay")
542
   tree = min_spanning_tree(g)
543
544
   graph_draw(g, pos=pos, edge_color=tree, output_size=(400, 400),
              output="min_tree.pdf")
545
546
547
548
549

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.

550
.. figure:: min_tree.*
551
552
553
554
555
556
557
   :align: center

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

.. testcode::

    g.set_edge_filter(tree)
558
    graph_draw(g, pos=pos, output_size=(400, 400), output="min_tree_filtered.pdf")
559
560
561

This is how the graph looks when filtered:

562
.. figure:: min_tree_filtered.*
563
564
565
   :align: center

Everything should work transparently on the filtered graph, simply as if the
Tiago Peixoto's avatar
Tiago Peixoto committed
566
567
568
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.
569
570
571

.. testcode::

Tiago Peixoto's avatar
Tiago Peixoto committed
572
    bv, be = betweenness(g)
573
574
575
    be.a /= be.a.max() / 5
    graph_draw(g, pos=pos, vertex_fill_color=bv, edge_pen_width=be,
               output_size=(400, 400), output="filtered-bt.pdf")
576

577
.. figure:: filtered-bt.*
Tiago Peixoto's avatar
Tiago Peixoto committed
578
   :align: center
579
580
581
582
583
584
585


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
586
    bv, be = betweenness(g)
587
588
589
    be.a /= be.a.max() / 5
    graph_draw(g, pos=pos, vertex_fill_color=bv, edge_pen_width=be,
               output_size=(400, 400), output="nonfiltered-bt.pdf")
590

591
.. figure:: nonfiltered-bt.*
Tiago Peixoto's avatar
Tiago Peixoto committed
592
   :align: center
593
594
595
596
597
598
599
600

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

603
604
.. _sec_graph_views:

605
606
607
608
609
610
611
612
613
614
615
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
616
617
filter parameters. For example, to create a directed view of the graph
``g`` constructed above, one should do:
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642

.. 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
"efilter" parameter:

.. 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)
643
644
645
646
    >>> be.a /= be.a.max() / 5
    >>> graph_draw(tv, pos=pos, vertex_fill_color=bv,
    ...            edge_pen_width=be, output_size=(400, 400),
    ...            output="mst-view.pdf")
647
648
649
    <...>


650
.. figure:: mst-view.*
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
   :align: center

   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
   :class:`~graph_tool.GraphView` object, and vice-versa.

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

This creates a graph view ``u`` which contains only the edges of ``g``
679
680
681
682
683
684
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.
685
686
687
688
689

The graph view constructed above can be visualized as

.. doctest::

690
691
692
    >>> be.a /= be.a.max() / 5
    >>> graph_draw(u, pos=pos, vertex_fill_color=bv, output_size=(400, 400),
    ... output="central-edges-view.pdf")
693
694
    <...>

695
.. figure:: central-edges-view.*
696
697
698
699
700
701
702
703
704
   :align: center

   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
705
706
707
708
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:
709
710
711
712
713
714
715
716
717
718


    >>> 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::

719
    >>> graph_draw(u, pos=pos, output_size=(400, 400), output="composed-filter.pdf")
720
721
    <...>

722
.. figure:: composed-filter.*
723
724
725
726
   :align: center

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