December 25th, 2013, 03:23 AM

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 = .
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. Another issue is that we also have cyclic paths, eg consider row 4 & 5 :
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 listoflist 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)
December 26th, 2013, 12:15 PM

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...esmanproblem/ 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 12:19 PM.
December 26th, 2013, 01:09 PM

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!