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)

##
Advertising

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
http://pallini.di.uniroma1.it/Guide.html
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.
Dima
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.