#OK to post homework
#Joseph Koutsoutis, 03-30-2025, Assignment 17

read `C17.txt`:
read `C2.txt`:
with(numtheory):

#1

MyOrd := proc(x, n) local r, L:
  L := sort(convert(divisors(phi(n)), list)):
  for r in L do:
    if x^r mod n = 1 then:
      return r:
    fi:
  od:
end:


#2

RWG_old := proc(n, K) local M, i, j, ra:
  ra := rand(0..K):
  for i from 1 to n do:
    for j from 1 to n do:
      if i = j then:
        M[i,j] := 0:
      else:
        M[i,j] := ra():
      fi:
    od:
  od:
  [seq([seq(M[i,j], j=1..n)], i=1..n)]:
end:

RWG := proc(n, p, K) local ra, T, E, e:
  ra := rand(1..K):
  E := RG(n, p)[2]:
  for e in E do:
    T[e] := ra():
  od:
  [n, E, op(T)]:
end:


#3


#This is for graphs generated by RWG_old, which was based on question 2 
#before it was updated on March 29.
Dijkstras_old := proc(M, j, i) local pq, n, curr, prev, visited, dists, k, l, d, P:
  n := nops(M):
  dists := [seq(infinity, k=1..n)]:
  prev := [seq(0, k=1..n)]:
  visited := [seq(0, k=1..n)]:
  dists[j] := 0:
  prev[j] := j: 

  priqueue:-initialize(pq):
  priqueue:-insert([0, j], pq):

  while pq[0] <> 0 do: 
    curr := priqueue:-extract(pq):
    if visited[curr[2]] <> 1 then:
      visited[curr[2]] := 1:
      for l from 1 to n do:
        if l <> curr[2] and visited[l] <> 1 then:
          d := -curr[1] + M[curr[2], l]: 
          if d < dists[l] then:
            prev[l] := curr[2]:
            dists[l] := d:
             priqueue:-insert([-d, l], pq):
          fi:
        fi:
      od:
    fi:
  od:
  if dists[i] = infinity then:
    return [infinity, []]:
  fi:
  P := []:
  k := i:
  while prev[k] <> k do:
    P := [k, op(P)]:
    k := prev[k]:
  od:
  [dists[i], [j, op(P)]]:
end:


BruteForceAPSP_old := proc(M) local i, j, A, n, Paths, d, P:
  n := nops(M):
  for i from 1 to n do:
    for j from 1 to n do:
      if i <> j then:
        A[i,j] := infinity:
      else:
        A[i,j] := 0:
      fi:
    od:
  od:
  
  Paths := [seq([0, [i]], i=1..n)]:
  while Paths <> [] do:
    d, P := op(Paths[-1]):
    i := P[-1]:
    Paths := Paths[1..-2]:
    for j from 1 to n do:
      if not j in P then:
        if d + M[i][j] < A[P[1], j] then:
          A[P[1], j] := d + M[i][j]:
          Paths := [op(Paths), [d + M[i][j], [op(P), j]]]:
        fi:
      fi:
    od:
  od:
  [seq([seq(A[i,j], j=1..n)], i=1..n)]:
end:


TestDijkstras_old := proc() local M, A, B, i, j:
  M := RWG_old(10, 20):
  A := [seq([seq(Dijkstras_old(M, i, j)[1], j=1..10)], i=1..10)]:
  B := BruteForceAPSP_old(M):
  evalb(A = B):
end:


ConvertToMatrix := proc(G) local n, E, T, i, j, A:
  n, E, T := op(G):
  for i from 1 to n do:
    for j from 1 to n do:
      if i = j then:
        A[i,j] := 0:
      elif {i,j} in E then:
        A[i,j] := T[{i,j}]:
      else:
        A[i,j] := infinity:
      fi:
    od:
  od:
  [seq([seq(A[i,j], j=1..n)], i=1..n)]:
end:


TestDijkstras := proc(p) local M, A, B, i, j:
  M := ConvertToMatrix(RWG(10, p, 20)):
  A := [seq([seq(Dijkstras_old(M, i, j)[1], j=1..10)], i=1..10)]:
  B := BruteForceAPSP_old(M):
  evalb(A = B):
end: