Force Gap to forget graph automorphism groups

asked 2013-07-26 09:43:43 +0100

MT
1 ●1 ●1 ●1

I'm interested in computing and storing a huge number of graphs. For each graph I compute, I temporarily need to compute its automorphism group -- but I don't need to, and don't want to, remember that automorphism group. It looks like sage deals with graphs on its own but calls Gap to deal with automorphism groups.

The problem is that Gap, not sage, exceeds it permitted memory. Why? Here is a (silly) example of what I'm talking about: running

mylist=[];
count = 1;
while True:
    g = graphs.RandomGNP(6, .5);
    aut = g.automorphism_group();
    mylist.append(g);
    if aut.order() > 1:
        print "Graph number %s has nontrivial automorphisms!"%(count);
    count += 1;

gives me after some hours

RuntimeError: Gap produced error output
Error, exceeded the permitted memory (`-o' command line option)

How can I force sage/gap to forget the automorphism groups attached to the graphs (but remember the graphs)? Ideally Gap should only need to store one automorphism group at a time.

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2013-07-29 10:57:49 +0100

Volker Braun
3301 ●11 ●30 ●75

Any live Sage object will keep a reference to a GAP object alive. Also, Sage objects in cyclic references will never have their bound GAP objects cleared (though that works in LibGAP). Use gap.NamesUserGVars() to list all global GAP variables (the ones starting with $sage are associated to Sage objects).

edit flag offensive delete link

Comments

Thanks -- gap.NamesUserGVars() is very useful. Can you clarify what is meant by "Sage objects in cyclic references will never have their bound GAP objects cleared?" is there an instance of cyclic referencing in the sample code? It's strange: if I delete the "if" statement that computes the order of the group aut, then adding the line del(aut) at the end of the loop solves the memory leak. But if I compute the order of the group, or compute anything else about it, then no amount of deleting gets rid of it (not even saving its properties like order in separate variables and deleting them.)

MT ( 2013-07-29 22:48:37 +0100 )edit

Volker: by "Sage objects in cyclic references", do you mean Sage objects referenced in a loop? What about in a test clause? MT: have you tried g.automorphism_group(order=True,return_group=False)

slelievre ( 2013-07-29 23:26:12 +0100 )edit

thanks much, I didn't know about the option to return only the order. I should clarify that sadly, in my actual code, I *do* need to look at all of the automorphisms (the sample code was oversimplified).

MT ( 2013-07-30 00:07:40 +0100 )edit

If there is caching somewhere in the code for automorphism_group() and order() then its easy to get cyclic references. I haven't checked myself, though. You can try to use libgap, e.g. libgap(g.automorphism_group()).Order()

Volker Braun ( 2013-07-30 12:39:54 +0100 )edit

add a comment

answered 2013-07-26 12:23:56 +0100

slelievre
17704 ●22 ●160 ●350 http://carva.org/samue...

updated 2013-07-29 23:32:00 +0100

About your code. (1) Lists are indexed from 0, so initializing count at 0 would let you access graph number n by typing mylist[n]. (2) No need for semicolons. (3) You can compute the order of the automorphism group without giving it a name. Maybe that's what's making GAP store them.

Below is a rewrite of your code taking these comments into account.

mylist=[]
count = 0
while True:
    g = graphs.RandomGNP(6, .5)
    mylist.append(g)
    if g.automorphism_group().order() > 1:
        print "Graph number %s has nontrivial automorphisms!"%(count)
    count += 1

If you still experience memory problems, the GAP manual has a section about memory information, telling you how to check how much memory is used.

There is also an FAQ entry telling you how to force garbage collection in GAP.

It says: 2. Garbage collection. The GAP memory manager runs when the system runs out of free memory and can take significant time. To standardise when this happens, run GASMAN("collect") before each test.

Finally, the GAP mailing list archive has this post about garbage collection.

EDIT: You can add options to the automorphism_group method so that it will return the order and not the group. Maybe that can solve your problem?

mylist=[]
count = 0
while True:
    g = graphs.RandomGNP(6, .5)
    mylist.append(g)
    if g.automorphism_group(order=True,return_group=False) > 1:
        print "Graph number %s has nontrivial automorphisms!"%(count)
    count += 1

edit flag offensive delete link

Comments

Thanks for the links and cleaning up my code. I've looked into what's going on in gap and it does look like a problem with gap's garbage collection being leaky, so I've contacted the gap folks.

MT ( 2013-07-29 09:55:23 +0100 )edit

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Force Gap to forget graph automorphism groups

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Force Gap to forget graph automorphism groups edit

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Force Gap to forget graph automorphism groups