<div dir="ltr"><img src="cid:ii_14286ddecf8fd49b" alt="Inline image 2" width="414" height="310"><img src="cid:ii_14286ddc25a8591d" alt="Inline image 1" width="414" height="310">Hi Tutors,<div><br></div><div>So I'm writing code for a depth first search where I have 1 start point and 1 end point. Between those points there are a series of 1-way roads that goes from one vertex to the next. Sometimes the vertex can have 4 or 5 one way road paths going into it or out of it. </div>
<div><br></div><div>What I want to do is list each unique possible path someone can go from the start to end point, have the list written out and ideally labeled as "list'n'". </div><div><br></div><div>Here's some code that I started off with but I keep getting errors and in general can't get it to do what I want it to do. If you could guide me in the right direction or tell me how I can alter the code I've been coming across to fit my needs that'd be great. </div>
<div><br></div><div>I've also attached an image of the road map that I'm trying to develop, along with the decisional points that each vertex can take someone to and from. Thanks for help!</div><div><br></div><div>
<div>#start=q9</div><div>q9 = (10, 33)</div><div>q10 = (11, 28, 29, 30)</div><div>q11 = (15)</div><div>q16 = (17,19,24)</div><div>q18 = (17, 19, 24)</div><div>q24 = (25, 26)</div><div>q27 = (34)</div><div>q28 = (29, 30)</div>
<div>q30 = (12, 31, 34)</div><div>q32 = (34)</div><div>q33 = (15, 30)</div><div>q35 = (36, 37)</div><div>q37 = (38, 39)</div><div>q39 = (40, 41, 99)</div><div>#end = 99</div></div><div><br></div><div><div>#trying new DFS code</div>
<div>parent = {s:None}</div><div>def DFS_VISIT(V, Adj,s):</div><div> for v in Adj[s]:</div><div> s.inprocess=True</div><div> if v not in parent:</div><div> s.inprocess=False</div><div> parent[v]=s</div>
<div> DFS_VISIT(V,Adj,s)</div><div>#dfs visit code, controls checking notes around you</div><div>def dfs(V,Adj):</div><div> parent = {}</div><div> for s in V:</div><div> if s not in parent:</div><div>
parent[s] = None</div><div> DFS_VISIT(V,Adj,s)</div><div><br></div><div>#dfs has you start from any new vertex point possible</div></div><div><br></div><div>This is about as far as I've gotten writing my own code. I have found some other DFS algorithms but I'm not sure how to adapt it to fit my needs. </div>
<div><br></div><div><div>import sys</div><div><br></div><div>def extractPaths(current_node,path,loops_seen):</div><div> path.append(current_node)</div><div> # if node has outgoing edges</div><div> if nodes[current_node]!=None:</div>
<div> for thatnode in nodes[current_node]:</div><div> valid=True</div><div> # if the node we are going to has been</div><div> # visited before, we are completeing</div><div> # a loop.</div>
<div> if thatnode-1 in path:</div><div> i=len(path)-1</div><div> # find the last time we visited</div><div> # that node</div><div> while path[i]!=thatnode-1:</div>
<div> i-=1</div><div> # the last time, to this time is</div><div> # a single loop.</div><div> new_loop=path[i:len(path)]</div><div> # if we haven't seen this loop go to</div>
<div> # the node and node we have seen this</div><div> # loop. else don't go to the node.</div><div> if new_loop in loops_seen:</div><div> valid=False</div>
<div> else:</div><div> loops_seen.append(new_loop)</div><div> if valid:</div><div> extractPaths(thatnode-1,path,loops_seen)</div><div> # this is the end of the path</div>
<div> else:</div><div> newpath=list()</div><div> # increment all the values for printing</div><div> for i in path:</div><div> newpath.append(i+1)</div><div> found_paths.append(newpath)</div>
<div> # backtrack</div><div> path.pop()</div><div><br></div><div># graph defined by lists of outgoing edges</div><div>nodes=[[2],[3],[4],[5,9],[6,7],[7],[4,8],None,None]</div><div># I tried this but it didn't work nodes=zip(['q9','q10','q11','q16','q18','q24','q27','q28','q30','q32','q33','q35','q37','q39'],[(10,33),(11, 28, 29, 30), (15),(17,19,24),(25, 26),(34),(29, 30),(34),(15, 30),(36, 37),(38, 39),(40, 41, None)])</div>
<div>#also tried this but it ididn't work nodes = {1: [2, 3],2: [1, 4, 5, 6],3: [1, 4],4: [2, 3, 5],5: [2, 4, 6],6: [2, 5]}</div><div>found_paths=list()</div><div>extractPaths(0,list(),list())</div><div>for i in found_paths:</div>
<div> print(i)</div></div><div><br></div><div><br></div><div>Best,</div><div>Randy</div></div>