[Nauty] canonical label for directed graphs

Brendan McKay bdm at cs.anu.edu.au
Wed Aug 3 22:38:27 EST 2005

* Gordon Royle <gordon at csse.uwa.edu.au> [050803 22:24]:
> nauty already computes canonical labellings for directed graphs....   
> there is no need to modify the algorithm.
> However the default settings for the "options" structure is to have  
> options.digraph set to FALSE - presumably because some speed can be  
> gained if the algorithm can rely on the input being undirected  
> without actually confirming that edge j-i is present when it notices  
> edge i-j.
> So, just set options.digraph = TRUE before your call to nauty, and it  
> will treat it as a directed graph
If you are calling nauty from your own problem, I also recommend
   options.mininvarlevel = 1;
   options.maxinvarlevel = 99;      /* or something */
   options.invarproc = adjacencies;
For long jobs you might want to test whether this helps or hurts.
The values of these parameters can change the canonical labelling
so be consistent.


More information about the Nauty mailing list