Re: MemoryError when using nx.simple_cycles on a 55 nodes complete digraph.

[freak...@gmail.com]

I tried to run the same array on a 64bit desktop with 6Gb of ram. The RAM was at 1.7Gb when the script started and reached 3.55Gb when it spited the MemoryError.

However, this time, as I was not in debug mode, it gave the traceback debug, as follows:

  File "<string>", line 2, in simple_cycles
  File "C:\Python27\lib\site-packages\networkx\utils\decorators.py", line 63, in _not_implemented_for
    return f(*args,**kwargs)
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 205, in simple_cycles
    dummy=circuit(startnode, startnode, component)
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit
    if circuit(nextnode, startnode, component):
  File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 165, in circuit
    result.append(path + [startnode])
MemoryError
>>>

Thanks a lot for your help,

Aleix

On Thursday, June 6, 2013 8:56:29 PM UTC-3, freak...@gmail.com wrote:

Dear All,

I just bumped into a MemoryError when I was debugging the following lines:

working_array_digraph=nx.DiGraph(working_array)

cycles_list = nx.simple_cycles(working_array_digraph)

where working_array is a table representing 55 nodes, i.e. an array of shape (55,55) which thus contains 3025 values.

so I think the cycles_list should be about 5*10^95 long but I might be wrong

After running for 25minutes, the last line of the code above spit out:

MemoryError: MemoryError()

I am on Linux, spider 2.1.13, python 2.7.3 32 bits and I have 6Gb of Ram in my laptop with an i5 CPU. (Actually 8Gb but the 32bits version of the OS cannot use them all).

How can I debug this more finely and are there any workarounds to be able to find all simple cycles of the array I am working with?

Thanks a lot to all!

Aleix

[freak...@gmail.com]

Actually, the issue is more worrying than expected: the simple_cycles returns the MemoryError for a complete digraph as smal as with 10 nodes (with 9 or less it is fine):

>>> matrix=np.ones((9,9))
>>> working_array_digraph=nx.DiGraph(matrix)
>>> cycles_list = nx.simple_cycles(working_array_digraph)
>>> len(cycles_list)
125673

HOWEVER,

>>> matrix=np.ones((10,10))

>>> working_array_digraph=nx.DiGraph(matrix)

>>> cycles_list = nx.simple_cycles(working_array_digraph)

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

File "<string>", line 2, in simple_cycles

File "C:\Python27\lib\site-packages\networkx\utils\decorators.py", line 63, in _not_implemented_for

return f(*args,**kwargs)

File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 205, in simple_cycles

dummy=circuit(startnode, startnode, component)

File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit

if circuit(nextnode, startnode, component):

File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit

if circuit(nextnode, startnode, component):

File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit

if circuit(nextnode, startnode, component):

File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit

if circuit(nextnode, startnode, component):

File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit

if circuit(nextnode, startnode, component):

File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit

if circuit(nextnode, startnode, component):

File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit

if circuit(nextnode, startnode, component):

File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit

if circuit(nextnode, startnode, component):

File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 168, in circuit

if circuit(nextnode, startnode, component):

File "C:\Python27\lib\site-packages\networkx\algorithms\cycles.py", line 165, in circuit

result.append(path + [startnode])

MemoryError

[Dan Schult]

Would it be possible to try it using the code in the pull request?
I think if the list of cycles is going to be 10^95 long, we're not going to be able to help. But maybe you should think about cycle_basis which gives a basis for all cycles and then all possible cycles can be created from that basis.

It certainly could be true that the recursive nature of this algorithm demands memory. But I think the issue is bigger than that. Listing all elementary cycles for most graphs is not practical. Maybe we should provide more warnings of this fact in the docs.
Dan

[freak...@gmail.com]

Dear all,

