Opened 4 years ago
Last modified 3 years ago
#24924 closed enhancement
Making the bliss canonical form available for edge labelled graphs — at Version 2
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: |
Description (last modified by )
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.
Change History (2)
comment:1 Changed 4 years ago by
- Summary changed from Ḿaking the bliss canonical form available for edge labelled graphs to Making the bliss canonical form available for edge labelled graphs
comment:2 Changed 4 years ago by
- Description modified (diff)