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 .
make
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,
solve_time=1879.5741ms
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.