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 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.
