#17464: Computing the automorphism group of a graph
----------------------------+----------------------------
Reporter: azi | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.5
Component: graph theory | Keywords:
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
----------------------------+----------------------------
Hello!
I have a suggestion for a big improvement for the Graph Theoretical module
of Sage. Right now I am a not in the proper mood to do it myself so I am
leaving this here in case anyone is willing to do it or as a TODO note for
a later time.
Consider the graph on ~10k vertices located in the file
https://www.dropbox.com/s/pbtk2965ti71u9n/graph.txt.gz?dl=0 where each
line contains an edge pair.
Using the standard way in Sage (read graph call automorphism_group() )
takes a few ''' hours''' (I'll tell the exact time when it actually
finishes) to compute and makes a ''' 30GB''' memory footprint.
The same thing can be done using bliss
http://www.tcs.tkk.fi/Software/bliss/index.html with no actual memory
footprint in '''20 seconds.'''
So right now its much cheaper for me to just write the graph into DIMACS
format call bliss and parse its output.
I guess the same kind of performance can be obtained using nauty so I
suppose there is something OFF with the current implementation of the
automorphism group method. IIRC it is written in Python?
Hopefully we can make this into a productive patch.
--
Ticket URL: <http://trac.sagemath.org/ticket/17464>
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.
