#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 | cad441ec9fcfa114fc481411e949557845c45ab5
Branch: | Stopgaps:
public/bliss |
Dependencies: |
#17552 |
-------------------------+-------------------------------------------------
Comment (by azi):
Replying to [comment:34 ncohen]:
> Yooooooooo !
>
> > Since this is not done for graphs it makes all of this very suspicious
but it works.
> >
> > I've also talked with the author of bliss who confirmed this is an
actually bug that he'll address in an upcoming release of bliss. In the
meantime he says the above is a valid fix.
>
> Oh, excellent news !
>
> > That said, I think it makes sense to see what is to be done to push
this branch further?
>
> First, it would be really good to have the 'spkg' ticket in
`positive_review`. Jeroen set it back to `needs_work` recently, and now
you have something else to add to it: the patch to change this line.
>
> Now, you cannot modify upstream directly (i.e. the .tar.bz2 file) so you
must use the 'patch' mechanism that is already being used in
build/pkgs/sympy (for example). Look at the sympy/spkg-install file and
the patches/ folder. The corresponding doc is there:
>
> http://www.sagemath.org/doc/developer/packaging.html#patching-sources
>
> > I have added some small documentation and would like to hear any kind
of input that you may have.
I think it would be good to mention how the patch is created since there
may be different parameters to diff and also since we like to just copy
paste stuff and not think too much.
>
> Well, it seems that you still have some notes to yourself in the branch.
Those that you cannot solve right now should probably appear in the
documentation of the function to which they apply, and not at module
level. (note: you can write a docstring in C functions. It will not appear
as html do of course, but that's the right place to write the function's
doc.)
>
> In particular you have some formatting to do (a)length of lines b) the
first line of doc is a one-line sentence describing the function.
>
> You can also add the mechanism that makes
GenericGraph.automorphism_group use bliss if available by default (set
algorithm=None by default, and {{{if algorithm is None and
is_package_installed("bliss")}}} then ...) if you like, otherwise I will
do it at some point.
>
> There is also this in the code
> {{{
> + if algorithm == "bliss":
> + print 'yes'
> + return
> }}}
Yes, I'll make bliss the default the above was just a test. Though I we
should really test this thoroughly since it can get messy if we leave a
bug inside.. I spotted one before. Considering
{{{
return PermutationGroup(gens)
}}}
everything works well most of the time (since in all tested graphs every
vertex appears in some cycle of the generator). But if you do not specify
the domain you may get automorphism groups not acting on all the required
points...
>
> But really that's just cleaning. Short of that I do not think that there
is anything important missing.
>
> Oh, by the way: I do not think that you should really carry those
vert2int or int2vert around. You could just say somewhere that the integer
names of the vertices are those obtained by the ordering of `g.vertices()`
>
> Then defining the two dictionaries is rather easy
> {{{
> int2verts = g.vertices()
> vert2int = {v:i for i,v in enumerate(int2verts)}
> }}}
Yes that's right. What made me choose the present version is the fact that
the second line is already a for loop over the vertices and from how I
understand g.vertices() that always involves a loop as well (at least to
get the labels of the graph, grrr)?
>
> Well, that's all. Only "code administration" `^^;`
Thanks.
>
> Nathann
Jernej
--
Ticket URL: <http://trac.sagemath.org/ticket/17464#comment:35>
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.
