import unittest
from collections import deque
from heapq import heappush, heappop
################################################################################
# InterviewCake.com
################################################################################
# construct_path :: Map String String -> String -> String -> [String]
def construct_path(paths, beg, end):
"""
Reconstruct the path from `beg` to `end`.
"""
result = []
current = end
print(paths)
print(beg, end)
print('-----')
while current:
result.append(current)
current = paths[current]
result.reverse()
return result
def get_path_ic(graph, beg, end):
"""
InterviewCake uses a dictionary and back-tracking to store and reconstruct
the path instead of storing the path as state on each node.
This reduces the memory costs. See get_path_bft for an example of this less
optimal solution.
"""
if beg not in graph:
raise Exception('Origin node absent from graph.')
if end not in graph:
raise Exception('Destination node absent from graph.')
q = deque()
q.append(beg)
paths = {beg: None}
while q:
node = q.popleft()
if node == end:
print(graph)
return construct_path(paths, beg, end)
for x in graph[node]:
if x not in paths:
paths[x] = node
q.append(x)
return None
################################################################################
# Per-node state
################################################################################
def get_path_bft(graph, beg, end):
"""
Here we find the shortest path from `beg` to `end` in `graph` by doing a BFT
from beg to end and storing the path state alongside each node in the queue.
"""
if beg not in graph:
raise Exception('Origin node absent from graph.')
if end not in graph:
raise Exception('Destination node absent from graph.')
q = deque()
seen = set()
q.append([beg])
while q:
path = q.popleft()
node = path[-1]
seen.add(node)
if node == end:
return path
for x in graph[node]:
if x not in seen:
q.append(path + [x])
################################################################################
# Dijkstra's Algorithm
################################################################################
def get_path(graph, beg, end):
"""
Here we find the shortest path using Dijkstra's algorithm, which is my
favorite solution.
"""
if beg not in graph:
raise Exception(
'The origin node, {}, is not present in the graph'.format(beg))
if end not in graph:
raise Exception(
'The origin node, {}, is not present in the graph'.format(end))
q = []
seen = set()
heappush(q, (1, [beg]))
while q:
weight, path = heappop(q)
node = path[-1]
seen.add(node)
if node == end:
return path
for x in graph[node]:
if x not in seen:
heappush(q, (weight + 1, path + [x]))
return None
# Tests
class Test(unittest.TestCase):
def setUp(self):
self.graph = {
'a': ['b', 'c', 'd'],
'b': ['a', 'd'],
'c': ['a', 'e'],
'd': ['b', 'a'],
'e': ['c'],
'f': ['g'],
'g': ['f'],
}
def test_two_hop_path_1(self):
actual = get_path(self.graph, 'a', 'e')
expected = ['a', 'c', 'e']
self.assertEqual(actual, expected)
def test_two_hop_path_2(self):
actual = get_path(self.graph, 'd', 'c')
expected = ['d', 'a', 'c']
self.assertEqual(actual, expected)
def test_one_hop_path_1(self):
actual = get_path(self.graph, 'a', 'c')
expected = ['a', 'c']
self.assertEqual(actual, expected)
def test_one_hop_path_2(self):
actual = get_path(self.graph, 'f', 'g')
expected = ['f', 'g']
self.assertEqual(actual, expected)
def test_one_hop_path_3(self):
actual = get_path(self.graph, 'g', 'f')
expected = ['g', 'f']
self.assertEqual(actual, expected)
def test_zero_hop_path(self):
actual = get_path(self.graph, 'a', 'a')
expected = ['a']
self.assertEqual(actual, expected)
def test_no_path(self):
actual = get_path(self.graph, 'a', 'f')
expected = None
self.assertEqual(actual, expected)
def test_start_node_not_present(self):
with self.assertRaises(Exception):
get_path(self.graph, 'h', 'a')
def test_end_node_not_present(self):
with self.assertRaises(Exception):
get_path(self.graph, 'a', 'h')
unittest.main(verbosity=2)
