id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
24924 Making the bliss canonical form available for edge labelled graphs stumpc5 "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." enhancement closed major sage-8.3 graph theory fixed bliss, graph automorphism, canonical form SimonKing dimpase gh-dimpase etn40ff Christian Stump Dima Pasechnik N/A 0830efc90604f7d4b432e013b9242b24e618c762 0830efc90604f7d4b432e013b9242b24e618c762 #20382