Ask Your Question

fmorlin's profile - activity

2019-09-15 13:57:14 +0100 received badge  Scholar (source)
2019-09-15 09:32:59 +0100 received badge  Good Question (source)
2019-09-15 06:01:19 +0100 received badge  Supporter (source)
2019-09-13 16:05:43 +0100 received badge  Nice Question (source)
2019-09-13 16:03:35 +0100 commented answer Memory leak with matroid is_connected method

Thank you for your answer! I verified and in fact there was no memory leak occurring in the first code snippet I posted. The issue appears to be related with the is_connected() method.

2019-09-13 11:32:59 +0100 received badge  Student (source)
2019-09-12 23:59:40 +0100 received badge  Editor (source)
2019-09-12 13:41:20 +0100 asked a question Memory leak with matroid is_connected method


I've been using Graphic Matroids to deal with some enumeration problems, where I filter a list of graphs based on their flats. Even without really undestanding what happens at low level, I could verify that the computation is faster when I build the equivalent representation of each graphic matroid using the Incidence matrix of the graph over GF(2).

One big issue that I am facing is that some memory leak is ocurring. As the size of my list of graphs grows, the ram memory got consumed until a point that my computer breaks down and restarts. My way out has been to use a bash script to keep calling the main program until I reach the end of an external text file (the input).

To force the gc.collect() seems to not be an option, because the program becomes really slow.


The memory leak seems to be related with the is_connected method. Here is a piece of my code showing two different situations:

With the use of is_connected:

sage: G = [g for g in graphs.nauty_geng("12 16:16 -Ct")]
sage: len(G)
sage: print(get_memory_usage())
....: for g in G:
....:     A = g.incidence_matrix()
....:     M = Matroid(A, ring = GF(2))
....:     if M.is_connected():
....:         pass
....: print(get_memory_usage())

and without:

sage: print(get_memory_usage()) 
....: for g in G:
....:     A = g.incidence_matrix()
....:     M = Matroid(A, ring = GF(2))
....:     for r in range(M.corank()):
....:         for F in M.coflats(r):
....:             pass
....: print(get_memory_usage())


Ok, I solved my problem by just explicitly declaring the function is_connected in the body of my code, instead of using the method present in the abstract matroid class. I'm not sure about why it really worked, I tried this approach because I thought it had something to do with the lists that are created by the components method, however I stopped investigating when I notice the memory leak vanished just by using the function. To be honest, I changed the script to not return any output (there was an option to input a certificate flag and return the components).

I'm letting the code below for the case someone faces a similar problem or has any better solution or clue about why it happened:

cpdef components(self):

    B = self.basis()
    components = [frozenset([e]) for e in self.groundset()]

    for e in self.groundset() - B:
        C = self.circuit(B | set([e]))
        components2 = []
        for comp in components:
            if len(C & comp) != 0:
                C = C | comp
        components = components2
    return components

cpdef is_connected(self):

    comp = components(self)

    if len(comp) == 1:
        return True
        return False