[Tutor] Depth First Search Listing all possible combinations

[Alan Gauld]

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