#OK to post homework
#Joseph Koutsoutis, 04-06-2025, Assignment 18

read `C18.txt`:


#1
#I used parts of hw17 so that this averages based on the least number of edges in a shortest path.
AveLengthSP := proc(G, a) local p:
  add(DijkstrasPathLens(G, a)[2]) / G[1]:
end:


#2
AveLengthStat := proc(n, p, K, M) local i, ave, var, lens:
  lens := [seq(AveLengthSP(RWG(n, p, K), 1), i=1..M)]:
  ave := add(lens) / M:
  var := add((lens[i] - ave)^2, i=1..M) / (M-1):
  evalf(ave), evalf(var):
end:

#I ran AveLengthStat(100, 1/4, 2, 1000) 5 times which returned:

#                  1.741580000, 0.002728031632
#                  1.736190000, 0.002333317217
#                  1.741230000, 0.002623410511
#                  1.737600000, 0.002710150150
#                  1.740070000, 0.002535630731





###Slightly modified code from hw17###

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:

DijkstrasPathLens := proc(G, j) local pq, n, curr, lens, visited, dists, k, l, d, P, M:
  M := ConvertToMatrix(G):
  n := nops(M):
  dists := [seq(infinity, k=1..n)]:
  visited := [seq(0, k=1..n)]:
  dists[j] := 0:
  lens := [seq(infinity, k=1..n)]:
  lens[j] := 0:

  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] or d = dists[l] and lens[l] > lens[curr[2]] + 1 then:
            lens[l] := lens[curr[2]] + 1:
            dists[l] := d:
             priqueue:-insert([-d, l], pq):
          fi:
        fi:
      od:
    fi:
  od:
  return [dists, lens]:
end: