TRACES 0.01

 

TRACES is a canonical labeling tool for graphs. It is based on the algorithm described in

http://arxiv.org/abs/0804.4881. A new version of the paper is here.


A preliminary version of TRACES can be downloaded here: TracesApr08.zip.


HOW IT WORKS

TRACES is built as an additional command of Brendan McKay’s nauty 2.2; the nauty page is http://cs.anu.edu.au/~bdm/nauty/.

SIZE LIMITS: At present, graphs with more than 12000 vertices cannot be considered.


OUTPUT DESCRIPTION (with comments)



Traces version Apr, 2008 (Canonical). Dreadnaut version 2.2 (64 bits).

> <G/Circ52    (1)

> :            (2)

Initial partition: 1 cell

[ 1:52 ]

Refined partition: 1 cell

[ 1:52 ]

Multi-refined partition: 1 cell

[ 1:52 ]

ITERATION 0 (1 cell); next position: 0; target size: 52; group time/time = 0.00/0.00 seconds.

┌───────────────────────┐

|                     0 | (3)

└───────────────────────┤ next position: 2; cells: 4; multi-refs: 2

    1     2     1)    1 |  28  ▯▯  size: 2‧3; 18 orbits.  (4)

    2     4     2)    2 |  16  ▯▯▯  size: 2³‧3²; 8 orbits.                   

    3     6     3)    3 |   6

    4     8     4)    6 |   3

    5    10     5)   15 |   5

    6    12     6)   21 |   2  ▯▯▯▮  size: 2⁴‧3²; 4 orbits. (4)

✓━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

(Sub)group size: 2⁴‧3²; 4 gens; 4 orbits.

ITERATION 1 (4 cells); next position: 2; target size: 25; group time/time = 0.00/0.00 seconds.

┌───────────────────────────┐

|                     0   2 |

└───────────────────────────┤ discrete partition; multi-refs: 14

    7    14     1)    1  28 | ... see above

----------------------------| (5)

    8    15     1)    1  29 |

----------------------------|

    9    18     1)    1  35 |  

----------------------------|

   10    21     1)    1  47 |

----------------------------|

   11    30     1)    6   9 | (6)

────────────────────────────────────────────────────────────────

Graph: G/Circ52.dre; nodes: 52; edges = 650

Group size: 2⁴‧3²; 4 gens; 4 orbits

Cpu time = 0.00 seconds; 11 attempts (24 aborted); 35 Mref steps; GroupTime = 0.00 seconds

────────────────────────────────────────────────────────────────

Orbits:  1 4 5 12:14 21:27 30 31 38:40 47:52

        2 28

        3 29

        6:11 15:20 32:37 41:46


(1) the input graph (Circ52, located into the folder G);

(2) type : to execute Traces;

  1. (3)the position(s) of individualized vertices;

  2. (4)an attempt is a sequence of individualizations which produce a discrete partition; in this example, the first attempt is the one which individualizes the vertex 1 and then 28; an empty rectangle (▯) indicates that an automorphism has been found fixing the vertices which are considered during the attempt; a white rectangle (▮) indicates an automorphism between vertices of different attempts;

  3. (5)the dotted line indicates here that the individualization of vertex 1 and then 29 is better (wrt some invariant criterion) than the individualization of 1 and then 28; therefore, the previous attempt is discarded;

  4. (6)the integers 11    30     1 indicate the amount of completely computed attempts, the total amount of attempts (including those aborted by invariant criteria) and the amount of attempts to be expanded at the next iteration, respectively.