[Nauty-list] Digraphs
Brendan McKay
bdm at cs.anu.edu.au
Mon Aug 1 08:50:19 EST 2011
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
More information about the Nauty
mailing list