The graph_tool module provides a Graph class and several algorithms that operate on it. The internals of this class, and of most algorithms, are written in C++ for performance.
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:
>>> from graph_tool.all import *
In the following, it will always be assumed that the previous line was run.
An empty graph can be created by instantiating a Graph class:
>>> g = Graph()
By default, newly created graphs are always directed. To construct undirected graphs, one must pass the directed parameter:
>>> ug = Graph(directed=False)
A graph can always be switched on-the-fly from directed to undirected (and vice versa), with the set_directed() method. The “directedness” of the graph can be queried with the is_directed() method,
>>> ug = Graph()
>>> ug.set_directed(False)
>>> assert(ug.is_directed() == False)
A graph can also be created from another graph, in which case the entire graph (and its internal property maps, see Property maps) is copied:
>>> g1 = Graph()
>>> # ... populate g1 ...
>>> g2 = Graph(g1) # g1 and g2 are copies
Once a graph is created, it can be populated with vertices and edges. A vertex can be added with the add_vertex() method,
>>> v = g.add_vertex()
which returns an instance of a Vertex class, also called a vertex descriptor. The 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 vertices:
>>> vlist = g.add_vertex(10)
>>> print len(vlist)
10
Each vertex 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 vertex_index attribute of the graph (which is a property map, see Property maps), or by converting the vertex descriptor to an int.
>>> v = g.add_vertex()
>>> print g.vertex_index[v], int(v)
11 11
There is no need to keep the vertex descriptor lying around to access them at a later point: One can obtain the descriptor of a vertex with a given index using the vertex() method,
>>> print g.vertex(8)
8
Another option is to iterate through the vertices, as described in section Iterating over vertices and edges.
Once we have some vertices in the graph, we can create some edges between them with the add_edge() method, which returns an edge descriptor (an instance of the Edge class).
>>> v1 = g.add_vertex()
>>> v2 = g.add_vertex()
>>> e = g.add_edge(v1, v2)
Edges also have an unique index, which is given by the edge_index property:
>>> print g.edge_index[e]
0
Unlike the vertices, edge indexes are not guaranteed to be continuous in any range, but they are always unique.
Both vertex and edge descriptors have methods which query associate information, such as in_degree(), out_degree(), source() and target():
>>> v1 = g.add_vertex()
>>> v2 = g.add_vertex()
>>> e = g.add_edge(v1, v2)
>>> print v1.out_degree(), v2.in_degree()
1 1
>>> assert(e.source() == v1 and e.target() == v2)
Edges and vertices can also be removed at any time with the remove_vertex() and remove_edge() methods,
>>> e = g.add_edge(g.vertex(0), g.vertex(1))
>>> g.remove_edge(e) # e no longer exists
>>> g.remove_vertex(g.vertex(1)) # the second vertex is also gone
Algorithms must often iterate through the vertices, edges, out edge, etc. of the graph. The Graph and Edge classes provide the necessary iterators for doing so. The iterators always give back edge or vertex descriptors.
In order to iterate through the vertices or edges of the graph, the vertices() and edges() methods should be used, as such:
for v in g.vertices():
print v
for e in e.vertices():
print e
The code above will print the vertices and edges of the graph in the order they are found.
The out- and in-edges of a vertex, as well as the out- and in-neighbours can be iterated through with the out_edges(), in_edges(), out_neighbours() and in_neighbours() respectively.
from itertools import izip
for v in g.vertices():
for e in v.out_edges():
print e
for e in v.out_neighbours():
print e
# the edge and neighbours order always match
for e,w in izip(v.out_edges(), v.out_neighbours()):
assert(e.target() == w)
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 instances of the same class, PropertyMap. Each property map has an associated value type, which must be chosen from the predefined set:
| Type name | Aliases |
|---|---|
| bool | uint8_t |
| int32_t | int |
| int64_t | long |
| double | float |
| long double | |
| string | |
| vector<bool> | vector<uint8_t> |
| vector<int32_t> | vector<int> |
| vector<int64_t> | vector<long> |
| vector<double> | vector<float> |
| vector<long double> | |
| vector<string> | |
| python::object | object |
New property maps can be created for a given graph by calling the new_vertex_property(), new_edge_property(), or new_graph_property(), for each map type. The values are then accessed by vertex or edge descriptors, or the graph itself, as such:
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))
vprop_double = g.new_vertex_property("double")
vprop_vint = g.new_vertex_property("vector<int>")
eprop_dict = g.new_edge_property("object")
gprop_bool = g.new_edge_property("bool")
vprop_double[g.vertex(10)] = 3.1416
vprop_vint[g.vertex(40)] = [1, 3, 42, 54]
eprop_dict[g.edges().next()] = {"foo":"bar", "gnu":42}
gprop_bool[g] = True
Property maps with scalar value types can also be accessed as a numpy ndarray, with the get_array() method, i.e.,
from numpy.random import random
# this assigns random values to the properties
vprop_double.get_array()[:] = random(g.num_vertices())
Any created property map can be made “internal” to the respective 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 vertex_properties, edge_properties or graph_properties. When inserted in the graph, the property maps must have an unique name (between those of the same type):
>>> eprop = g.new_edge_property("string")
>>> g.edge_properties["some name"] = eprop
>>> g.list_properties()
some name (edge) (type: string)
Graphs can be saved and loaded in two formats: graphml and dot. Graphml is the default and preferred format. The dot format is also supported, but since it contains no type information, all properties are read later as strings, and must be converted per hand. Therefore you should always use graphml, except when interfacing with another software which expects dot format.
A graph can be saved or loaded to a file with the save and load methods, which take either a file name or a file-like object. A graph can also be loaded from disk with the load_graph() function, as such:
g = Graph()
# ... fill the graph ...
g.save("my_graph.xml.gz")
g2 = load_graph("my_graph.xml.gz")
# g and g2 should be a copy of each other
Graph classes can also be pickled with the pickle module.
A Price network is the first known model of a “scale-free” graph, invented in 1976 by de Solla Price. It is defined dynamically, and 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 method using graph-tool.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 | #! /usr/bin/env python
# We probably will need some things from several places
import sys, os
from pylab import * # for plotting
from numpy.random import * # for random sampling
seed(42)
# We need to import the graph_tool module itself
from graph_tool.all import *
# let's construct a Price network (the one that existed before Barabasi). It is
# a directed network, with preferential attachment. The algorithm below is a
# very naive, and a bit slow, but quite simple.
# We start with an empty, directed graph
g = Graph()
# We want also to keep the age information for each vertex and edge. For that
# let's create some property maps
v_age = g.new_vertex_property("int")
e_age = g.new_edge_property("int")
# The final size of the network
N = 100000
# We have to start with one vertex
v = g.add_vertex()
v_age[v] = 0
# we will keep a list of the vertices. The number of times a vertex is in this
# list will give the probability of it being selected.
vlist = [v]
# let's now add the new edges and vertices
for i in xrange(1, N):
# create our new vertex
v = g.add_vertex()
v_age[v] = i
# we need to sample a new vertex to be the target, based on its in-degree +
# 1. For that, we simply randomly sample it from vlist.
i = randint(0, len(vlist))
target = vlist[i]
# add edge
e = g.add_edge(v, target)
e_age[e] = i
# put v and target in the list
vlist.append(target)
vlist.append(v)
# now we have a graph!
# let's calculate its in-degree distribution and plot it to a file
in_hist = vertex_hist(g, "in")
figure(figsize=(4,3))
errorbar(in_hist[1], in_hist[0], fmt="o", yerr=sqrt(in_hist[0]), 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("$P(k_{in})$")
savefig("deg-hist.png")
# let's do a random walk on the graph and print the age of the vertices we find,
# just for fun.
v = g.vertex(randint(0, g.num_vertices()))
for i in xrange(0, 100):
print "vertex:", v, "in-degree:", v.in_degree(), "out-degree:",\
v.out_degree(), "age:", v_age[v]
if v.out_degree() == 0:
print "Nowhere else to go... We found the main hub!"
break
n_list = []
for w in v.out_neighbours():
n_list.append(w)
v = n_list[randint(0, len(n_list))]
# let's save our graph for posterity We want to save the age properties as
# well... To do this, they must become "internal" properties, as such:
g.vertex_properties["age"] = v_age
g.edge_properties["age"] = e_age
# now we can save it
g.save("price.xml.gz")
|
The following is what should happen when the program is run.
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!
This is the degree distribution, with 100000 nodes. If you want to really see a power law, try to increase the number of vertices to something like 10^6 or 10^7.
In-degree distribution of a price network with 100000 nodes.
We can draw the graph to see some other features of its topology. For that we use the graph_draw() function.
g = load_graph("price.xml.gz")
g.remove_vertex_if(lambda v: g.vertex_index[v] >= 1000)
graph_draw(g, size=(10,10), layout="arf", output="price.png")
First 1000 nodes of a price network.
One of the very nice features from graph-tool is the “on-the-fly” filtering of edges and/or vertices. Filtering means the temporary masking of vertices/edges, which are not really removed, and can be easily recovered. Vertices or edges which are to be filtered should be marked with a PropertyMap with value type bool, and then set with set_vertex_filter() or 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.
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.
Here is an example which obtains the minimum spanning tree of a graph, using edge filtering.
g, pos = triangulation(random((500,2))*4, type="delaunay")
tree = min_spanning_tree(g)
graph_draw(g, pos=pos, pin=True, size=(8,8), ecolor=tree, output="min_tree.png")
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.
We can now filter out the edges which don’t belong to the minimum spanning tree.
g.set_edge_filter(tree)
graph_draw(g, pos=pos, pin=True, size=(8,8), output="min_tree_filtered.png")
This is how the graph looks when filtered:
Everything should work transparently on the filtered graph, simply as if the masked edges were removed. For instance, the following code will calculate the betweenness() centrality of the edges and vertices, and draws them as colors and line thickness in the graph.
bv, be = betweenness(g)
be.a *= 10
graph_draw(g, pos=pos, pin=True, size=(8,8), vsize=0.07, vcolor=bv,
eprops={"penwidth":be}, output="filtered-bt.png")
The original graph can be recovered by setting the edge filter to None.
g.set_edge_filter(None)
bv, be = betweenness(g)
be.a *= 10
graph_draw(g, pos=pos, pin=True, size=(8,8), vsize=0.07, vcolor=bv,
eprops={"penwidth":be}, output="nonfiltered-bt.png")
Everything works in analogous fashion with vertex filtering.
Additionally, the graph can also have its edges reversed with the set_reversed() method. This is also an O(1) operation, which does not really modify the graph.
As mentioned previously, the directedness of the graph can also be changed “on-the-fly” with the set_directed() method.