On Wednesday, March 7, 2018 at 8:44:52 AM UTC, Christian Stump wrote: > > 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. >
It is perfectly possible to implement canonical form/isomorphism of edge-labelled (di)graphs in the same vein as un-labelled ones. (I did it as a part of a project in my undergraduate years, the code (in Fortran IV :-)) is unfortunately lost. It should not be too hard to re-do.) It's just I'm not aware of such implementations available anywhere. > > 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. > OK, in this case indeed it won't be noticeable. > > 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 > the only improvement I could see in your scheme is that bliss/nauty can return a permutation you need to apply to your graph to make it canonical, and it would be probably more efficient to apply it (after the dropping the extra vertices you created) directly to your original labelled (di)graph. Still faster would be to make a Sage graph backend compatible with bliss or nauty API in the sense that they could operate directly on the graph you created, but this is much more work, naturally. > > >> 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.
