[Nauty] lexicografic ordered canonical form

[Brendan McKay]

* Joost Winne <Joost.Winne at UGent.be> [030806 18:08]:
> Hi,
> 
> I have the following question:
> 
> Given a graph G, the canonical form produced by nauty is CANONG.
> This form CANONG is not necessarely lexicograficly ordered
> (lexicograficly ordered means that rows and columns are ordered
> when seen as a bitstring).
> There can be several ways to lexicografic order the canonical form CANONG,
> since 2 lexicograficly ordered graphs can be isomorphic (if this wasn't
> true we wouldn't need nauty in the first place).
> Is their a way to lexicograficly order CANONG into CANONG_LEX in such a
> way that it is guaranteed that CANONG_LEX is lex. smaller than all other
> lex. ordered isomorphics of CANONG (G).
> Otherwise put, I would like a canonical form which is also the
> lexicografic smallest.

This is an excellent question as it would be very convenient for many
orderly generation algorithms if the nauty canonical form was the
lexicographically smallest form.  However, nauty uses a completely
different notion of canonicity (designed to be efficient to compute
rather than easy to define) and there is no simple way of changing that.

An alternative to minimal forms that could also be used in orderly
generation would be a canonical form such that removing the last vertex
leaves the canonical form of the smaller graph.  That sounds more likely
to be computable but still there are difficulties that are not easy
to overcome.

In the case of generating families of objects, often the orderly method
that relies on minimal forms can be replaced by another method that is
well suited to nauty.  A general description is in my paper here:
    http://cs.anu.edu.au/~bdm/papers/orderly.ps.gz
Perhaps that is not the easiest source to learn the method.  If you
indicate that this is the subject you are interested in and what type of
thing you want to generate, we can probably find some references which
give more application-specific explanations.

Brendan.