Re: [Tutor] Depth First Search Listing all possible combinations
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 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 recursi
Re: [Tutor] Depth First Search Listing all possible combinations
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 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)
>>> q1
