Problem with arrays in a recursive class function

[Aaron Scott]

I have a list of nodes, and I need to find a path from one node to
another. The nodes each have a list of nodes they are connected to,
set up like this:



class Node(object):
def __init__(self, connectedNodes):
self.connectedNodes = connectedNodes

nodes = {
1: Node([4]),
2: Node([3]),
3: Node([2, 4, 5]),
4: Node([1, 6, 3]),
5: Node([3, 7]),
6: Node([4, 9]),
7: Node([5, 8]),
8: Node([7, 9]),
9: Node([6, 8])
}



I made a quick brute-force pathfinder to solve it (in this case, a
path from node 1 to node 9). Here it is:



class PathFind(object):
def __init__(self, source, destination):
self.source = source
self.destination = destination
self.solved = []
def Search(self):
self.PathFind([self.source])
if self.solved:
print "Solutions: "
for i in self.solved:
print "\t" + str(i)
else:
print "Couldn't solve."
def PathFind(self, trail):
location = trail[-1]
if location == self.destination:
self.solved.append(trail)
print "Solution found: " + str(trail)
else:
possibilities = []
for i in nodes[location].connectedNodes:
if not i in trail: possibilities.append(i)
for i in possibilities:
trail.append(i)
self.PathFind(trail[:])
if not possibilities:
print "Dead end: " + str(trail)

finder = PathFind(1, 9)
finder.Search()



Unfortunately, it doesn't seem to be giving me the result I was after.
This is the output:



Solution found: [1, 4, 6, 9]
Dead end: [1, 4, 6, 3, 2]
Solution found: [1, 4, 6, 3, 2, 5, 7, 8, 9]
Solutions:
[1, 4, 6, 9]
[1, 4, 6, 3, 2, 5, 7, 8, 9]



The problem is the array trail[], which seems to survive from instance
to instance of PathFind(). I thought that by calling self.PathFind
(trail[:]), I was creating a new copy of trail[], but obviously
something isn't running like I expected. Is there something I'm
misunderstanding here, or is there just a stupid bug in my code I
haven't caught?

 

[Aaron Scott]

Never mind -- ditched the attempt and implemented Dijkstra.

 

[Bruno Desthuilliers]

Aaron Scott a écrit :

I have a list of nodes, and I need to find a path from one node to
another. The nodes each have a list of nodes they are connected to,
set up like this:



class Node(object):
def __init__(self, connectedNodes):
self.connectedNodes = connectedNodes

nodes = {
1: Node([4]),
2: Node([3]),
3: Node([2, 4, 5]),
4: Node([1, 6, 3]),
5: Node([3, 7]),
6: Node([4, 9]),
7: Node([5, 8]),
8: Node([7, 9]),
9: Node([6, 8])
}



I made a quick brute-force pathfinder to solve it (in this case, a
path from node 1 to node 9). Here it is:



class PathFind(object):
def __init__(self, source, destination):
self.source = source
self.destination = destination
self.solved = []
def Search(self):
self.PathFind([self.source])
>
if self.solved:
print "Solutions: "
for i in self.solved:
print "\t" + str(i)

print "\t%s" % i

else:
print "Couldn't solve."
def PathFind(self, trail):
location = trail[-1]
if location == self.destination:
self.solved.append(trail)

I think you want
self.solved.append(trail[:])

Hint : Python doesn't use "pass by value".

> The problem is the array trail[], which seems to survive from instance
to instance of PathFind(). I thought that by calling self.PathFind
(trail[:]), I was creating a new copy of trail[],

Yes. But on the 'not solved' branch, you do mutate trail !-)