This code is meant to implement a Graph
class which has a method that returns a path between 2 nodes using depth-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 copy import deepcopy
class Graph:
def __init__(self):
self.verts = set()
def add_vert(self, id):
new_vert = Vertex(id)
self.verts.add(new_vert)
return new_vert
def get_vert(self, id):
for vert in self.verts:
if vert.id == id:
return vert
return None
def dfs(self, start, end):
path_stack = []
visited = set()
path_stack.append([start])
while path_stack:
cur_path = path_stack.pop()
last = cur_path[-1]
visited.add(last)
if last != end:
path_stack = self.push_paths_in_order(path_stack, cur_path, visited)
else:
return cur_path
return None
def push_paths_in_order(self, path_stack, cur_path, visited):
last = cur_path[-1]
queue = PriorityQueue()
for neighbour in last.neighbours:
if neighbour not in visited:
# make queue like max heap so that we can push
# paths to path_stack in increasing order
dist_to_neighbour = last.neighbours[neighbour] * -1
queue.put((dist_to_neighbour, neighbour))
while not queue.empty():
new_path = deepcopy(cur_path)
next_vert = queue.get(0)[1]
new_path.append(next_vert)
path_stack.append(new_path)
return path_stack
class Vertex:
def __init__(self, id):
self.id = id
self.neighbours = dict()
def add_neighbour(self, to, weight):
self.neighbours[to] = weight
Node
would be a better name forVertex
? \$\endgroup\$Node
from now on to minimise the chance someone might be a bit confused. \$\endgroup\$