[Nauty] canonical label for directed graphs

[Brendan McKay]

* Edward N Turner <ent03r at ecs.soton.ac.uk> [050803 23:06]:
> Great - thanks for that.
> 
> One more question that will help my understanding - is the set of
> discrete partitions created when generating the search tree for a given
> graph unique? And so, the min/max in this ordering (however we define it
> e.g., half/full adj matrix) can be taken as the canonical label?
 
That is how nauty finds the canonical label. The difficult part of
defining the canonical labelling completely is to define exactly
which discrete partitions are generated. It is defined in a way that
is tuned for fast computation, and not tuned for easy explanation in
human language.

Brendan.