[Nauty-list] Digraphs

[Brendan McKay]

If the digraphs are strongly connected it should be ok anyway.

If not, you can use the invariant "adjacencies".  In dreadnaut:
    *=13 k=0 99

In a program:
    #include <nautinv.h>

    options.digraph = TRUE;
    options.invarproc = adjacencies;
    options.mininvarlevel = 0;
    options.maxinvarlevel = 99;
and link with nautinv.o, or if you are using the sparse data
structures the invariant is called "adjacencies_sg".

This will slightly slow down easy cases but prevent the worst
behaviour.

Brendan.


* Mathieu Dutour <Mathieu.Dutour at ens.fr> [110731 23:40]:
> 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.
> 
>   Mathieu
> 
> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list