Skip to content

Instantly share code, notes, and snippets.

@bivoje
Created June 2, 2019 10:59
Show Gist options
  • Save bivoje/db2d2e4e94081b5eec822a3f2928c498 to your computer and use it in GitHub Desktop.
Save bivoje/db2d2e4e94081b5eec822a3f2928c498 to your computer and use it in GitHub Desktop.
process table generator for Dijkstra's algorithm
# code for calculating solution for 3rd case of exerciseno.5 of setion 10.6 from the book Discrete Mathematics and Its Applications 7th ed.
# can be used for general dijkstra solver
def show_graph_entry(ls):
return "[" + " ".join(map(lambda u: f'{ls[u]}-{chr(u+ord("a"))}', ls)) + "]"
def show_graph_it(graph):
for v in graph:
yield f'{chr(v+ord("a"))}: {show_graph_entry(graph[v])}'
def show_graph(graph):
return "\n".join(show_graph_it(graph))
def read_graph_edge(pair):
w, u = pair.split('-')
return int(w), ord(u)-ord('a')
def read_graph_entry(line):
v, ls = line.split(':')
v, ls = ord(v)-ord('a'), ls[2:-1]
edges = {}
for pair in ls.split():
w, u = read_graph_edge(pair)
edges[u] = w
return v, edges
def read_graph(lines):
graph = {}
for line in lines.split("\n"):
if line == "": continue
v, es = read_graph_entry(line)
graph[v] = es
return graph
def get_sym_graph(n):
halt = False
graph = {}
for v in range(0,n):
graph[v] = {}
for v in range(0,n):
if halt: break
while True:
print(f'vertex {chr(v+ord("a"))}: ', end="")
line = input()
if line == "":
continue
if line[0] == "p":
print(show_graph(graph))
continue
if line[0] == "n":
break
if line[0] == "q":
halt = True
break
if line[0] == "r":
graph[v] = {}
print("[]")
continue
w, u = line.split()
w, u = int(w), ord(u)
graph[v][u] = w
print(show_graph_entry(graph[v]))
# ended inserting for vertex v.
# symmetr-ize
for u in graph[v]:
graph[u][v] = graph[v][u]
return graph
class PathStone:
def __init__(self):
self.w = None
self.through = None
self.confirmed = False
def __repr__(self):
return str({'w':self.w, 't':self.through, 'c':self.confirmed})
def __str__(self):
if self.w is None:
return "-"
if self.confirmed:
return "|"
return self.show()
def show(self):
s = '.'
if self.through is not None:
s = str(chr(self.through+ord("a")))
return str(self.w) + s
def lt_inft(a, b):
if not a: return False
if not b: return True
return a < b
def minstone_idx(stones):
u = None
for v in range(0, len(stones)):
if stones[v].confirmed: continue
if not u: u = v
if lt_inft(stones[v].w, stones[u].w): u = v
return u
def dijkstra(graph, s, e):
n = len(graph)
stones = []
for _ in range(0,n):
stones.append(PathStone())
stones[s].w = 0
stones[s].through = None
stones[s].confirmed = True
v = s
stones_acc = []
print(" | " + ' '.join(map(lambda x: chr(x+ord('a')).rjust(3), range(0, n))))
while v is not None:
stones[v].confirmed = True
for u,w in graph[v].items():
if stones[u].confirmed: continue
if lt_inft(stones[u].w, stones[v].w + w):
continue
#print(f'updating {u}')
stones[u].w = stones[v].w + w
stones[u].through = v
ls = list(map(lambda x: str(x).rjust(3), stones))
ls[v] = ' '*(3-len(stones[v].show())) + f'\x1b[1;4;31m{stones[v].show()}\x1b[0m'
print(f'{chr(v+ord("a")).rjust(2)}| {" ".join(ls)}')
v = minstone_idx(stones)
#graph = get_sym_graph(range(ord('a'), ord('t')+2))
graph = read_graph("""
a: [2-b 4-c 1-d]
b: [2-a 3-c 1-e]
c: [4-a 3-b 2-e 2-f]
d: [1-a 5-f 4-g]
e: [1-b 2-c 3-h]
f: [2-c 5-d 3-h 2-i 4-j 3-g]
g: [4-d 3-f 2-k]
h: [3-e 3-f 8-o 1-l]
i: [2-f 3-l 2-m 3-j]
j: [4-f 3-i 6-m 3-n 6-k]
k: [2-g 6-j 4-n 2-r]
o: [8-h 6-l 4-m 6-s 2-p]
l: [1-h 3-i 6-o 3-m]
m: [2-i 6-j 3-l 4-o 2-p 5-n]
n: [3-j 4-k 5-m 2-q 1-r]
r: [2-k 1-n 8-q 5-t]
p: [2-m 2-o 2-s 1-t 1-q]
q: [2-n 1-p 3-t 8-r]
s: [6-o 2-p 2-u]
t: [1-p 3-q 5-r 8-u]
u: [2-s 8-t]
""")
dijkstra(graph,0, ord('u')-ord('a'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment