#17464: Computing the automorphism group of a graph
-------------------------+-------------------------------------------------
Reporter: azi | Owner:
Type: | Status: needs_work
enhancement | Milestone: sage-6.5
Priority: major | Resolution:
Component: graph | Merged in:
theory | Reviewers:
Keywords: | Work issues:
Authors: | Commit:
Report Upstream: N/A | 3c37cb81e7bfbc58f953035054dd4c30d0750880
Branch: | Stopgaps:
public/bliss |
Dependencies: |
#17552 |
-------------------------+-------------------------------------------------
Comment (by azi):
Replying to [comment:24 ncohen]:
> Yo !
>
> > Before we change Graph.canonical_form,is_isomorphic,automorphism_group
I suggest that we address >the FIXME stuff in the bliss.pyx code.
>
> I am already writing some code at the moment and when I will be done I
must go back to my blackboard. Is there is some specific question that you
have for this patch please ask it, but if I begin to look at bliss' API,
understand your code and answer the questions that you wrote inside it
will probably take me as much time as writing the interface from scratch
`:-P`
Okay.
Sooo
1. Bliss returns a list of automorphisms as bijections. There is a
function inside the code that then in one pass creates the respective
cycle notation for the permutation while also applying the labelling of
the graph. We have Permutation.to_cycle() that does the job but only on
integer valued bijections. As is I'd like to leave this function in
bliss.pyx and then perhaps once labelled permutations are supported by
to_cycle(), revert to that. The main reason being that I am using Sage on
graphs with 700k vertices and its a pain to have to iterate over and over
for sake of labels.
2. There is a very erratic bug using bliss on digraphs.
{{{
sage: D = digraphs.Kautz(10,2,1)
sage: from sage.graphs.bliss import *
sage: D.automorphism_group().is_isomorphic(automorphism_group(D))
True
sage: D.automorphism_group().is_isomorphic(automorphism_group(D))
Bliss fatal error: Internal error - unknown splitting heuristics
Aborting!
}}}
I have no clue why this is happening. Do you have any intuition as to
where to look for the issue? The code for Graph/Digraph that raises this
exception is identical yet this only happens sporadically with digraphs.
As far as technical questions go, this are the main things I need some
input about.
Best,
Jernej
> > Another "issue" that is not in the code is what are we to do with the
heuristics. There are a few heuristics for bliss and we can make them as
an available choice for Sage or just go ahead with the default one.
>
> The current branch contains already many commits, and there are many
things to pay attention to (we really don't want this code to return wrong
results because of a typo) so it will probably be best to keep this branch
to a minimum.
>
> That does not mean that anything will have to be delayed: this branch
will be sooner in `positive_review`, and then you can expose those
features in another ticket.
>
> Good luck ! `:-P`
>
> Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17464#comment:25>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