I made some tests. Just a reminder that finding all simple cycles of a complete digraph is the very worst case of finding simple cycles since all simple cycles are present. The trend of number of simple cycles I found is about (nbr_nodes-1)!*3 (I know that the number of Hamiltonian cycles of a complete digraph is (nbr_nodes-1)!. The (nbr_nodes-1)!*3 number is an approximation I found after calculating the simple cycles for complete digraphs from 2 to 11 nodes.

Both simple_cycle.py and the new code suggested above (simple_cycle2.py) have similar cpu times (but I guess this is because it is the worst case for finding the simple cycles). Both manage to find the simple cycles of a complete digraph up to 11 nodes. From 12 nodes onwards, it raises a memory error.

Thus, the biggest simple cycle list that simple_cycles.py is able to calculate is for an 11 node complete digraph which contains 10 976 184 cycles.

According to the approximation of cycles described above, the list containing all simple cycles of a 12 node complete digraph contains about 120E6 cycles (of which one third are hamiltonian cycles, i.e. 12 nodes long, and the rest simple cycles of smaller length); but it seems that this is already too much for python or the module.

This is however against python's max capacity (unless my back-of-the-envelope calculation is wrong). According to http://stackoverflow.com/questions/855191/how-big-can-a-python-array-get
'''According to the source code, the maximum size of a list is PY_SSIZE_T_MAX/sizeof(PyObject*).
PY_SSIZE_T_MAX is defined in pyport.h to be ((size_t) -1)>>1
On a regular 32bit system, this is (4294967295 / 2) / 4 or 536870912.
Therefore the maximum size of a python list on a 32 bit system is 536,870,912 elements.
As long as the number of elements you have is equal or below this, all list functions should operate correctly.'''

The question is then: if the size all cycles of a 12 nodes complete digraph should be below 536E6 elements so why does simple_cycle.py run out of memory? (see below for a quick code to replicate the error)

The memory error is raised when appending to the final results list The error is:
File "/usr/lib/pymodules/python2.7/networkx/algorithms/cycles.py", line 161, in circuit

result.append(path + [startnode])
MemoryError

So how can this limitation be overcome? Would it be possible to split the results list every, say, 10 million elements (i.e. cycles)?

I will also explore the possibility of using cycle_basis, but I believe it is not the way to follow in my case. I ran the test above on a complete digraph to show the worst case. What I do in my case is to find all simple cycles between the economic sectors which are usually represented by a complete digraph. However, I subtract those cycles according to some weighting algorithm and need to iterate it over the remainder of the original array to subtract the remaining cycles, that is why I need to recalculate the remaining cycles within that graph (which then is not a complete digraph any more because some arcs are zeroed after some iterations). I believe I really need to use the simple_cycles.py module. The issue is that although I can aggregate the sectors economy not to exceed the calculation capacity of simple_cycles.py (i.e. reduce the economy to 11 sectors), this is really hindering the possible analyses since this level of aggregation is too coarse compared to the original data set which contains about 55 sectors.

Thanks a lot,

Aleix

========= code replicating error =============
import networkx as nx
nbr_nodes=12
working_array_digraph=nx.DiGraph(np.ones((nbr_nodes,nbr_nodes)))
all_cycles = nx.simple_cycles(working_array_digraph)
print('''... There are {0} simple cycles in a {1} node complete digraph '''.format(len(all_cycles),nbr_nodes))

[franck kalala]

Hi all,

Is there any way that networkx can read spss file?

Merci

[Dan Schult]

When you describe the largest list possible, that's based on how big the index can be.  The memory error is almost certainly due to running out of memory--not running out of index space.  Remember too that each element of the list takes up memory too.

The more interesting question for me is whether you really need a single list with all these cycles in it.  Is there a better way to store that information so that you can recreate the entire list one at a time without having to hold it all in memory at once?  That's why I like the idea of using cycle_basis instead of simple_cycles.  Since every simple cycle is the "sum" of cycles in the cycle basis, you can store the cycle basis and still create all simple cycles as needed.  But there may be something better than cycle_basis for your problem.  I can't quite understand your algorithm from your description but it sounds like a function that generates each cycle in turn, rather than generating a single list of cycles would beat the combinatorial demon of factorial growth in array size.

Dan

 

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.
Visit this group at http://groups.google.com/group/networkx-discuss?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Aleix]

Hi Dan,

thanks for your reply.

The issue for me is that I do not need "all" cycles of the graph. I just need the cycles that really appear on the graph. The problem is that the graphs I usually work with are almost complete and thus have a lot of cycles in it.

What I do is processing the graph and extract the simple cycles that it originally contained iteratively, so I need to recalculate the remaining cycles after the each cycle extraction because I do not extract each cycle at once but small parts of several cycles. Specifically, what I do is find the weakest cycling  flow (i.e. the weakest arc of all cycles) and divide it between  all the cycles sharing that arc. The division/allocation of the weakest arc is made according the the circuit probabilities of each cycle and their weight.

However, I liked you idea/ question "The more interesting question for me is whether you really need a single list with all these cycles in it." Would it be possible to apply that with simple_cycles? I would not mind getting several lists containing the simple cycles of the graph.

Thanks a lot,

Aleix

2013/6/10 Dan Schult <dsc...@colgate.edu>

--
You received this message because you are subscribed to a topic in the Google Groups "networkx-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/networkx-discuss/6FiQy-cxsBM/unsubscribe?hl=en.
To unsubscribe from this group and all its topics, send an email to networkx-discu...@googlegroups.com.

[Dan Schult]

Hi Aleix,
So, it looks like you need to be able to find the edge that is the "weakest arc" (to know which to remove) and to know all the cycles through that edge. (to be able to divide the edge weight between each cycle).
That sounds like you need an algorithm to find "weakest arc" rather than finding all simple cycles.

What do you mean by weakest arc? You mention circuit probabilities of each cycle and their weight, but also cycling flow. Its hard to tell if that is something that might involve our flow algorithms or not...
Dan

[Aleix]

Hi Dan,

Yes!!! that might be the solution! I was first finding all cycles and then finding the weakest arc within all cycles, I could do it the other way around as you suggested: first find the weakest arc and then find all cycles that go through that arc (if none, I will just skip that arc and never visit it again), then the algorithm will be much quicker because it does not need to find all simple cycles at once but only the ones going through that particular arc. I will have a look how to do that and whether it would gather the same result (if you already know a function of networkx finding all cycles going through a specific arc, please let me know).

Sorry I was not consistent in the terms I used. I actually wrongly used the term weakest cycling flow. I meant the weakest arc weight within all cycles. The arc weight being defined as usual (in my case representing a flow: the amount of materials in tons going from one node (economic sector) to another). The circuit probability of a cycle is the probability of a particle fulfilling that particular cycle (i.e. the product of all output probabilities of getting to the next node of the cycle).

Thanks a lot again for your help!

Aleix

[Aleix]

Dear Dan

I had a look at the network 1.7 reference and I saw that only simple_cycles and cycle_basis deal with cycles. They however do not allow to find all simple cycles going through a specific node nor specific edge. (BTW, in previous emails I was calling arcs edges; I believe they can be used interchangeably...I am afraid graph theory is not my main field).

However, I believe the simple_cycles function could be modified to accept more arguments defining the restriction of the search of simple cycles (i.e. accept node(s) and/or edge(s)). Do you think that is possible? (I am afraid I don't know how to do that). Also, this might be an improvement that is worth implementing in networkx since it allows a more "refined", less memory consuming search of simple_cycles.

Best,

Aleix

2013/6/10 Aleix <freak...@gmail.com>

[Dan Schult]

Dear Aleix,

The algorithm I think of for finding cycles starting from a specific node or edge involve a (graph theory jargon warning) depth first search.  In the search, if you bump into the starting node, then you have a cycle through that node.  If you start with an edge, then cycles that include that edge are just paths from one end of the edge to the other that don't go through the starting edge.  So the whole literature and vast set of algorithms for paths becomes available to find cycles.  I'm not sure if any of that will help you, but it is worth at least looking at a simple shortest_path function to see how it is done and think about how that might help you.

The other approach to your problem which is the approach I might try for a large graph and I understand is related to how Google finds eigenvectors for these huge networks it looks at:

Actually do the simulation of particles moving across the network and compute the cycles they make.  You may not get THE weakest arc, but you should get very close fairly quickly.  And that is often good enough to learn something.  

Anyway, those are two possible approaches.  I don't think the simple_cycles approach is reasonable given the size of the problems you are looking at.

Dan

[Aleix]

Dear Dan,

Thanks again for all your comments and support.

Finding the cycles within a graph is not a trivial task and as you mentioned there are several types of algorithms able to find them in the literature (see Mateti and Deo (1976) for a comparison); the most efficient algorithm is the Johnson (1975) algorithm (also reviewed  in the Mateti and Deo paper), which is the one implemented in nx.simple_cycles. That is why I want to stick to it.

On the other hand, I think figured out how to restrict the simple_cycles search to a single (or few) nodes; and also how to filter the results containing a specific arc/edge. I believe this would be an enhancement of the module worthy to be implemented in netwokx since it would enable more refined searches, and thus quicker and requiring less memory. Do you know how where I can suggest the new code? Is it in the developper mailing list?

Best,

Aleix

[Aleix]

sorry I forgot the references:

Johnson, Donald B. 1975. “Finding All the Elementary Circuits of a Directed Graph.” SIAM Journal on Computing 4 (1) (March): 8. doi:http://dx.doi.org/10.1137/0204007.

Mateti, Prabhaker, and Narsingh Deo. 1976. “On Algorithms for Enumerating All Circuits of a Graph.” SIAM Journal on Computing 5 (1) (March): 10. doi:http://dx.doi.org/10.1137/0205007.

2013/6/11 Aleix <freak...@gmail.com>

[Dan Schult]

Other references I have found helpful---though not helpful enough to put in the codebase:
References
----------
.. [1] Enumerating the cycles of a digraph: a new preprocessing strategy.
G. Loizou and P. Thanish, Information Sciences, v. 27, 163-182, 1982.
http://dx.doi.org/10.1016/0020-0255(82)90023-8

.. [2] A search strategy for the elementary cycles of a directed graph.
J.L. Szwarcfiter and P.E. Lauer, BIT NUMERICAL MATHEMATICS,
v. 16, no. 2, 192-204, 1976.
http://dx.doi.org/10.1007/BF01931370

[Aleix]

Hi,

Thanks, I did not know them. They are backtracking algorithms, as the Johnson one. The Szwarcfiter and Lauer runs in O(N +M(C + 1)) time while the Johnson in O(N +M)(C + 1)). I have no idea whether that is much difference.

However, both will encounter the same issue: the result array containing all cycles will trigger a memory error since there are simply too many elementary circuits to enumerate. So, the problem is rather how to refine the search rather than finding a quicker algorithm.

However, some people in the devel list were suggesting to improve the simple_cycles module speed-wise. Maybe you can suggest the Szwarcfiter and Lauer algorithm.

I will focus on narrowing the search of cycles for a give specific node and also on filtering the result array by cycles containing a specific arc. The first will increase speed (since it will narrow the search) and both delay the memory error and bigger graphs can be analysed since the result array will be smaller. I can let you know when I create the discussion if you are interested.

Best,

Aleix

2013/6/11 Dan Schult <dsc...@colgate.edu>