Writing extensions in C++¶
It’s possible to extend graphtool with code written in C++, as we explain in this text. This is useful for projectspecific code that is not available in the library, but nevertheless needs to run faster than what is possible with the pure Python API.
Note
In order to write C++ extensions, a general background on C++ with templates, the Boost Graph Library (BGL) and boost.Python is strongly recommended.
A C++ extension to graphtool consists of a compiled object file that is
imported as a Python module, and it contains one or more functions that
operate on Graph
and
PropertyMap
objects. We demonstrate with an example
that computes kcores using the
algorithm of [batagelj] (this is already implemented in
kcore_decomposition()
, but serves as a good
example).
The first part is a file kcore.hh
that defines a
function template that implements the desired algorithm:
1#include "graph_tool.hh"
2
3using namespace graph_tool;
4using namespace boost;
5using namespace std;
6
7// This template function takes a graph 'g' and a vertex property map 'core_map'
8// where the core values will be stored. Their exact types are unspecified at
9// this point.
10
11template <typename Graph, typename CoreMap>
12void kcore_decomposition(Graph& g, CoreMap core_map)
13{
14 // The vertex index is an internal property map that every graph possesses
15 typedef typename property_map<Graph, vertex_index_t>::type
16 vertex_index_map_t;
17 vertex_index_map_t vertex_index = get(vertex_index_t(), g);
18
19 // Create some auxiliary property maps
20 typedef typename vprop_map_t<size_t>::type::unchecked_t vmap_t;
21
22 vmap_t deg(vertex_index, num_vertices(g)); // Remaining degree
23 vmap_t pos(vertex_index, num_vertices(g)); // Position in bin (core)
24
25 typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
26
27 vector<vector<vertex_t>> bins; // Each bin stores the set of vertices of a
28 // core
29
30 // Put each vertex to the bin corresponding to its degree
31 for (auto v : vertices_range(g))
32 {
33 size_t k = out_degree(v, g);
34 deg[v] = k;
35 if (k >= bins.size())
36 bins.resize(k + 1);
37 bins[k].push_back(v);
38 pos[v] = bins[k].size()  1;
39 }
40
41 // Proceed from smallest bin to largest. For each vertex in bin, check the
42 // neighbours; if any of them have a larger remaining degree, reduce it by
43 // one, and put it in the correct bin.
44 for (size_t k = 0; k < bins.size(); ++k)
45 {
46 auto& bins_k = bins[k];
47 while (!bins_k.empty())
48 {
49 auto v = bins_k.back();
50 bins_k.pop_back();
51 core_map[v] = k;
52 for (auto e : out_edges_range(v, g))
53 {
54 auto u = target(e, g);
55 auto& ku = deg[u];
56 if (ku > deg[v])
57 {
58 auto& bins_ku = bins[ku];
59 auto w = bins_ku.back();
60 auto pos_w = pos[w] = pos[u];
61 bins_ku[pos_w] = w;
62 bins_ku.pop_back();
63 auto& bins_ku_m = bins[ku  1];
64 bins_ku_m.push_back(u);
65 pos[u] = bins_ku_m.size()  1;
66 ku;
67 }
68 }
69 }
70 }
71}
The second part is a compilation unit kcore.cc
that sets up the PythonC++ interface:
1#include <boost/python.hpp>
2#include "kcore.hh"
3
4// The function below will take the graph that comes from graphtool (always an
5// instance of GraphInterface) and the property map (always an instance of
6// boost::any).
7
8void kcore_bind(GraphInterface& gi, boost::any core_map)
9{
10 // We don't know the actual type of the graph represented by 'gi' and the
11 // property map 'core_map'. We need to evoke the appropriate instance of the
12 // algorithm at runtime using the gt_dispatch<>() function.
13 //
14 // The gt_dispatch<>() function takes as first argument the template
15 // function object that will be called with the correct types, and the
16 // remaining (variadic) arguments are the list of types that will be
17 // considered for every argument of the function passed in the first
18 // argument. In the case below 'all_graph_views()' represents all possible
19 // graph views (directed, undirected, filtered, reversed, etc.) and
20 // 'writable_vertex_scalar_properties' represents all vertex property maps
21 // with scalar types that are writable (this excludes the vertex index
22 // map). If we had more graphs or property maps to pass, we would simply
23 // increase the parameter list accordingly.
24 //
25 // The gt_dispatch<>() function returns an object that needs to be called
26 // with the specific objects that should be used for the dispatched call. In
27 // this case we extract the actual view from `gi.get_graph_view()` and pass
28 // the `core_map`.
29
30 gt_dispatch<>()
31 ([&](auto& g, auto core){ kcore_decomposition(g, core); },
32 all_graph_views(), writable_vertex_scalar_properties())
33 (gi.get_graph_view(), core_map);
34};
35
36// The lines below setup a Python module called 'libkcore' that reflects the
37// function 'kcore_bind' above as 'kcore' when imported from Python.
38
39BOOST_PYTHON_MODULE(libkcore)
40{
41 using namespace boost::python;
42 def("kcore", kcore_bind);
43}
When using the gt_dispatch<>() function, we can make use of the following type lists for the graph views:
List of graph views 
Description 


All possible graph views 

All directed graph views 

All undirected graph views 

All directed but reversed graph views 

All undirected, and directed but not reversed graph views 

All directed but not reversed graph views 

All unfiltered graph views 

All unfiltered and not reversed graph views 
Likewise, for the types of property maps we have:
List of property maps 
Description 


All vertex property maps 

All edge property maps 

All writable vertex property maps 

All writable edge property maps 

All scalarvalued vertex property maps 

All scalarvalued edge property maps 

All writable scalarvalued vertex property maps 

All writable scalarvalued edge property maps 

All integervalued vertex property maps 

All integervalued edge property maps 

All floatingpointvalued vertex property maps 

All floatingpointvalued edge property maps 

All vertex property maps with vector of scalar types 

All edge property maps with vector of scalar types 

All vertex property maps with vector of integer types 

All edge property maps with vector of integer types 

All vertex property maps with vector of floatingpoint types 

All edge property maps with vector of floatingpoint types 
Finally, we need to bind things from the Python side with the file
kcore.py
:
1import graph_tool
2
3# We import the C++ module (called libkcore.so)
4import libkcore
5
6# The function below is what will be used from Python, and dispatch to the the
7# C++ module.
8
9def kcore_decomposition(g, core=None):
10 if core is None:
11 core = g.new_vertex_property("int")
12
13 # For graph objects wee need to pass the internal GraphInterface which is
14 # assessed via g._Graph__graph.
15
16 # Property maps need to be passed as boost::any objects, which is done via
17 # the _get_any() method.
18
19 libkcore.kcore(g._Graph__graph, core._get_any())
20 return core
Naturally, before we can use the extension, we need to compile it. To do
this, we need to inform the compiler where to find the graphtool
include files. For that we use the pkgconfig
infrastructure, by calling pkgconfig cflags libs graphtoolpy3.7
(in case graphtool was compiled for Python 3.7). To keep things
organized, we create a Makefile
:
1CXX=g++
2CXXFLAGS=O3 fopenmp std=gnu++17 Wall fPIC `pkgconfig cflags libs graphtoolpy3.9` shared
3ALL: libkcore.so
4
5libkcore.so: kcore.hh kcore.cc
6 ${CXX} ${CXXFLAGS} kcore.cc o libkcore.so
(If you use MacOS, you may want to use a different compiler such as
clang++
.) After compiling by typing make
, we can import and use
the kcore.py
module:
>>> from kcore import kcore_decomposition
>>> g = gt.collection.data["football"]
>>> c = kcore_decomposition(g)
>>> print(c.a)
[8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8]
Rangebased iteration over vertices and edges¶
Users familiar with the BGL may have noticed that iteration over vertices and edges was done in a peculiar way in the example above. The standard BGL way of iterating is something like:
auto rg = vertices(g);
for(auto vi = rg.first; vi != rg.second; ++vi)
{
auto v = *vi; // get the vertex descriptor
}
In graphtool iteration can also be done in a more convenient way using rangebased iteration:
for(auto v : vertices_range(g))
{
// v is the vertex descriptor
}
Both approaches above are equivalent. Graphtool also provides
edges_range()
, out_edges_range()
, in_edges_range()
, etc., in
an analogous fashion.
Extracting specific property maps¶
Sometimes it’s more convenient to extract property map of known types
directly instead of relying on gt_dispatch<>()
. This can be done
simply by calling boost::any_cast
as follows:
void kcore_bind(GraphInterface& gi, boost::any core_map)
{
// Vertex property map of type int32_t
typedef typename vprop_map_t<int32_t>::type vprop_t;
vprop_t c = boost::any_cast<vprop_t>(core_map);
gt_dispatch<>()
([&](auto& g){ kcore_decomposition(g, c.get_unchecked()); },
all_graph_views()) (gi.get_graph_view());
};
Checked and unchecked property maps¶
Property maps in graphtool can either be ‘checked’ or ‘unchecked’, when they are seen from the C++ side. A checked property map automatically resizes itself if the underlying graph changes (via the addition of nodes or edges). However this involves bounds checking for every lookup, which can result in performance hit. For static graphs, it’s better to use unchecked property maps, which do not perform bounds checking (but do not adapt to a changing graph).
The default property map types are by default checked:
// vprop_t and eprop_t below are checked vertex and edge
// property maps of type int32_t
typedef typename vprop_map_t<int32_t>::type vprop_t;
typedef typename eprop_map_t<int32_t>::type eprop_t;
The type hidden in a boost::any
that comes from Python is a checked
property map. However the types propagated by gt_dispatch<>()
are by default ‘unchecked’. It’s easy to obtain checked and unchecked
versions of each kind of property map:
// core_map is of type boost::any
typedef typename vprop_map_t<int32_t>::type vprop_t;
vprop_t c = boost::any_cast<vprop_t>(core_map);
// c is a checked property map. We can obtain an unchecked version
// as follows:
auto uc = c.get_unchecked(); // The type of uc is vprop_map_t<int32_t>::type::unchecked_t
// If the underlying graph has changed size in the meantime, we
// need to specify the new size when creating the unchecked map:
auto uc2 = c.get_unchecked(10000);
// From a checked property map, we can get the checked type in a similar fashion:
auto c2 = uc.get_checked();
// c and c2 have the same type.
References¶
 batagelj
Vladimir Batagelj, Matjaž Zaveršnik, “Fast algorithms for determining (generalized) core groups in social networks”, Advances in Data Analysis and Classification Volume 5, Issue 2, pp 129145 (2011), DOI: 10.1007/s116340100079y [scihub, @tor], arXiv: cs/0310049