[Tutor] Depth First Search Listing all possible combinations
Randolph Scott-McLaughlin II
randolph.michael.sm at gmail.com
Sun Nov 24 02:41:21 CET 2013
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/20131123/139949f2/attachment-0001.html>
More information about the Tutor
mailing list