Ultimately, the classical canonical form/isomorphism implementations run on 
(di)graphs represented by 0-1 matrices, often
with bit entries. So that's how bliss_digraph is represented too.
Constructing it directly might be beneficial, especially if you have a 
problem of doing this on many small matrices
(20x20 would still be quite small; isomorphism complexity usually starts to 
kick in with, say, 100x100 matrices)

Anyhow, the main inefficiency in your approach is coming from constructing 
unnecessarily big graphs.
In fact, to encode an edge-coloured (say, k colours) n-vertex graph as an 
equivalent vertex-coloured graph
you only need O(n log k) vertices in the new graph. See Sect 14 in 
on how this can be done.

If you implemented this in Sage, it would be a great contribution! 

Also, I am not sure whether bliss is faster than nauty (nauty also is a 
Sage standard package, but lacks a cython interface)
But this is another story.


On Tuesday, March 6, 2018 at 4:18:07 PM UTC, Christian Stump wrote:
> Hi Simon,
> Thanks for trying! I was actually hoping for a way to completely avoid 
> creating this sage DiGraph. But either to get the matrix directly into the 
> algorithm (which currently seems impossible), or at least to directly 
> construct some internal graph data structure.
> Looking at the code of sage.graphs.bliss.canonical_form, you see that the 
> input digraph is turned into a bliss_digraph (whatever that is). So I 
> believe that there is, in principle, a way to bypass the DiGraph creation...
> Thanks again, Christian

You received this message because you are subscribed to the Google Groups 
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

Reply via email to