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
To unsubscribe from this group and stop receiving emails from it, send an email
To post to this group, send email to email@example.com.
Visit this group at https://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.