[Nauty] canonical label for directed graphs

Edward N Turner ent03r at ecs.soton.ac.uk
Wed Aug 3 21:46:44 EST 2005


Dear all,
Nauty currently allows us to find canonical labels for undirected graphs
- would it be possible to modify the algorithm it uses to obtain
canonical labels for directed graphs?

The adjacency matrices for undirected graphs are symmetric about the
main diagonal - and so we only need to consider one half for the
ordering of matrices. However, the adjacency matrices for directed
graphs won't be symmetric in general - so my question is; would it
suffice to consider the whole matrix for the ordering, to find a
canonical label for a directed graph?

Best,
Edward T.





More information about the Nauty mailing list