I have a dictionary where the key is the node and the value is another dictionary. This dictionary has as keys the parent of the node and the cost to reach that node. For example:
nodes = {0: {'cost': 0, 'parent': None}, 1: {'cost': 2, 'parent': 0}, 2: {'cost': 3, 'parent': 0}, 3: {'cost': 6, 'parent': 1}, 4: {'cost': 8, 'parent': 2}}
I want to extract each node in order of cost. First ones of less value. How could I do it?
From each entry in the dictionary, build a 2-tuple whose first member is the value that you want to use as the sorting key. In this case that's the cost attribute from the entry's internal dictionary.
The second member of the tuple will be the entry's key in the original dictionary. Putting this key into the tuple will allow you to reference the entry in the original dictionary after the tuples have passed through the priority queue.
Collect these tuples in a list.
You can do all of the above in one statement:
tuplist = [ (v['cost'], k) for k, v in nodes.items() ]
Then use the heapq module to organise the list of tuples as a minheap:
import heapq
heapq.heapify(tuplist)
Now you can do whatever you want with the minheap. Presumably you'll want to use heapq.heappop() to extract the tuples in ascending order of cost, and then use the key from the extracted tuple to access the corresponding dictionary entry and do something with it. That would look something like this:
while tuplist:
tup = heapq.heappop(tuplist)
key = tup[1]
print key, nodes[key]
which produces:
0 {'cost': 0, 'parent': None}
1 {'cost': 2, 'parent': 0}
2 {'cost': 3, 'parent': 0}
3 {'cost': 6, 'parent': 1}
4 {'cost': 8, 'parent': 2}
There is code below that shows one way to accomplish your goal.
However, depending on your design goal(s), you may want to consider using a different data type other than a dict to store node information. Since the dict won't maintain key-value order, you would have to iterate through the entire dict to make sure you get the lowest cost key.
Consider something like heapq, which is built on a Python list and would give you methods like heappush(heap, item) and heappop(heap)
I want to extract each node in order of cost. First ones of less value. How could I do it?
def get_lowest_cost_node(nodes):
# if there are multiple nodes with the same cost, will return the first one found
# if nodes is empty, will return None
lowest_cost = float('inf') # bigger than any other python number
lowest_cost_node = None
for k, v in nodes.iteritems():
# iteritems() in Python 2.x, items() in Python 3.x
if v['cost'] < lowest_cost:
lowest_cost = v['cost']
lowest_cost_node = k
return lowest_cost_node
e.g.
In : nodes = {0: {'cost': 0, 'parent': None}, 1: {'cost': 2, 'parent': 0}, 2: {'cost': 3,
: 'parent': 0}, 3: {'cost': 6, 'parent': 1}, 4: {'cost': 8, 'parent': 2}}
:
In : get_lowest_cost_node(nodes)
Out: 0
In : nodes2 = {0: {'cost': 10, 'parent': None}, 1: {'cost': 2, 'parent': 0}, 2: {'cost':
...: 3, 'parent': 0}, 3: {'cost': 6, 'parent': 1}, 4: {'cost': 1, 'parent': 2}}
...:
In : get_lowest_cost_node(nodes2)
Out: 4
