[Nauty-list] Digraphs

Mathieu Dutour Mathieu.Dutour at ens.fr
Sun Jul 31 23:40:43 EST 2011

Dear nauty world,

I remember some time ago in Canada that Brendan McKay told me
that nauty was slow for digraphs and that instead I should use
vertex colors. I did that and it works well.

But recently, I have seen some problems whre digraphs are needed
a priori, i.e. there is no obvious sink/source to decompose it
by vertex colors.

Is nauty still slow for digraphs? Is there some reduction technique
to map digraphs as graphs? Since I am at it, the digraph edges are 
actually weighted but I can use the reduction technique to 
n log2(k) larger digraph.


More information about the Nauty mailing list