-
Notifications
You must be signed in to change notification settings - Fork 0
/
path.py
140 lines (119 loc) · 3.41 KB
/
path.py
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
'''
Read in a dictionary of nodes, similar to:
nodes : {
"First" : {
"Second" : 3,
"Third" : 2,
"Fourth" : 4 },
"Second" : {
"Third" : 1,
"Fourth" : 2 },
"Third" : {
"Fourth" : 4 },
"Fourth" : {}
}
This defines each node in the graph,
and each unique weighted path to
other nodes. If the graph is directed,
then these define all the available
paths. If undirected, then the back-paths
will be created before seeking a shortest
path.
Note: debugging lines are commented out,
and produce output beginning with a dash.
Uncomment as required, comment out
for production.
'''
import json
class graphUnknownNodeError(Exception):
pass
class graphNoPathError(Exception):
pass
class graph:
'''
read in and process a graph, and
seek the shortest path between two nodes.
'''
def __init__(self, filename, directed=False):
f = open(filename)
raw = f.read()
f.close()
''' due to a quirk in MobileC, drop
the first character.
'''
self._nodes = json.loads(raw[1:])
if not directed:
for node in self._nodes:
for edge in self._nodes[node]:
self._nodes[edge][node] = self._nodes[node][edge]
def display_graph(self):
'''
display the dictionary holding the
nodes
'''
return f"{self._nodes}"
def shortest_path(self, begin, end):
'''
find the shortest path from
begin to end, using the graph
already defined here
'''
# initialize some accumulators
self._shortest = []
self._shortest_length = None
self._path =[]
self._path_length = 0
# print("-begin search...")
# sanity checks
if begin not in self._nodes:
raise graphUnknownNodeError(f"Node {begin} not defined")
if end not in self._nodes:
raise graphUnknownNodeError(f"Node {end} not defined")
def find_path(self, begin, end):
# print(f"-find_path: {self._path_length}: {self._path}")
# case 1: initial node
if not self._path:
self._path.append(begin)
# print(f"-added beginning: {self._path}")
find_path(self, begin, end)
return
# case 2: at the end node
if self._path[-1] == end:
# print(f"-at end: {self._path_length}: {self._path}")
if self._shortest_length == None or self._shortest_length > self._path_length:
self._shortest = self._path.copy()
self._shortest_length = self._path_length
return
# case 3: the general case
current = self._path[-1]
# print(f"-current: {current}: {self._nodes[current]}")
if self._shortest_length:
if self._path_length >= self._shortest_length:
# print(f"-short at: {self._path_length} {current}")
return
for check in self._nodes[current]:
if check in self._path:
continue
if self._shortest_length:
if self._path_length >= self._shortest_length:
# print(f"-short-circuited at {check}")
return
# print(f"-checking {current}->{check}")
self._path.append(check)
length = self._nodes[current][check]
self._path_length += length
find_path(self, begin, end)
self._path_length -= length
self._path.pop()
return
find_path(self, begin, end)
return (self._shortest_length, self._shortest)
# f = open("path.json")
# data = f.read()
# print(data)
# nodes = json.loads(data[1:])
# print(nodes)
gra = graph("path.json", directed=False)
# print(f"- defined graph: {gra.display_graph()}")
(short_len, short_path) = gra.shortest_path("A", "G")
print(f"shortest = {short_len}, {short_path}")