Better codes for ring-finding program in python

Question

I wrote a ring detection program in a very stupid way. Can anyone help to improve it? The following code is to find all 5-member rings. I need a general function which is able to find N-member rings, where N is typically less than 10. Thanks a million!

In my problem, I have about 2000 points. Each point connected to several other points, these connected points are stored in neighbor_list. And the point[i].neighbor_list() return a list of the neighbors of point[i]. The idea in the following code is starting from one point, traverse its neighbor list and it's neighbor's neighbor list, and so on, to find the routes/cycles/rings to go back to the original point. The central part of my code is the following, which finds only rings formed by 5 points. I need a general code to find all N-member rings. Please leave a comment if anything is not clear.

for r0 in range(2000): #ring member 0
    rin.append(r0)
    for r1 in point[r0].neighbor_list():
        rin.append(r1) #ring member 1 
        for r2 in point[r1].neighbor_list():
            if r2 == r0: continue # to avoid the case of a-b-a ...
            else: rin.append(r2)
            for r3 in point[r2].neighbor_list():
                if r3 == r1: continue
                else: rin.append(r3)
                for r4 in point[r3].neighbor_list():
                    if r4 == r2: continue
                    else: rin.append(r4)
                    for r5 in point[r4].neighbor_list():
                        if r5 == r0: 
                            rin.append(r5)
                            rings.append(list(rin)) # find a ring, save it
                            rin.pop()
                        else: continue  
                    rin.pop()
                rin.pop()
            rin.pop()
        rin.pop()
    rin.pop()

And what are these objects such that `neighbor_list()` works? (and what does it return despite the obvious!) — Jon Clements, Aug 27 '13 at 15:07
to That1Guy and Jon Clements: Thanks for the response. I am sorry for the confusing message. Each point connected to several points, these connected points are stored in its neighbor_list. And the point[i].neighbor_list() return a list of these neighbors. So the idea is starting from one point, traverse its neighbor list and it's neighbor's neighbor list, see if there is a route go back to the original point. The route is defined as a ring. Let me know if it is still not clear. — Greg, Aug 27 '13 at 16:00
@That1Guy: Thanks for the response. Please see above my explanation. — Greg, Aug 27 '13 at 16:10
@Jon Clements: Thanks for the response. Please see above my explanation — Greg, Aug 27 '13 at 16:10
I have added "Graph theory" tag. Your problem involve a graph. You may want to explore this subject as it is very interesting and useful. — MatthieuW, Aug 27 '13 at 18:15
I edited my question, hope it's more clear now, although I believe the original question is clear enough with the code itself. Hope Slater Tyranus, glts, Viktor Kerkez, and George Stocker can release their hold soon. — Greg, Aug 27 '13 at 21:15

score 1 · Accepted Answer · edited May 23 '17 at 12:29

1

You are trying to find cycles of size N in an undirected graph.

You may find all cycles and then select the ones with right size. See this answer. Finding all cycles in undirected graphs

edited May 23 '17 at 12:29

Community

1
1

answered Aug 27 '13 at 16:06

MatthieuW

2,292
15
25

Thanks for the answer. I need some time to learn the "breadth first search" to see if it works for me. – Greg Aug 27 '13 at 16:18
The first link I put was not correct, it was for detecting one cycle. I quickly edited it to "all cycles" but not quickly enough. You are lucky, there is even an answer python code with this question. (I didn't test it) – MatthieuW Aug 27 '13 at 18:03
Thanks again. The python code in the link doesn't seem work for my problem. I have 2000 points and about 8000 edges, which might make it impossible to find all cycles. I tried to give a break, "if len(path) > 10: break", to the loop "for edge in graph:", that did not seem to help either. I never find any cycle by that code, while my code above take 1 second to find all 5-points cycles. – Greg Aug 27 '13 at 20:16

Better codes for ring-finding program in python

1 Answers1