Skip to main content
  1. Quick Start/

Quick Start - Standalone

Table of Contents

On this page, you can find a description on how to compile and use dejavu as a command-line program. If you instead want to use the C++ API, there is a quick start guide for this as well.

Compilation #

Using cmake, the project should compile without any further dependencies:

cmake .

Compilation produces a binary dejavu.

Usage #

The binary dejavu accepts files in the DIMACS graph format (see paragraph below). The program then computes the symmetry group of the graph, with several different output options (such as a generating set or group size) Only undirected graphs can be handled – but the graphs may contain vertex colors. An example call solving the graph pp-25-100 might be:

dejavu pp-25-100 

The output will end in two lines describing the result as follows:

symmetries=1.0000*10^4, deterministic=false, error=1/2^10,

Here, symmetries tells us the number of found symmetries, deterministc whether the solver terminated without error, and in case it did not error tells us the configured error probability assuming uniform random numbers.

Options are available to configure the solver, as is listed below:

Command Line Argument Effect
--err [n] sets the error to be bounded by 1/2^N, assuming uniform random numbers
--silent does not print progress of the solver
--gens prints found generators line-by-line to console
--gens-file [f] writes found generators line-by-line to file F
--grp-sz prints group size to console (even if –silent)
--pseudo-random uses pseudo random numbers (default)
--true-random uses random device of OS
--true-random-seed seeds pseudo random with random device of OS
--permute randomly permutes the given graph
--permute-seed [n] seed for the previous option with N

For example, if we want to output just the found generators of a graph, we may call the solver as follows:

dejavu k-10 --silent --gens

This gives us the following output, where each line describes a generator of the graph:

(7 8)
(6 7)
(5 6)
(4 5)
(3 4)
(2 3)
(1 2)
(0 1)
(9 0)

DIMACS graph files #

Let us explain DIMACS files with a simple example: a path of length 3:

A DIMACS graph file starts with a line describing how many vertices and edges a graph contains. In our case, this is 4 vertices and 3 edges:

p edge 4 3

Then, we can add lines each describing an (undirected) edge of the graph. Note that each edge is only added once, i.e., we only define either e 1 2 or e 2 1, but not both.

p edge 4 3
e 1 2
e 2 3
e 3 4

Additionally, we may color vertices as follows. A vertex v with color c can be defined using a line n v c.