[Tutor] Depth First Search Listing all possible combinations
Randolph Scott-McLaughlin II
randolph.michael.sm at gmail.com
Mon Nov 25 03:45:02 CET 2013
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.sm at 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.gauld at 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 at python.org
>> To unsubscribe or change subscription options:
>> https://mail.python.org/mailman/listinfo/tutor
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20131124/edb995d0/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: coding_ROUTES.py
Type: text/x-python-script
Size: 2228 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/tutor/attachments/20131124/edb995d0/attachment-0001.bin>
More information about the Tutor
mailing list