1

Short version for problem in link -> https://codereview.stackexchange.com/q/227081/207512

Here is a short code snippet for the problem

While coding for 0/1 Knapsack using Branch and Bound in python, I used a queue from the queue module, to store all the nodes ....

The code snippet where the queue is checked to not be empty, and then values are fetched and pushed into the queue as per code.

Here, q = queue.Queue() initialised with an empty node u(-1,0,0, 0) . u2 is an empty node in beginning to store node in every iteration of loop.

while not q.empty():
        u = q.get()
        ............some code ..........
        q.put(u2)
        display_queue(q)
        ..........some code..............

The display_queue is defined as:

def display_queue(que):
  print("\nThe Nodes in queue currently: ")
  for item in list(que.queue):
    print("level:{}, profit:{}, weight:{}, bound:{}".format(item.level, item.profit, item.weight, item.bound))
  print()

The problem:

If q was containing [(0,0,35)] initially. After adding (1,3,70), the queue becomes [(1,3,70),(1,3,70)]. Note: these are random values. Please don't confuse with the data on the output.

Output sample: Assume for some reason the queue is increasing, after suitable computations.

output 1 Output 2 Output 3

I have read the answers of related questions in stack overflow like: Why does adding a new value to list<> overwrite previous values in the list<> but am not able to implement the suggested correction.

When I tried to implement a miniature version of the code, I got everything correct. That is, the same thing(almost) but different outputs!

Another code

marc_s
  • 732,580
  • 175
  • 1,330
  • 1,459
RJ_SU
  • 31
  • 9
  • Added a short probable answer on the extended part of the question, given on top of this question. – RJ_SU Aug 29 '19 at 17:23

1 Answers1

0

It looks like you are taking things out of the queue as fast as you are putting them in. 

while not q.empty():
        u = q.get() #removes item from queue
        ............some code ..........
        q.put(u2) #adds item to queue
        display_queue(q)
        ..........some code..............

When you access the data from a queue with q.get() you are removing that item from the queue. Why the list(que.queue) gives you a list of three items; I'm not sure. If you wanted your items static you could use a list of lists.

q_var = []
q_var.append([0,35,3,92])
q_var.append([0,0,0,75])
q_var.append([1,45,5,75])

or if I understand correctly you could access your queue as you are doing in que.queue without removing an item by not using the get() method.

count = 0
while not q.empty():
        u = list(q.queue)[count]
        ............some code ..........
        q.put(u2) #adds item to queue
        display_queue(q)
        ..........some code..............
        count += 1

This assumes you have already added something to the queue. Either way the issue is get() method see https://docs.python.org/3/library/queue.html?highlight=queue#module-queue

"Queue.get(block=True, timeout=None)¶ Remove and return an item from the queue."

ShayneLoyd
  • 633
  • 1
  • 4
  • 9
  • I realise that a simple list implementation could be easily done. But my intent was to learn queues in python. I figured out a correction to this case which I have posted in the extended link given on top of the post. That method is working with get() itself. Please see latest edit(last output snap) for added confusion. – RJ_SU Aug 29 '19 at 21:51
  • The .get() method removes the returned item from queue. I understand that you are getting three items in q.queue, but if you read the documentation it does not list Queue.queue as it is not intended to be accessed by the end user. I'm not sure why it behaves this way, but you need to read the docs if you truly want to understand how you are supposed to use Queue. On the other site your short implementation does not use the get() method. – ShayneLoyd Sep 01 '19 at 04:19