[Nauty] canonical label for directed graphs
Edward N Turner
ent03r at ecs.soton.ac.uk
Wed Aug 3 21:46:44 EST 2005
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?
More information about the Nauty