[Tutor] Depth First Search Listing all possible combinations

[Randolph Scott-McLaughlin II]

[image: Inline image 2][image: Inline image 1]Hi 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 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.

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!

#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

#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)
#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)

#dfs has you start from any new vertex point possible

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.

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)


Best,
Randy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20131123/8b9e553f/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image (3).jpeg
Type: image/jpeg
Size: 1321086 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/tutor/attachments/20131123/8b9e553f/attachment-0002.jpeg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image (1).jpeg
Type: image/jpeg
Size: 1295221 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/tutor/attachments/20131123/8b9e553f/attachment-0003.jpeg>