Traces for digraphs with weighted arcs

The binary code available here has been produced for a Macbook Pro with 3.1 GHz Intel i7 processor (16GB of RAM), using the LLVM compiler (version 9.0.0) for running in a single thread. We recall that Traces always computes the order and generators of the automorphism group of the input graph. At the user's request, it computes the canonical form of the graph, too.

Description

The paper which describes the algorithm is this (submitted to SEA18).

Instructions

Download WTraces here.
Usage: ./WTraces -[cCpF#] filename.dre
Options:
-c compute the canonical labelling of the input graph;
-C as above, and then print the canonical graph;
-p assign weights to a simple graph (see below) and then run;
-F# individualize vertex # and then run according to the previous options.

Assigning weights

Given a graph G, a weighted version Gw of G can be built using the option -p, as follows: we consider the initial refined partition of G, say (W1,…,Wm), and to each arc (u,v) of G we assign the weight k if v ∈ Wk. This enables to force the program to consider the input as a weighted digraph. Note that the graph Gw has the same automorphism group of G.

Graph format

n=11 $=1 g
1 : 2 w4 8 w0 11;
2 : 1 w5 3 w3 9;
3 : w5 2 4 w3 9;
4 : 3 w4 5 w0 10;
5 : w4 4 6 w0 10;
6 : 5 w5 7 w3 9;
7 : w5 6 8 w3 9;
8 : w4 1 7 w0 11;
9 : 2 w2 3 6 w2 7 10 11;
10 : 4 5 w0 9;
11 : 1 8 w0 9;

The arrow from vertex u to v with label a,b indicates that the weight of the arc (u,v) is a and the weight of (v,u) is b

Disclaimer

The software is being currently tested. Please report any problem to piperno di uniroma1 it.