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

read `C19.txt`:


#1
EstimateAverageMinCost := proc(n,p,K,N) local ave, i, conn, c:
  ave := 0:
  conn := 0:
  for i from 1 to N do:
    c := MST(RWG(n,p,K)):
    if c <> FAIL then:
      ave += c[2]:
      conn++:
    fi:
  od:
  evalf(conn/N), evalf(ave / conn):
end:


#2
#I changed the error checking in LC(p) to check for rational inputs
#instead of fractions since this did not work for L[a]
EstimateTable := proc(n,N,a,b) local L, i, K:
  for i from 1 to a do:
      for K from 1 to b do:
        L[i,K] := EstimateAverageMinCost(n,i/a,K,N)[2]:
      od:
    od:
  return [seq( [seq(L[i,K], K=1..b)] , i=1..a)]:
end:

#EstimateTable(10,3000,5,10) outputted

#[[9., 12.36783439, 15.99271137, 19.63117284, 23.37419355, 26.90271132, 30.73993808, 34.53506098, 38.66467958, 41.89566613], 
# [9., 10.56038292, 12.93350478, 15.51598513, 18.12666667, 20.63415532, 23.19992636, 26.02773723, 28.62716870, 31.25607959], 
# [9., 9.458096828, 10.82546064, 12.57548430, 14.20882058, 15.91613765, 17.71901103, 19.65127175, 21.56479626, 23.21605351], 
# [9., 9.100333333, 9.746666667, 10.79700000, 12.03766667, 13.37666667, 14.70600000, 15.97966667, 17.17266667, 18.70700000], 
# [9., 9.017666667, 9.303333333, 9.957666667, 10.85200000, 11.76600000, 12.82433333, 13.80933333, 14.89966667, 16.03300000]]


#4
EulerianPath := proc(G) local n,E,v,i,e,P,num_nontriv_components,c,C,visited,N,moved:
  c := 0:
  n:=G[1]:
  E:=G[2]:
  visited := {}:

  for i from 1 to n do:
    if not i in visited then:
      C := CC(G, i):
      visited := visited union C:
      if nops(C) > 1 then:
        c++:
      fi:
    fi:
  od:

  #Check that we only have at most one component that is not an isolated vertex
  if c > 1 then return FAIL: fi:

  N := [{}$n]:
  for e in E do
    N[e[1]]:=N[e[1]] union {e[2]}:
    N[e[2]]:=N[e[2]] union {e[1]}:
  od:


  #Check the degrees are even
  for i in N do:
    if nops(i) mod 2 <> 0 then:
      return FAIL:
    fi:
  od:

  P := []:
  v := max[index]([seq(nops(i), i in N)]):

  while N[v] <> {} do:
    P := [op(P), v]:
    c := nops(CC([n,E], v)):
    moved := 0:
    for i in N[v] do:
      if moved=0 and nops(CC([n,E minus {i,v}], v)) = c then:
        i := N[v][1]:
        E := E minus {{i,v}}:
        N[v] := N[v] minus {i}:
        N[i] := N[i] minus {v}:
        v := i:
        moved := 1:
      fi:
    od:
    if moved = 0 then:
      i := N[v][1]:
      E := E minus {{i,v}}:
      N[v] := N[v] minus {i}:
      N[i] := N[i] minus {v}:
      v := i:
    fi:
  od:

  [op(P), v]:
end: