Exercise 1: dispatching a function to C++

Authors: Tiago P. Peixoto¹
Affiliations: ¹Inverse Complexity Lab
License: CC-BY

Take a look at the template below (available from the manual repo; no need to copy and paste.)

The first file defines a C++ function that receives a graph and a property map, and just prints its values.

#include "graph_tool.hh"

#include <iostream>

using namespace graph_tool;
using namespace boost;
using namespace std;

template <typename Graph, typename VMap>
void example(Graph& g, VMap vmap)
{
    cout << "Running on a graph with " << num_vertices(g)
         << " vertices and " << num_edges(g)
         << " edges, with vertex properties given by:" << endl;

    for (auto v : vertices_range(g))
        cout <<  vmap[v] << " ";
    cout << endl;
}

The second file is a compilation unit that dispatches the function above to the appropriate type, depending on what has been received from the Python interpreter.

#include <boost/python.hpp>
#include "example.hh"

BOOST_PYTHON_MODULE(libexample)
{
    using namespace boost::python;
    def("example",
        +[](GraphInterface& gi, std::any avmap)
        {
            gt_dispatch<>()
                ([&](auto& g, auto vmap){ example(g, vmap); },
                 all_graph_views, vertex_scalar_properties)
                (gi.get_graph_view(), avmap);
        });
}

The third file is a Python file that binds a function to the its C++ implementation defined above:

import graph_tool

import libexample

def example(g, vmap=None):
    if vmap is None:
        vmap = g.new_vertex_property("int")
    libexample.example(g._Graph__graph, vmap._get_any())
    return vmap

Finally, the Makefile below facilitates the compilation:

CXX=g++
CXXFLAGS=-O3 -fopenmp -std=gnu++17 -Wall -fPIC `pkg-config --cflags --libs graph-tool-py` -shared -DBOOST_ALLOW_DEPRECATED_HEADERS -DNDEBUG
ALL: libexample.so

libexample.so: example.hh example.cc
	${CXX} ${CXXFLAGS} example.cc -o libexample.so

We need to compile the C++ code by typing make:

$ make

!make

g++ -O3 -fopenmp -std=gnu++17 -Wall -fPIC `pkg-config --cflags --libs graph-tool-py` -shared -DBOOST_ALLOW_DEPRECATED_HEADERS -DNDEBUG example.cc -o libexample.so

Now we are ready to call the function above from Python:

from graph_tool.all import *
from example import example

g = collection.data["dolphins"]

example(g, g.vertex_index);

Running on a graph with 62 vertices and 159 edges, with vertex properties given by:
0 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 

Task 1: Modify the code above to store the number of second neighbors to the property map.¶

• Thomas (repo)
• Martina (task1)
• Max (repo)
• Sina (repo)
• Basti (repo)
• Bukyoung (tast1.hh task1.cc)

Task 2: Modify the code above to store for each vertex a vector with the 10 closest neighbors.¶

• Max (repo)
• Sina (repo)
• Basti (repo)
• Thomas (repo)
• Bukyoung (tast2.hh task2.cc)
• Martina (task2)

Task 3: Modify the code above to store the PageRank to the property map.¶

• Basti (repo)

Task 4: Modify the code above so that the function returns true if the graph is bipartite.¶

• Sina (repo)

Add your solution here as a link to a gitlab repository.

Task 5: Modify the code above so that the function returns performs some computation if the graph is undirected and another if it is directed.¶

• Bukyoung: Descriptive reciprocity (returns 1 if graph is undirected) (tast5.hh task5.cc)

Add your solution here as a link to a gitlab repository.