process table generator for Dijkstra's algorithm

dijkstra.py

# 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'))