Welcome, guest | Sign In | My Account | Store | Cart

Finding complete loops in a map of connected nodes (Python recipe) by Sachin Joglekar
ActiveState Code (http://code.activestate.com/recipes/578110/)

This module finds loops in a given map.Input is a dictionary like

d={1:[2,4,5,6],2:[1,3],3:[2,4,5,6],4:[1,3,5],5:[1,3,4],6:[1,3]}

this means node 1 is connected to nodes 2,4,5 and 6 and so on..

Output is a list of complete loops. for above examples,output is

[[1, 4, 5, 1], [3, 4, 5, 3], [1, 2, 3, 4, 1], [1, 2, 3, 5, 1], [1, 2, 3, 6, 1], [1, 4, 3, 5, 1], [1, 4, 3, 6, 1], [1, 5, 3, 6, 1], [1, 2, 3, 4, 5, 1], [1, 4, 5, 3, 6, 1]]

Python, 41 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def copy(l):
    l2=[]
    for x in l:
        l2.append(x)
    return l2
def loops(d):
    l=[]
    for x in d:
        l.append(x)
    lreq=[]
    lreq2=[]
    ltemp=[]
    for x in l:
        ltemp=[]
        ltemp.append(x)
        lreq2.append(ltemp)
    t=1
    while (t<=(len(l)-1)):
        lreq3=[]
        for x in lreq2:
            ltemp=copy(l)
            for y in x:
                ltemp.remove(y)
            for y in ltemp:
                h=copy(x)
                if y in d[x[-1]]:
                    h.append(y)
                    lreq3.append(h)
        if t>=2:
            for x in lreq3:
                if x[0] in d[x[-1]]:
                    h=copy(x)
                    h.append(h[0])
                    lreq.append(h)
        lreq2=copy(lreq3)
        t+=1
    for x in lreq:
        for y in lreq[(lreq.index(x)+1):]:
            if set(x)==set(y):
                lreq.remove(y)
    return lreq

developed this as a part of our project to build a circuit solver module in python. Just thought of sharing :)

Tags: circuit, connection, loops

1 comment

Mauricio Dada Fonseca de Freitas 11 years, 12 months ago  # | flag

The idea is very interesting. I haven't really read the full code, but I'll definitely try to understand it better sometime.

One question: How does the code scales? Have seen a lot loops. Maybe you wont have a huge data set to deal with, but it's definitely something deserving of attention.

A tip: if you want to copy a list you can just use:

l2 = l[:]

And of course, some comments and better variable names would really help code maintenance (you'll thank the effort later, through the project execution). And, since you're sharing the code, it'll help people understand it better!

Hope my comments were helpful.