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 

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 post to this group, send email to
Visit this group at
For more options, visit

Reply via email to