#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:26 ncohen]:
> Yoooooo !
>
> > 1. Bliss returns a list of automorphisms as bijections.
>
> Which are the automorphisms which generate the full automorphism group
of the graph ?
Yes, each time bliss discovers an automorphism it calls this function to
handle it.
>
> > 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 the sake of labels.
>
> +1 to that. It is not a very big amount of code, and one can never tell
the amount of useless computations done by the `Permutation` code anyway
`:-P`
Exactly:D
>
> > 2. There is a very erratic bug using bliss on digraphs.
> >
> > 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.
>
> But can it happen the first time you call the code, or only after
several attempts ? This looks like a memory leak problem... Unless it is a
bug in bliss `O_o`
Yes it can happen on first try as well!!
>
> Actually, reading the code a bit, I am totally scared by how you cast
Python objects like the two dictionaries to a bliss function. It expects C
arrays, and you give it a pointer to a Python dictionary ? `O_o;;;;`
No I am sure I am not doing this. The argument there is a just a void
pointer that bliss then passes on to your function.
Soo bliss takes a function pointer to YOUR function and a pointer to YOUR
data. And then it calls YOUR function passing it YOUR void pointer.
So that should be fine I suppose?
>
> Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17464#comment:27>
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.
