I solved the question thanks to Alan's suggestions. Attached is the .py file I ran to solve my question. Thanks guys.
On Sat, Nov 23, 2013 at 8:41 PM, Randolph Scott-McLaughlin II < randolph.michael...@gmail.com> wrote: > So I cleaned up the code to make it readable. I'm not getting an error > message now. What I'm getting is an empty bracket. I want to run > find_all_paths with my graph and then list the start and end point (in this > case that's q9 and q42) and then have it list a tuple of each path in a > separate line. Each path being a unique way to get to the end point. > > Here's what I enter and I get back [] > > >>> find_all_paths(graph, 'q9', 'q42') > > [] > > What I want is > > >>> find_all_paths(graph, 'q9', 'q42') > [q9, q10, q11 ,q15, q16, q17, q18, q20, q23, q34, q35, q36, q37, q38, q39, > q41, q42, end] > [then list another path.] > [list another path] > > graph = {'q9': ['q10', 'q33'], 'q10': ['q11', 'q 28', 'q29', 'q30'], > 'q11': ['q15'] , 'q16': ['q17', 'q19', 'q24'],' q18': ['q20'], 'q23': > ['q34'], 'q24': ['q25', 'q26'], 'q27': ['q34'], 'q28': ['q30', 'q29'], > 'q30': ['q34', 'q31', 'q12'], 'q32': ['q34'], 'q33': ['q15' , 'q30'], > 'q35': ['q36', 'q37'], 'q37': ['q38', 'q39'], 'q39': ['q41', 'q40', > 'q42'],'q42': ['end']} > > def find_path(graph, start, end, path=[]): > path = path + [start] > if start == end: > return path > if not graph.has_key(start): > return None > for node in graph[start]: > if node not in path: > newpath = find_path(graph, node, end, path) > if newpath: return newpath > return None > > > def find_all_paths(graph, start, end, path=[]): > path = path + [start] > if start == end: > return [path] > if not graph.has_key(start): > return [] > paths = [] > for node in graph[start]: > if node not in path: > newpaths = find_all_paths(graph, node, end, path) > for newpath in newpaths: > paths.append(newpath) > return paths > > > > > On Sat, Nov 23, 2013 at 7:13 PM, Alan Gauld <alan.ga...@btinternet.com>wrote: > >> On 23/11/13 21:30, Randolph Scott-McLaughlin II wrote: >> >>> Inline image 2Inline image 1Hi Tutors, >>> >>> >>> 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. >>> >>> 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'". >>> >>> Here's some code that I started off with but I keep getting errors >>> >> >> What kind of errors? >> And if there are error messages please provide copies of the entire error >> message not just a summary. They are usually extremely >> informative. >> >> >> in general can't get it to do what I want it to do. >>> >> >> What do you expect? What do you get? >> Don't force us to try to run it, guess what it should do, >> then assess what it is doing. >> Tell us. >> >> >> 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. >> >> We can try but you need to tell us more detail too. >> >> >> 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! >>> >> >> It may be helpful to somebody but not to me! :-( >> >> >> #start=q9 >>> q9 = (10, 33) >>> q10 = (11, 28, 29, 30) >>> q11 = (15) >>> q16 = (17,19,24) >>> q18 = (17, 19, 24) >>> q24 = (25, 26) >>> q27 = (34) >>> q28 = (29, 30) >>> q30 = (12, 31, 34) >>> q32 = (34) >>> q33 = (15, 30) >>> q35 = (36, 37) >>> q37 = (38, 39) >>> q39 = (40, 41, 99) >>> #end = 99 >>> >> >> Could you do a smaller example that exhibits the problem? >> >> >> #trying new DFS code >>> parent = {s:None} >>> def DFS_VISIT(V, Adj,s): >>> for v in Adj[s]: >>> s.inprocess=True >>> if v not in parent: >>> s.inprocess=False >>> parent[v]=s >>> DFS_VISIT(V,Adj,s) >>> >> >> You are using recursion but its not clear how you stop >> the recursion. Possibly when all elements of Adj[s] are >> not parents? But it looks lie you never use V and >> don't change Adj either. So I'm not sur4e how often >> this will recurse, but it may be more than the fixed >> limit compiled into Python. Is that one of the errors >> you get? >> >> >> #dfs visit code, controls checking notes around you >>> def dfs(V,Adj): >>> parent = {} >>> for s in V: >>> if s not in parent: >>> parent[s] = None >>> DFS_VISIT(V,Adj,s) >>> >> >> Note that you define a new 'parent' here. This is local to this function >> and hides the parent defined above DFS. But DFS will >> continue to use the one defined at the top. Is that what you expected? >> Its usually better to create unique names to avoid confusion. >> >> I have no idea what the stuff below does, it's way too much >> for me to try to wade through. I can't see any sign of you >> calling dfs() or DFS_VISIT() so I don't know what the >> connection is. I gave up at that point. Sorry. >> >> >> import sys >>> >>> def extractPaths(current_node,path,loops_seen): >>> path.append(current_node) >>> # if node has outgoing edges >>> if nodes[current_node]!=None: >>> for thatnode in nodes[current_node]: >>> valid=True >>> # if the node we are going to has been >>> # visited before, we are completeing >>> # a loop. >>> if thatnode-1 in path: >>> i=len(path)-1 >>> # find the last time we visited >>> # that node >>> while path[i]!=thatnode-1: >>> i-=1 >>> # the last time, to this time is >>> # a single loop. >>> new_loop=path[i:len(path)] >>> # if we haven't seen this loop go to >>> # the node and node we have seen this >>> # loop. else don't go to the node. >>> if new_loop in loops_seen: >>> valid=False >>> else: >>> loops_seen.append(new_loop) >>> if valid: >>> extractPaths(thatnode-1,path,loops_seen) >>> # this is the end of the path >>> else: >>> newpath=list() >>> # increment all the values for printing >>> for i in path: >>> newpath.append(i+1) >>> found_paths.append(newpath) >>> # backtrack >>> path.pop() >>> >>> # graph defined by lists of outgoing edges >>> nodes=[[2],[3],[4],[5,9],[6,7],[7],[4,8],None,None] >>> # 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)]) >>> #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]} >>> found_paths=list() >>> extractPaths(0,list(),list()) >>> for i in found_paths: >>> print(i) >>> >> >> -- >> Alan G >> Author of the Learn to Program web site >> http://www.alan-g.me.uk/ >> http://www.flickr.com/photos/alangauldphotos >> >> _______________________________________________ >> Tutor maillist - Tutor@python.org >> To unsubscribe or change subscription options: >> https://mail.python.org/mailman/listinfo/tutor >> > >
#graph = {'A': ['B', 'C'], 'B': ['C', 'D'], 'C': ['D'], 'D': ['C'],'E': ['F'], 'F': ['C']} #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)]) graph = {'START':[ 'q1-q8'], 'q1-q8':['q9'],'q9': ['q10', 'q33'], 'q10': ['q11', 'q28', 'q29', 'q30'], 'q11': ['q15'] , 'q12': ['q13'], 'q13': ['q14'], 'q14': ['q15'], 'q15': [ 'q16' ], 'q16': ['q17', 'q19', 'q24'], 'q17': ['q18'],' q18': ['q20-q23'], 'q19':['q20-q23'], 'q20-q23': ['q34'], 'q24': ['q25', 'q26'], 'q25': ['q26'], 'q26': ['q27'],'q27': ['q34'], 'q28': ['q30', 'q29'], 'q29': [ 'q30'], 'q30': ['q34', 'q31', 'q12'], 'q31': ['q32'],'q32': ['q34'], 'q33': ['q15' , 'q30'], 'q34': ['q35'], 'q35': ['q36', 'q37'], 'q36': ['q37'],'q37': ['q38', 'q39'], 'q38': ['q39'],'q39': ['q41', 'q40', 'END'], 'q40': ['q41'], 'q41': ['q42'], 'q42': ['END']} def find_path(graph, start, end, path=[]): path = path + [start] if start == end: return path if not graph.has_key(start): return None for node in graph[start]: if node not in path: newpath = find_path(graph, node, end, path) if newpath: return newpath return None def find_all_paths(graph, start, end, path=[]): path = path + [start] if start == end: return [path] if not graph.has_key(start): return [] paths = [] for node in graph[start]: if node not in path: newpaths = find_all_paths(graph, node, end, path) for newpath in newpaths: paths.append(newpath) return paths ROUTE=find_all_paths(graph, 'START', 'END') for index,elem in enumerate(ROUTE): print(index,elem) #next step for putting this in an excel spreadsheet code below is an example case that needs to be altered #import csv #with open(<path-to-file>, "w") as the_file: # csv.register_dialect("custom", delimiter=" ", skipinitialspace=True) # writer = csv.writer(the_file, dialect="custom") #for tup in tuples: # writer.write(tup)
_______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor