Quick Start - C++ API

On this page, we explain how to use the C++ API of dejavu. If you instead want to use dejavu as a standalone solver, there is a quick start guide for this as well.

Including dejavu #

First of all, dejavu is a header-only library. You can simply add dejavu to your C++ project by including the respective header file:

#include "dejavu.h"

Note that currently, dejavu requires to be compiled with C++ version 14. By default, dejavu is compiled without assertions. We recommend activating assertions for debugging purposes (by adding the definition DEJDEBUG). Assertions do however slow the code considerably.

In the following, we explain the most important basics on how to use the library. We describe elementary data structures, graphs and symmetries, necessary to communicate with dejavu.

Graphs #

Let us first describe how graphs are represented in dejavu. The most convenient way to pass a graph is to use the static_graph class. We explain the class by constructing a simple example: a path of length 3.

We now reproduce the graph using code. First, note that the graph consists of 4 vertices and 3 edges. There are two vertices of degree 1 (the ends of the path), and two vertices of degree 2 (inner nodes of the path). The code to produce this graph is as follows:

dejavu::static_graph g;
g.initialize_graph(4, 3);          // 4 vertices, 3 edges

// add vertices
const int v0 = g.add_vertex(0, 1); // = 0
const int v1 = g.add_vertex(0, 2); // = 1
const int v2 = g.add_vertex(0, 2); // = 2
const int v3 = g.add_vertex(0, 1); // = 3

// add edges
g.add_edge(v0, v1);
g.add_edge(v1, v2);
g.add_edge(v2, v3);

We first initialize the graph with 4 vertices and 3 edges. Note that the static_graph class requires us to immediately pass the final number of vertices and edges (hence, “static”). Then, we add vertices with their corresponding degree. Again, we need to give the final degree of each vertex. Finally, we add the edges connecting the previously defined nodes as desired.

To be more precise, the function add_vertex(int color, int degree) adds a vertex to the graph, where the first parameter is the “color” of the vertex, and the second parameter the degree in the graph (the number of edges connected to the vertex). The meaning of vertex colors is that vertices of different colors can not be mapped to each other using any symmetry. A more thorough explanation can be found here.

Symmetries #

The goal of dejavu is to compute the symmetries of a given graph. Hence, we need a way of retrieving the symmetries from the solver. We have a guide describing what symmetries are, and how they can be encoded in a computer. Generally, the solver returns a generating set, which is also explained in the guide mentioned above.

On the level of the API, symmetries (that together form a generating set) are returned using a hook function. More specifically, the user provides a hook of type dejavu_hook, which is in turn called for every symmetry returned by the solver. The definition for a dejavu_hook is as follows:

typedef const 
	std::function<void(int, const int *, int, const int *)> 
	dejavu_hook;

Note that a hook has four parameters, int n, const int* p, int nsupp, const int* supp. The meaning is as follows. The integer n gives the size of the domain of the symmetry, or in simple terms, the number of vertices of the graph. The array p is an array of length n. The described symmetry maps i to p[i].

Crucially, nsupp and supp tell us which i’s are interesting at all: whenever p[i] = i, we do not want to iterate over i. To enable this, the array supp tells us all the points where p[i] != i. In particular, supp[j] for 0 <= j < nsupp gives us the j-th vertex where p[supp[j]] != supp[j]. Note that nsupp gives the size of supp. In many applications, reading symmetries in this manner is crucial for adequate performance.

An example is provided below:

void my_hook(int n, const int *p, int nsupp, const int *supp) {
	for(int j = 0; j < nsupp; ++j) {
	    const int i = supp[j];
	    // do something with p[i]
	}
}

We want to mention that in general, dejavu might return redundant or even equivalent symmetries.

Calling dejavu #

Having constructed the graph above, and ready to receive symmetries using our hook, we now want to call dejavu to compute the symmetries. This is done through the use of the class solver and method automorphisms:

dejavu::solver d;
d.automorphisms(&g, std::function<dejavu_hook>(my_hook));

It should be mentioned that it is also possible to call automorphisms without a hook:

dejavu::solver d;
d.automorphisms(&g);

After a call to automorphisms has ended, further statistics can be retrieved. For example, the size of the computed automorphism group can be retrieved and printed to console as follows:

std::cout << d.get_automorphism_group_size() << std::endl;

The automorphism computation may be prone to error: due to randomization, dejavu might miss out on some symmetries in a given run (but it will never report generators that are not symmetries). See our discussion on errors for more information. However, the solver is sometimes sure that it found the entire automorphism group. This can be retrieved using as follows:

std::cout << d.get_deterministic_termination() << std::endl;

Example #

A full example can be found below. In the example, we produce a path of length 4, pass it to dejavu, and print out all the symmetries returned by dejavu through the use of the hook function print_hook.

#include "dejavu.h"

void print_hook(int n, const int *p, int nsupp, const int *supp) {
	std::cout << "We found a symmetry: ";
	for(int j = 0; j < nsupp; ++j) {
	    const int i = supp[j];
	    // do something with p[i]
	    std::cout << i << "->" << p[i] << ", ";
	}
	std::cout << std::endl;
}

int main(int argc, char *argv[]) {
	dejavu::static_graph g;
	g.initialize_graph(4, 3);          // 3 vertices, 2 edges

	// add vertices
	const int v0 = g.add_vertex(0, 1); // = 0
	const int v1 = g.add_vertex(0, 2); // = 1
	const int v2 = g.add_vertex(0, 2); // = 2
	const int v3 = g.add_vertex(0, 1); // = 3

	// add edges
	g.add_edge(v0, v1);
	g.add_edge(v1, v2);
	g.add_edge(v2, v3);

	dejavu::solver d;
	auto hook = dejavu_hook(print_hook);
	d.automorphisms(&g, &hook);

	std::cout << "#syms " << d.get_automorphism_group_size() 
              << std::endl;
	return 0;
}

Vertex IDs #

The function add_vertex guarantees to return vertex IDs starting from 0 going up to the number of vertices. Hence, in our example above, there is no need to track vertex IDs, and the example could be simplified as follows:

#include "dejavu.h"

void print_hook(int n, const int *p, int nsupp, const int *supp) {
	std::cout << "We found a symmetry: ";
	for(int j = 0; j < nsupp; ++j) {
	    const int i = supp[j];
	    // do something with p[i]
	    std::cout << i << "->" << p[i] << ", ";
	}
	std::cout << std::endl;
}

int main(int argc, char *argv[]) {
	dejavu::static_graph g;
	g.initialize_graph(4, 3);          // 3 vertices, 2 edges

	// add vertices
	g.add_vertex(0, 1); 
	g.add_vertex(0, 2); 
	g.add_vertex(0, 2); 
	g.add_vertex(0, 1);

	// add edges
	g.add_edge(0, 1);
	g.add_edge(1, 2);
	g.add_edge(2, 3);

    dejavu::solver d;
	auto hook = dejavu_hook(print_hook);
	d.automorphisms(&g, &hook);

	std::cout << "#syms " << d.get_automorphism_group_size() 
              << std::endl;
	return 0;
}