Opened 4 years ago

Last modified 3 years ago

#24924 closed enhancement

Ḿaking the bliss canonical form available for edge labelled graphs — at Initial Version

Reported by: stumpc5 Owned by:
Priority: major Milestone: sage-8.3
Component: graph theory Keywords: bliss, graph automorphism, canonical form
Cc: SimonKing, dimpase, gh-dimpase, ​etn40ff Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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 vertices 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.

Change History (0)

Note: See TracTickets for help on using tickets.