SAUCY

NAME

SYNOPSIS

saucy [ -sqzg ] [ -p count ] [ -t secs ] file

DESCRIPTION

saucy reads a graph from file in its native format, or if -g is specified, in the GAP format used by Shatter. Generators implicitly representing the automorphism group of the graph are computed and sent to standard output.  

OPTIONS

-s

Output computation statistics to standard error.

-q

Quiet mode: do not output the generators discovered during the search. This is primarily useful in conjunction with -s.

-z

Stop the search once the first discrete partition is found. Again, primarily useful in debugging refinement in conjunction with -s.

-g

Use GAP as the input and output format, for use with Shatter.

-t secs

Force saucy to end computation after at least secs seconds. saucy may not terminate immediately, depending on the current state of the computation. In particular, it will not terminate in the middle of outputting an automorphism.

-p count

Cache count automorphisms for efficient backtracking. The default count is 60 automorphisms. This cache is used only during backtracking, and thus increasing its size will not improve performance on many graphs. If the cache is needed, a larger cache can improve the effectiveness of the backtracking, but at the expense of time and memory overhead.

INPUT

saucy uses a very simplistic input format for graphs. Note that the brackets below are not part of the syntax, and that the vertices of a graph are numbered from 0.

{vertices} {edges} {cells} {starts...} {v1 v2} {...}

vertices

Total number of vertices in the graph.

edges

Total number of edges in the graph.

cells

Number of cells in the initial coloring. saucy operates on ordered partitions, or colorings, of the set of vertices of the graph. The cells attribute specifies the number of colors present in the initial coloring of the graph. If the graph is initially uncolored, then all vertices are indistinguished and cells should be 1.

starts

Locations of the starts of cells in the initial coloring. saucy reads cells-1 starts, each identifying the beginning of the new cell in the partition. The first cell starts from zero, and is omitted.

v1 v2

Add an edge between these two vertices. The remainder of the file consists of edges pairs of vertices. v1 and v2 are not allowed to be equal.

NOTES

saucy assumes that its input file is well-formed, and will not behave gracefully if it is not.  

AUTHOR

This program is written and maintained by Paul T. Darga <pdarga@umich.edu> with help from Mark Liffiton <liffiton@umich.edu>. The underlying mathematics, search tree, and basic refinement algorithms are all due to Brendan D. McKay and his nauty package. The algorithms are published in McKay, B. D., "Practical Graph Isomorphism", Congressus Numerantium 30 (1981), pp.45-87.

saucy was originally inspired by the work of DoRon B. Motter on his AutoGraph project.

This work was funded in part by NSF ITR grant 0205288.

Index

NAME

SYNOPSIS

DESCRIPTION

OPTIONS

INPUT

NOTES

AUTHOR