Dear Dima, 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. >
Thanks for this info clarifying that it seems impossible to feed the algorithm any other kind of integer matrix. Anyhow, the main inefficiency in your approach is coming from constructing > unnecessarily big graphs. > Also thanks for this reference, for the general problem this is certainly the correct approach. In my example cases though (as mentioned above), I have only very few edge labels (usually only two) so I doubt this improvement would change the overall performance. If you implemented this in Sage, it would be a great contribution! > I agree that this would be very worth having! But my cython skills are too weak to do this in the appropriate speed context. One question here: am I correct that the best we can currently hope for is to 1. feed the algorithm a list of labelled edges 2. turn this list of labelled edges into a list of unlabelled edges representing the edge-labelled graph as in Section 13 3. feed this to either the bliss or the nauty algorithm 4. get back an unlabelled graph 5. turn this back into an edge labelled graph > Also, I am not sure whether bliss is faster than nauty (nauty also is a > Sage standard package, but lacks a cython interface) > The only reason I use bliss over nauty is that it can return only a list of edges rather than creating the output DiGraph. And in the tests I did, 1/3 of the time was spend on constructing the canonical form and 2/3 were used to turn these output edges into a DiGraph (this compares bliss with and without constructing the output graph, nauty was as fast as bliss with output graph construction). Cheers, 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.
