This is a discussion ticket for improving the bliss canonical form input, based on https://groups.google.com/d/topic/sage-support/oZ7Uu5jTR9k/discussion.

Christian's aim: make the canonical form of a graph given by an integer matrix much faster.

This basic idea is to provide an alternative version of sage.graphs.bliss.canonical_form using a list of labelled edges as input rather than a graph. Maybe

def canonical_form_list(Vnr, edges, partition)

where we assume that (i,j,color) in edges has the property 0 <= i,j < Vnr and colors 0 <= color < k where the color 0 means "uncolored" and is assumed to be the most common color.

Since this is an internal speed-critial functionality, Christian believes that it would then be the user's responsibility to turn any input format of graph, if needed, into this format.

As Dima pointed out, we can turn this edge labelled graph into an unlabelled graph with O(Vnr log k) vertices as described in Sect 14 in http://pallini.di.uniroma1.it/Guide.html.

For now, this is only for discussion design and code snippets.

Depends on #20382

CC: @simon-king-jena @dimpase @dimpase @Etn40ff

Component: graph theory

Keywords: bliss, graph automorphism, canonical form

Author: Christian Stump

Branch/Commit: 0830efc

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/24924