[Nauty] Canonicalizing directed graphs.

[Brendan McKay]

* Alexander Engström <f96-aen at nada.kth.se> [040301 00:58]:
> 
> Under what conditions will the canonical graph of a directed graph be
> lower triangular?

There aren't any guarantees of this at all.  If you need a 
canonical form for an acyclic directed graph you will need
to add an extra relabelling stage after applying nauty.

Incidentally, acyclic directed graphs don't much like the
default parameters of nauty.  For better average efficiency,
use the invariant "adjacencies".

In dreadnaut:   k=1 10 *=13

In C:
    options.invarproc = adjacencies;
    options.mininvarlevel = 1;
    options.maxinvarlevel = 10;
  (and include nautinv.c in the program).

The value "10" is arbitrary, you could try adjusting it for best
behaviour in your application.  However note that the canonical
labelling may depend on the value.

Brendan.