Python - Multiple if statement get ignored

Question

I'm implementing BFS on a 2D-array with a list serve as "queue". I add each unvisited neighbor of current cell(i, j) to the queue, and in each loop, pop the head of the queue as the current cell, until the queue is empty. Standard stuff.

The problem seems that only one "if" statement is executed in each loop. I can't see why it happens.

for tgroup in targets.keys(): #group of targets
    for t in targets[tgroup]: #each target in group
        visited = [[False]*len(cells[0])]*len(cells)
        queue = []
        cur = None
        queue.append(t)
        visited[t[0]][t[1]] = True
        cells[t[0]][t[1]].fields[tgroup-3] = 0
        while len(queue) > 0:
            cur = queue[0]
            queue = queue[1:]

            if cur[0] > 0 and visited[cur[0]-1][cur[1]] is False:
                queue.append((cur[0]-1,cur[1]))
                visited[cur[0]-1][cur[1]] = True
                cells[cur[0]-1][cur[1]].fields[tgroup-3] = min(cells[cur[0]-1][cur[1]].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 't', cur

            if cur[0] < len(cells)-1 and visited[cur[0]+1][cur[1]] is False:
                queue.append((cur[0]+1,cur[1]))
                visited[cur[0]+1][cur[1]] = True
                cells[cur[0]+1][cur[1]].fields[tgroup-3] = min(cells[cur[0]+1][cur[1]].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 'b', cur

            if cur[1] > 0 and visited[cur[0]][cur[1]-1] is False:
                queue.append((cur[0],cur[1]-1))
                visited[cur[0]][cur[1]-1] = True
                cells[cur[0]][cur[1]-1].fields[tgroup-3] = min(cells[cur[0]][cur[1]-1].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 'l', cur

            if cur[1] < len(cells[0])-1 and visited[cur[0]][cur[1]+1] is False:
                queue.append((cur[0],cur[1]+1))
                visited[cur[0]][cur[1]+1] = True
                cells[cur[0]][cur[1]+1].fields[tgroup-3] = min(cells[cur[0]][cur[1]+1].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 'r', cur

            if cur[0] > 0 and cur[1] > 0 and visited[cur[0]-1][cur[1]-1] is False:
                queue.append((cur[0]-1,cur[1]-1))
                visited[cur[0]-1][cur[1]-1] = True
                cells[cur[0]-1][cur[1]-1].fields[tgroup-3] = min(cells[cur[0]-1][cur[1]-1].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 'tl', cur

            if cur[0] > 0 and cur[1] < len(cells[0])-1 and visited[cur[0]-1][cur[1]+1] is False:
                queue.append((cur[0]-1,cur[1]+1))
                visited[cur[0]-1][cur[1]+1] = True
                cells[cur[0]-1][cur[1]+1].fields[tgroup-3] = min(cells[cur[0]-1][cur[1]+1].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 'tr', cur

            if cur[0] < len(cells)-1 and cur[1] > 0 and visited[cur[0]+1][cur[1]-1] is False:
                queue.append((cur[0]+1,cur[1]-1))
                visited[cur[0]+1][cur[1]-1] = True
                cells[cur[0]+1][cur[1]-1].fields[tgroup-3] = min(cells[cur[0]+1][cur[1]-1].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 'bl', cur

            if cur[0] < len(cells)-1 and cur[1] < len(cells[0])-1 and visited[cur[0]+1][cur[1]+1] is False:
                queue.append((cur[0]+1,cur[1]+1))
                visited[cur[0]+1][cur[1]+1] = True
                cells[cur[0]+1][cur[1]+1].fields[tgroup-3] = min(cells[cur[0]+1][cur[1]+1].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 'br', cur

targets are the starting coordinates of this algorithm. I need to traverse the entire map to fill out some 'floor field' to find the shortest path from each location of the map to these targets. Each t in target is stored as a tuple (i,j)

visited are the markers for visited nodes.

cur is the current node, stored as a tuple (i,j).

cells is the 2D-array. Each cell has a list attribute .fields containing "floor field" weight for each target, representing the distance from this cell to the target. The weight of non-target cells are default to 9, for now, for simplicity. The weight for the targets are default to 0.

Here's a sample 9*9 input map:

4 1 1 1 1 1 1 1 1
0 1 1 0 0 0 0 1 0
0 1 1 1 1 2 0 1 0
0 1 1 1 1 2 0 1 0
0 1 1 0 0 0 0 1 0
3 1 1 0 0 0 1 1 0
3 1 1 0 0 0 1 1 0
0 1 1 0 0 0 1 0 0
0 5 5 5 0 0 1 0 0

But the floor field generated for the target represented as number 3 is:

9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9

It doesn't traverse all nodes.

Update:

It works when I replaced

visited = [[False]*len(cells[0])]*len(cells)

with

visited = [[False for x in range(len(cells[0]))] for y in range(len(cells))]

Can someone explain the difference? Thanks a lot!

For one, don't use `is False`, just do `not visited[cur[0]-1][cur[1]]`, for example. — Wayne Werner, Feb 03 '16 at 03:10
Is only one if statement checked and then it prematurely moves to the next iteration (might be an indentation problem), or are all if statements checked but only the first is matched? — Peter Gibson, Feb 03 '16 at 03:13
Guys, I think it's a matter of how I generate the `visited` list. Immediately after each update of `cur`, when I `print visited[cur[0]-1][cur[1]]` it alway outputs `True`, which is weird. — Fenwick, Feb 03 '16 at 03:23
@AustinHastings basically I group targets in the `targets` dictionary. `tgroup` are integers as dictionary keys. In the value of each `tgroup` are the targets represented by the same number, say `3`, in the input map. `3` is the smallest number to represent a target. So `tgroup-3` is basically the index of the `tgroup` in the `fields` list. I don't think these have anything to do with the BFS. — Fenwick, Feb 03 '16 at 03:27
Hi, can anyone look at the update section and explain what's going on? Both methods seem to generate the same 2d array, but act differently. THanks! — Fenwick, Feb 03 '16 at 03:45
http://stackoverflow.com/questions/240178/python-list-of-lists-changes-reflected-across-sublists-unexpectedly — Lafexlos, Feb 03 '16 at 03:52

Lafexlos · Accepted Answer · 2016-02-03T03:58:36.150

1

After your first call

visited = [[False]*len(cells[0])]*len(cells)

visited contains len(cells) number of lists which are essentially same (they all reference to one list). So when you change a value in there, everyone of those gets changed since they are same.

>>>a = [[False]*4]*4
>>>a[0][0] = True
>>>a
>>>[[True, False, False, False],
   [True, False, False, False],
   [True, False, False, False],
   [True, False, False, False]]

>>> for x in a: print id(x)
>>> 135345096
    135345096
    135345096
    135345096

On your second call, you create seperate lists. So when you change one, the value only changed in it.

edited Feb 03 '16 at 03:58

answered Feb 03 '16 at 03:48

Lafexlos

7,618
5
38
53

Thanks! Just curious, what's the point of allowing the first call kind of syntax then? Multithreading? – Fenwick Feb 03 '16 at 04:07
You might want to change multiple values at once, for those cases this might be useful but I am not sure. There are most likely more cases, which I can't think of right now, that is useful. – Lafexlos Feb 03 '16 at 04:11
1

https://docs.python.org/2/faq/programming.html#how-do-i-create-a-multidimensional-list – Lafexlos Feb 03 '16 at 04:12

Python - Multiple if statement get ignored

1 Answers1