Adding to list a class instance

Question

I'm implementing a code to find the shortest path between two nodes, but why when I change the first line of the DFS function the output change too . Isn't it true that

path += [start] is equivalent to path = path + [start]?

the output before changing is ::

Current DFS path: 0
Current DFS path: 0->1
Current DFS path: 0->1->2
Current DFS path: 0->1->2->3
Current DFS path: 0->1->2->3->4
Current DFS path: 0->1->2->3->5
Current DFS path: 0->1->2->4
Current DFS path: 0->2
Current DFS path: 0->2->3
Current DFS path: 0->2->3->1
Current DFS path: 0->2->3->4
Current DFS path: 0->2->3->5
Current DFS path: 0->2->4
shortest path is  0->2->3->5

after changing is ::

Current DFS path: 0
Current DFS path: 0->1
Current DFS path: 0->1->2
Current DFS path: 0->1->2->3
Current DFS path: 0->1->2->3->4
Current DFS path: 0->1->2->3->4->5
shortest path is  0->1->2->3->4->5

The code ::

class Node(object):
    def __init__(self, name):
        """Assumes name is a string"""
        self.name = name
    def getName(self):
        return self.name
    def __str__(self):
        return self.name

class Edge(object):
    def __init__(self, src, dest):
        """Assumes src and dest are nodes"""
        self.src = src
        self.dest = dest
    def getSource(self):
        return self.src
    def getDestination(self):
        return self.dest
    def __str__(self):
        return self.src.getName() + '->' + self.dest.getName()

class WeightedEdge(Edge):
    def __init__(self, src, dest, weight = 1.0):
        """Assumes src and dest are nodes, weight a number"""
        self.src = src
        self.dest = dest
        self.weight = weight
    def getWeight(self):
        return self.weight
    def __str__(self):
        return self.src.getName() + '->(' + str(self.weight) + ')'\
               + self.dest.getName()

#Figure 12.8
class Digraph(object):
    #nodes is a list of the nodes in the graph
    #edges is a dict mapping each node to a list of its children
    def __init__(self):
        self.nodes = []
        self.edges = {}
    def addNode(self, node):
        if node in self.nodes:
            raise ValueError('Duplicate node')
        else:
            self.nodes.append(node)
            self.edges[node] = []
    def addEdge(self, edge):
        src = edge.getSource()
        dest = edge.getDestination()
        if not (src in self.nodes and dest in self.nodes):
            raise ValueError('Node not in graph')
        self.edges[src].append(dest)
    def childrenOf(self, node):
        return self.edges[node]
    def hasNode(self, node):
        return node in self.nodes
    def __str__(self):
        result = ''
        for src in self.nodes:
            for dest in self.edges[src]:
                result = result + src.getName() + '->'\
                         + dest.getName() + '\n'
        return result[:-1] #omit final newline

class Graph(Digraph):
    def addEdge(self, edge):
        Digraph.addEdge(self, edge)
        rev = Edge(edge.getDestination(), edge.getSource())
        Digraph.addEdge(self, rev)

#Figure 12.9
def printPath(path):
    """Assumes path is a list of nodes"""
    result = ''
    for i in range(len(path)):
        result = result + str(path[i])
        if i != len(path) - 1:
            result = result + '->'
    return result 

def DFS(graph, start, end, path, shortest, toPrint = False):
    """Assumes graph is a Digraph; start and end are nodes;
          path and shortest are lists of nodes
       Returns a shortest path from start to end in graph"""
    path = path + [start]
    if toPrint:
        print('Current DFS path:', printPath(path))
    if start == end:
        return path
    for node in graph.childrenOf(start):
        if node not in path: #avoid cycles
            if shortest == None or len(path) < len(shortest):
                newPath = DFS(graph, node, end, path, shortest,
                              toPrint)
                if newPath != None:
                    shortest = newPath
    return shortest

def shortestPath(graph, start, end, toPrint = False):
    """Assumes graph is a Digraph; start and end are nodes
       Returns a shortest path from start to end in graph"""
    return DFS(graph, start, end, [], None, toPrint)

#Figure 12.10
def testSP():
    nodes = []
    for name in range(6): #Create 6 nodes
        nodes.append(Node(str(name)))
    g = Digraph()
    for n in nodes:
        g.addNode(n)
    g.addEdge(Edge(nodes[0],nodes[1]))
    g.addEdge(Edge(nodes[1],nodes[2]))
    g.addEdge(Edge(nodes[2],nodes[3]))
    g.addEdge(Edge(nodes[2],nodes[4]))
    g.addEdge(Edge(nodes[3],nodes[4]))
    g.addEdge(Edge(nodes[3],nodes[5]))
    g.addEdge(Edge(nodes[0],nodes[2]))
    g.addEdge(Edge(nodes[1],nodes[0]))
    g.addEdge(Edge(nodes[3],nodes[1]))
    g.addEdge(Edge(nodes[4],nodes[0]))
    sp = shortestPath(g, nodes[0], nodes[5])
    print('Shortest path found by DFS:', printPath(sp))

Note :: this code is from this book enter link description here

Possible duplicate of [Why does += behave unexpectedly on lists?](http://stackoverflow.com/questions/2347265/why-does-behave-unexpectedly-on-lists) — Łukasz Rogalski, Dec 06 '16 at 12:20

John Coleman · Accepted Answer · 2016-12-06T12:28:05.103

3

They are not the same

path += [start] is equivalent to path.extend([start]) -- it mutates path.

On the other hand

path = path + [start] creates a new list and names it start.

Consider the following experiment, and note the IDs:

>>> a = [1]
>>> id(a)
55937672
>>> a += [2,3]
>>> id(a)
55937672
>>> b = [1]
>>> id(b)
55930440
>>> b = b + [1,2]
>>> id(b)
55937288

The ID of b changed but the ID of a didn't.

As to why it makes a difference in your code -- DFS is a function. In the version which uses path += [start], you are modifying the passed parameter path -- and this modification persists after the call returns. On the other hand, in the version which uses path = path + [start], you are creating a new local variable named path, one which goes out of scope when the call returns, without any changes to the parameter path.

edited Dec 06 '16 at 12:28

answered Dec 06 '16 at 12:16

John Coleman

51,337
7
54
119

Is this mean that using ' a = a + something ' better than using ' a += something ' to avoid unexpected bug ...? – Jafar Abdi Dec 06 '16 at 13:16
1

@JafarAbdi it depends on what you want to do. If you *want* to modify the original list then use `a += something` but if you want to get a new list then use `a = a + something`. If you are in a situation when it doesn't matter, I would go with `a += something` since it will be more memory efficient. On the other hand, in some contexts the side-effect of modifying the list is undesirable (because it might effect the caller's environment in an unwanted way) in which case use `a = a + something`. – John Coleman Dec 06 '16 at 13:22

score 0 · Answer 2 · answered Dec 06 '16 at 12:22

0

In line

path=path+[start]

you create new list object.

In line

path+=[start]

you modify list object that already exists.

You can try this:

path2=path[:]
path2+=[start]

answered Dec 06 '16 at 12:22

Jaroslaw Matlak

574
1
12
23

Adding to list a class instance

2 Answers2