Preprocessor ·

Table of Contents

The library contains a preprocessor that can be used in conjunction with symmetry detection tools. The dejavu solver always automatically applies the preprocessor, but it may also be used in conjunction with other tools.

Preprocessor #

The preprocessor is designed to shrink large, sparse graphs. Before giving a graph to an off-the-shelf symmetry detection solver (such as bliss, nauty, saucy, Traces), the graph is instead first handed to the preprocessor. The preprocessor shrinks the graph, in turn hopefully speeding up the subsequent solver.

Some technicalities apply, though: a hook for symmetries must be provided (a dejavu_hook), and symmetries of the reduced graph must be translated back to the original graph. The preprocessor can do the reverse translation automatically, by providing a special hook that is in turn given to the backend solver (see the examples below). The graph format used by the preprocessor is described below as well.

Example using bliss #

#include "bliss/graph.hh"
#include "dejavu/preprocessor.h"
#include "dejavu/tools/bliss_converter.h"

...

dejavu::static_graph g;

// graph must be parsed into g here!

// lets preprocess...
dejavu::preprocessor p;
// hook is a dejavu_hook callback function
p.reduce(&g, &hook);

// ...and then we give the graph to bliss: first, convert the graph
bliss::Graph bliss_graph;
convert_dejavu_to_bliss(&g, &bliss_graph);

// then call bliss
bliss::Stats bliss_stat;
bliss_graph.find_automorphisms(bliss_stat, 
    dejavu::preprocessor::bliss_hook, (void*) &p);

// done!

Note that the bliss_hook uses the field p.saved_hook to call the user-defined dejavu_hook (i.e., in the example above hook). This also holds for all other solvers described below.

Example using nauty #

#include "dejavu/preprocessor.h"
#include "dejavu/tools/nauty_converter.h"
#include "nauty/naugroup.h"

...

dejavu::static_graph g;

// graph must be parsed into g here!

// lets preprocess...
dejavu::preprocessor p;
// hook is a dejavu_hook callback function
p.reduce(&g, &hook);

// ...and then we give the graph to nauty: first, convert the graph
sparsegraph nauty_graph;
DYNALLSTAT(int, lab, lab_sz);
DYNALLSTAT(int, ptn, ptn_sz);
convert_dejavu_to_nauty(&g, &nauty_graph, &lab, &lab_sz, &ptn, &ptn_sz);

// then call nauty
statsblk stats;
DYNALLSTAT(int, orbits, orbits_sz);
DYNALLOC1(int,  orbits, orbits_sz, nauty_graph.nv, "malloc");
static DEFAULTOPTIONS_SPARSEGRAPH(options);
options.schreier = true;
options.defaultptn = false;
options.userautomproc = dejavu::preprocessor::nauty_hook;
if(nauty_graph.nv > 0) {
    sparsenauty(&nauty_graph, lab, ptn, orbits, &options, &stats, NULL);
}

// clean up
DYNFREE(lab, lab_sz);
DYNFREE(ptn, ptn_sz);
SG_FREE(nauty_graph);

// done!

Note that the nauty_hook uses the static field preprocessor::save_preprocessor to access p again, which in turn accesses p.saved_hook. If multi-threading is used in this configuration, preprocessor::save_preprocessor should be changed to thread_local. This also holds for Traces.

The convert_dejavu_to_nauty method allocates memory for the graph, lab and ptn using the respective macros of nauty. Freeing up the memory has to be handled by the user.

Example using Traces #

#include "dejavu/preprocessor.h"
#include "dejavu/tools/traces_converter.h"
#include "nauty/traces.h"

...

dejavu::static_graph g;

// graph must be parsed into g here!

// lets preprocess...
dejavu::preprocessor p;
// hook is a dejavu_hook callback function
p.reduce(&g, &hook);

// ...and then we give the graph to Traces: first, convert the graph
sparsegraph traces_graph;
DYNALLSTAT(int, lab, lab_sz);
DYNALLSTAT(int, ptn, ptn_sz);
convert_dejavu_to_traces(&g, &traces_graph, &lab, &lab_sz, &ptn, &ptn_sz);

// then call Traces
statsblk stats;
DYNALLSTAT(int, orbits, orbits_sz);
DYNALLOC1(int,  orbits, orbits_sz, traces_graph.nv, "malloc");
static DEFAULTOPTIONS_TRACES(options);
options.schreier = true;
options.defaultptn = false;
options.userautomproc = dejavu::preprocessor::traces_hook;
if(nauty_graph.nv > 0) {
    Traces(&traces_graph, lab, ptn, orbits, &options, &stats, NULL);
}

// clean up
DYNFREE(lab, lab_sz);
DYNFREE(ptn, ptn_sz);
SG_FREE(traces_graph);

// done!

The convert_dejavu_to_traces method allocates memory for the graph, lab and ptn using the respective macros of Traces. Freeing up the memory has to be handled by the user.

Example using saucy #

#include "dejavu/preprocessor.h"
#include "dejavu/tools/saucy_converter.h"
#include "dejavu/saucy.h"

...

dejavu::static_graph g;

// graph must be parsed into g here!

// lets preprocess...
dejavu::preprocessor p;
// hook is a dejavu_hook callback function
p.reduce(&g, &hook);

// ...and then we give the graph to saucy: first, convert the graph
saucy_graph _saucy_graph;
int* colors = nullptr;
convert_dejavu_to_saucy(&g, &_saucy_graph, &colors);

// then call saucy
struct saucy_stats stats;
if(g.v_size > 0) {
    struct saucy *s = saucy_alloc(_saucy_graph.n);
    saucy_search(s, &_saucy_graph, 0, colors, 
        &dejavu::preprocessor::saucy_hook, &p, &stats);
    saucy_free(s);
}

// clean up
delete[] colors;
delete[] _saucy_graph.edg;
delete[] _saucy_graph.adj;

// done!

I want to mention that I have also seen a saucy version that uses a slightly different graph format. In this version, saucy_graph contains another field colors. In order to translate to this format, we just need to additionally set _saucy_graph.colors = colors, and remove colors from the parameter list of saucy_search:

...
saucy_search(s, &_saucy_graph, 0, 
    &dejavu::preprocessor::saucy_hook, &p, &stats);
...

Again, the convert_dejavu_to_saucy method allocates memory for the graph and colors, which has to be handled by the user.