#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2011
    Posts
    19
    Rep Power
    0

    Exclamation Building a list of shortest path and relationship from a CSV file


    Hi all, I need your help on an incomplete code which I wrote to handle the issue I have.

    So I have this input file :-

    Code:
    -----INPUT FILE : test2.csv-----
    #child, parent, relation
    M3,Q,P
    M54,M7,P
    M54,M27,E
    Q,M7,P
    M7,Q,E
    M7,M3,P
    M27,Q,E
    Code:
    ======OUTPUT REQUIRED====
    M3->Q,P
    M54->M7->Q,P
    M7->Q,E
    M27->Q,E

    ==========PROBLEM EXPLANATION=============
    Q is the ultimate parent. I want to trace all childs back to Q (the shortest path to parent 'Q').
    For example for the first row, the output should be =
    Code:
    M3->Q, P
    .
    But second row, M54 is child of M7 with a relation tag of 'P' (M54->M7, P), but we need to traverse M7 to the ultimate parent who is 'Q'. As we search through along the csv file for M7's parent, we see that from row 5 & 6, M7 can have either 'M3' as his parent or 'Q' as his parent. So we have two paths tracing to the ultimate parent Q :-
    Code:
    M54->M7->Q,PE & M54->M7->M3->Q,PPP
    But we would like to have the shortest path only , i.e.
    Code:
    M54->M7->Q,PE
    Another issue is that we also have cyclic paths, eg consider row 4 & 5 :-
    Code:
    Q,M7,P
    M7,Q,E
    So in such a case we would like the output as M7->Q,E (rather than Q->M7->Q as one would expect).

    This is the code Ive come up with so far :-

    Code:
    # Read the csv file
    import csv
    z=[]
    with open('test2.csv', 'rb') as f:
        reader = csv.reader(f)
        for row in reader:
            z.append(row)        
             
    # Now generate list-of-list to store relations. Eg [['M7', 'Q', ['P']],.....
    for i in range(len(z)):
        t=z[i].pop()
        z[i].append([t])
     
    # Now lets populate the list   
    t=[]    
    out=[]
    for i in range(len(z)):
        child = z[i][0]
        if z[i][1]=='Q': #whos the parent ?
                out.append(z[i])
                continue
        t.append(z[i])
        index=t.index(z[i])
        print (index)
        parent=t[index][1]
        print (parent)
        length=len(t[index])
        for j in range(len(z)):
            if z[j][0] == child:
                if z[j][1]=='Q':
                    t[index].insert(length,'Q')
            
    #print (parent)
    print ("temp=",t)
    print ("out=",out)
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2009
    Posts
    491
    Rep Power
    33
    It would help if you provided distances between the points as we have no idea what they are and also explain what records like M54,M7,P mean.. I diagram would also help as distance is not enough. If I go X distance south from A expecting to hit B, but B is north of A, then you would never hit B unless you went all the way around the world. There are many sites that address the logic used to solve the Traveling Salesman Problem that you could read to get a better idea of what is to be done, like http://polynomialtimes.com/algorithm...esman-problem/ Finally do some testing of the code posted. This block will produce an error
    Code:
    for i in range(len(z)):
        t=z[i].pop()
        z[i].append([t])
    Last edited by dwblas; December 26th, 2013 at 11:19 AM.
  4. #3
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,854
    Rep Power
    481
    Likewise, I don't understand your input. The comment and data suggest each row has three fields child, parent, and relation.

    The words of the comment confuse me.
    child and parent specify a relation.
    Thus I ignore the third field while reconciling that it has a purpose.

    Anyway, the data appears to represent a graph. You'll probably want Dijkstra's algorithm. solving a maze in python with Dijkstra's algorithm
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo