4.2. graph-canon

The graph_canon program performs canonicalization of (a permutation of) a given input graph. It contains many different configurations of the graph canonicalization algorithm that can be selected through switches. The program additional has two distinct modes:

--mode <mode>

  • test (default): All canonicalization results are compared for equality. Allows for outputting additional information from the algorithm execution.

  • benchmark: Minimal overhead mode, with no result checks and limited information gathering.

The program really consists of many executables (all on the form graph-canon-*), each with different algorithm configurations. The main executable, graph-canon, is a wrapper script that invokes the correct executable depending on the given arguments. This wrapper script is a Python program, which supports argcomplete.

4.2.1. General Options

-h, --help

Print help message. Note, part of the message changes depending on which --mode has been given.

--id <string>

The id to print in the beginning of every output line. It defaults to either ‘default’, ‘stdin’, or the filename given with -f.

--postId <string>

The id to print in the end of every data output line. It defaults to the empty string.

--postHeader <string>

The id to print in the end of every header output line. It defaults to the empty string.

-s <seed>, --seed <seed>

Seed for random number generator. The default value is static_cast<std::size_t>(std::time(0)).

-p <num>, --permutations <num>

Number of random permutations to try. For test mode an additional run is performed in the beginning with the original vertex order. Default is 5.

4.2.2. Graph Loading Options

-f <filename>, --dimacs <filname>

File with graph in DIMACS format (see read_dimacs_graph()). Use ‘-‘ to read from stdin. If not used, a default graph is used.

--vertex-labels <mode>

  • none (default): vertices are unlabelled.

  • uniform: vertices are labelled with a uniformly random number in the range 0 to --vertex-label-max (excluding).

--vertex-label-max

See --vertex-labels. Default is 5.

--edge-labels <mode>

  • none (default): edges are unlabelled.

  • uniform: edges are labelled with a uniformly random number in the range 0 to --edge-label-max (excluding).

--edge-label-max

See --edge-labels. Default is 5.

-d, --directed

Interpret the graph as a directed graph.

--parallel-edges

Allow parallel edges, otherwise they are ignored.

--loops

Allow loop edges, otherwise they are ignored.

4.2.3. Algorithm Configuration Options

--ftarget-cell <alg>

The algorithm for selecting target cells:

  • f: select the first non-trivial cell.

  • fl: select the first of the largest cell.

  • flm (default): select the first of the largest cell of those with maximum non-uniformly joined degree.

--ftree-traversal <alg>

The algorithm for exploring the search tree:

  • dfs: depth-first traversal.

  • bfs-exp (default): breadth-first traversal with 1 experimental path per tree vertex.

  • bfs-exp-m: breadth-first traversal with 1 experimental path per tree vertex, limited by memory specified by -m.

-m <MB>, --memory <MB>

Memory limit (in MB) before the tree traversal bfs-exp-m switches to DFS mode. Default is 4 GB.

--frefine <alg>

The degree-based refinement function to use:

  • WL-1 (default): Weisfeiler-Leman algorithm, with 1 dimension.

--faut-pruner <alg>

The automorphism pruning algorithm to use:

  • none: Do not prune using automorphisms.

  • basic (default): Prune using the subset of generators that fix the necessary elements.

  • schreier: Prune using fully calculated stabilizers.

--faut-implicit, --fno-aut-implicit

Enable or disable the implicit automorphisms visitor. Enabled as default.

--fpartial-leaf, --fno-partial-leaf

Enable or disable the partial leaf certificate visitor. Enabled as default.

--ftrace, --fno-trace

Enable or disable the trace visitor. Enabled as default.

--fquotient, --fno-quotient

Enable or disable the quotient graph visitor. Enabled as default.

--fdegree-1, --fno-degree-1

Enable or disable the visitor for fast handling of degree-1 vertices. Enabled as default.

4.2.4. Program Execution Options

--memcheck

Run the program through Valgrind.

--debug

Run the program through GDB (or if --memcheck then with vgdb in Valgrind).

--profile

Run the program through Valgrind with callgrind.

4.2.5. Options Specific for Benchmark Mode

The program perform several rounds of canonicalization, all on randomly permuted versions of the input graph.

-t <s>, --time <s>

Time limit (in seconds). This is only checked after each round finishes.

4.2.6. Options Specific for Test Mode

The program perform several rounds of canonicalization. First on the input graph, and then on randomly permuted versions of that graph. As default the options are applied to the first round, on the input graph.

--last

Apply debug and output options to the last permuted graph instead of the input graph.

--graph-dot <filename>

Print graph in dot format, with the original and canonical indices to this file.

--tree-dot <filename>

Print the search tree from a canonicalization run.

--json <filename>

Print log data as JSON to a file, suitable for the GraphCanon Visualizer. The output is not affected by the --g* options.

-g, --gall

Print all debug information.

--gtree

Print debug information related to tree traversal.

--gcanon

Print debug information related to selecting a canonical leaf in the tree.

--gaut

Print debug information related to automorphism discovery.

--grefine

Print debug information related to the refinement procedure.

--gcompressed

Print debug information in a shorter format.

--stats

Print statistics from one canonicalization run.