# Get a path between graph nodes using breadth-first search

This code is meant to implement a Graph class which has a method that returns a path between 2 nodes using breadth-first search.

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

from queue import PriorityQueue
from collections import deque
from copy import deepcopy

class Graph:
def __init__(self):
self.nodes = dict()

new_node = Node(id)
self.nodes[id] = new_node
return new_node

def get_node(self, id):
node = self.nodes[id] if id in self.nodes else None
return node

def bfs(self, start, end):
queue = PriorityQueue()
queue.put((0, start))
seen = set([start])
parents = dict()

while not queue.empty():
cur_node = queue.get(0)
if cur_node is not end:
for neighbour in cur_node.neighbours:
if neighbour not in seen:
dist_to_neighbour = cur_node.neighbours[neighbour]
queue.put((dist_to_neighbour, neighbour))
parents[neighbour] = cur_node
else:
path = self.get_path(start, end, parents)
return path
return None

def get_path(self, start, end, parents):
path = deque([end])
cur_node = end
while cur_node is not start:
cur_node = parents[cur_node]
path.appendleft(cur_node)
return list(path)

class Node:
def __init__(self, id):
self.id = id
self.neighbours = dict()

self.neighbours[to] = weight


I have a few ideas about what might be improved but I'm not sure how to do it (or even if it's worth doing).

1. There might be a better way to do get_node() instead of squashing it into 2 lines like how I've done it.
2. Maybe cur_node = queue.get(0) should be 2 lines?
3. Change dist_to_neighbour = cur_node.neighbours[neighbour] to use a method instead of using dictionary notation (which might be a little awkward). Maybe I should have a method instead?
4. Using something else instead of a deque in get_path() (especially in an interview context where deque might be a bit too exotic).

Here is my previous attempt at this code. I've also used the answers to my depth-first search attempts here and here to write this code.

I don't see that you are using add_node or get_node anywhere, but I'm assuming you would when actually using this class.

Nevertheless, I think these functions would better be called __setitem__ and __getitem__, allowing usage, such as g = Graph(); g = Node(5) and print g. This would also make initializing the graph easier, which leads me to my next recommendation.

I would expect the Graph class to take an argument on initialization to directly build a graph (without having to manually add every single node).

Lastly, get_node can be greatly simplified by using dict.get, which returns None when the key is not present in the dictionary.

class Graph:
def __init__(self, nodes=None):
self.nodes = dict()
if nodes is not None:
for _id in nodes:
self[_id] = Node(_id)

def __setitem__(self, _id, val):
self.nodes[_id] = val

def __getitem__(self, _id):
return self.nodes.get(_id)

self[_id] = Node(_id)

...


This allows initializing an instance like this: Graph([1,2,3]). It does not, however, allow initializing a nested structure.

1. Use dict.get
2. I would maybe use _, cur_node = queue.get(0) to make it clearer that you don't need the priority here.
3. I think it is still quite readable.
4. deque does not seem too exotic to me, but then again, I don't perform job interviews, so who know.

Last but not least, I would have a look at whether you really need queue.PriorityQueue here. One of its features is that it is thread-safe, because it performs locking when adding or popping values from the queue. However, it also incurs a performance hit because of this (I saw a factor 2 being discussed for Python 2.6).

Instead you could roll your own implementation using heapq, similar to the one shown in the implementation details for heapq, maybe without the part about REMOVED entries, because you don't change the priority of a neighbour once you have calculated it. So you could use:

from heapq import heappush, heappop
import itertools

class PriorityQueue:
'''A new PriorityQueue.
Parameters:
self.pq = []                         # list of entries arranged in a heap
self.counter = itertools.count()     # unique sequence count

count = next(self.counter)

This should basically be how queue.PriorityQueue is implemented as well, but without the locking. Note that heapq is implemented in C, so it is quite fast. You would have to make some performance comparisons to see how this performs with respect to queue.PriorityQueue.
• Thanks for the answer. Using __setitem__ and __getitem__ definitely make it nicer. Being able to initialise a graph with a list makes sense. Your answers to my thoughts were quite helpful. Also, your section about using heapq due to performance was very interesting. I learned a lot of new interesting stuff from that. Thanks :) Nov 23 '16 at 6:07