1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
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)
|
