# [sage-support] Re: Graph canonical form directly on matrices

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