Brendan McKay's publications. The nauty Traces page. Brendan McKay and Adolfo Piperno Please visit the new nauty Traces page at for much more than is here. Summary nauty and Traces are programs for computing automorphism groups of graphs and digraphs. They can also produce a canonical labelling. nauty and Traces are written in a portable subset of C, and run on a considerable number of different systems. There is a small suite of programs called gtools included in the nauty package. For example, geng can generate non-isomorphic graphs very quickly. Documentation A complete manual is included in the package. The original design of nauty is in B. The original design of Traces is in A. The current algorithms behind nauty and Traces are described in the paper B. How to get it If you agree to the restrictions listed below, you may fetch version 2.5 of nauty , and version 2.0 of Traces , as a gzipped tar file (720223 bytes).
See the file changes24-25.txt for a summary of recent changes. Nauty mailing list Restrictions. Traces – Automorphism Group. When Traces is only looking for the automorphism group, and not for a canonical labelling, it employs a strategy which is sometimes much faster than the basic one. Suppose that while generating the nodes on some level L, it notices (during experimental path generation) that one of them, say ν, has a child which is discrete. At this point, Traces determines and keeps all the discrete children of ν (modulo the usual automorphism pruning).
Now, for all nodes ν' on level L, a single discrete child is found, if any, and an automorphism is discovered if it is equivalent to any child of ν. The figure shows (left) the whole tree up to level L+1, where a node labelled by X represents a discrete partition with certificate X, while an unlabelled (red) node stands for a non-discrete partition. The tree at the center of this figure shows the part of the tree which is traversed by Traces during the search for a canonical labelling.
TCS - Software - bliss. TCS / Software / bliss Authors: Tommi Junttila and Petteri Kaski bliss is an open source tool for computing automorphism groups and canonical forms of graphs. It has both a command line user interface as well as C++ and C programming language APIs. Graphs, Isomorphism, and Canonical Forms Below we briefly formally describe what bliss does. A colored graph is a triple G=(V,E,c) where V={1,2,... and Let γ:V→V be a permutation of V.
Gγ = (V, {{vγ,wγ} | {v,w}∈E}, cγ), where cγ:V→N is defined for all v∈V by cγ(vγ)=c(v). Two colored graphs, G1=(V,E1,c1) and G2=(V,E2,c2), are isomorphic if there exists a permutation γ:V→V such that G1γ=G2. An automorphism of a colored graph is an isomorphism of the colored graph onto itself. Aut(G1)={⟨1→1,2→2,3→3,4→4⟩,⟨1→1,2→2,3→4,4→3⟩} in Figure 1. A function ρ from colored graphs to colored graphs is a canonical representative map if the following two conditions hold: Directed Graphs The software tool bliss can also handle directed graphs. A Note of Caution. Saucy3. Saucy - Summer 2004 Saucy2 - Summer 2008 Saucy3 - Spring 2012 Quick Links Summary Many computational tools have recently begun to benefit from the use of the symmetry inherent in the tasks they solve, and use general-purpose graph symmetry tools to uncover this symmetry. Common applications include organic chemistry, constraint solvers, logistics, optimization, bio-informatics, and finite group theory.
However, older symmetry-finding tools often suffer quadratic runtime (or worse!) In the number of symmetries explicitly returned and are therefore of limited use on very large, sparse, symmetric graphs. Our implementation has been stable and reliable for many years. Saucy currently does not deal with approximate symmetries and with spatial data. June 2013: in addition to the current saucy implementation, we have developed an algorithm to find symmetries of Boolean functions represented by (sizable) circuits. Source Code The latest version of saucy is available upon request. Benchmarks H. H.