(*Excercise 1: Write a module called dataToMatrix that reads in graph data (an example of which is located in the graph.txt file on Moodle) and builds a distance matrix,Q.Hint:If two points are not connected you should assign infinite distance.*)
dataToMatrix[filePath_String]:=Module[{data,lines,connections,maxNode,matrix,i,j,k,destinationNode},(*Define local variables*)
data=Import[filePath,"Plaintext"];(*Import file as plain text*)
If[data===$Failed,Return["File import failed. Please check the file path or format."]];(*Check if import was successful*)
lines=StringSplit[data,"\n"];(*Split the contents of the file into lines*)
(*Process each line into {source,destination,weight} format*)
connections={};
For[i=1,i<=Length[lines],i++,(*Iterate over each line in'lines'*)
Module[{elements,sourceNode,edges},(*Define local variables for the loop*)
elements=StringSplit[lines[[i]],", "];(*Split the line into parts based on ", "*)
sourceNode=Quiet[ToExpression[StringDelete[elements[[1]],"node"]]];(*Extract and convert the source node,removing the "node" prefix*)
If[Head[sourceNode]=!=Integer,Continue[]];(*Skip if sourceNode is not a valid integer*)
For[j=2,j<=Length[elements],j++,(*Iterate over remaining elements,starting from the 2nd one*)
Module[{destNode,weight},(*Define local variables for the loop*)
If[!StringContainsQ[elements[[j]]," "],Continue[]];(*Skip if there is no space between destination node and weight*)
{destNode,weight}=StringSplit[elements[[j]]," "];(*Split element into destination node and weight*)
(*Append the connection with parsed source,destination,and weight to'connections' list*)
AppendTo[connections,{sourceNode,Quiet[ToExpression[StringDelete[destNode,"node"]]],Quiet[ToExpression[weight]]}];]];]];
maxNode=Max[Flatten[connections[[All,{1,2}]]]];(*Find the maximum node index to determine matrix size*)
destinationNode=maxNode;(*Assume last node is the destination node*)
(*Initialize an (maxNode+1) x (maxNode+1) matrix with Infinity*)
matrix=ConstantArray[Infinity,{maxNode+1,maxNode+1}];
(*Set diagonal elements to Infinity,except for the destination node*)
For[i=0,i<=maxNode,i++,matrix[[i+1,i+1]]=If[i==destinationNode,0,Infinity];];
(*Populate the matrix with connection weights*)
For[k=1,k<=Length[connections],k++,(*Iterate over each entry in connections*)
Module[{source,dest,weight},(*Define local variables for the loop*)
{source,dest,weight}=connections[[k]];(*Extract source,destination,and weight values from the connections list for the current k*)
matrix[[source+1,dest+1]]=weight;]];(*Set the weight in the matrix for the edge from 'source' to 'dest'. Add 1 to account for 1-based indexing*)
Q=MatrixForm[matrix](*Return matrix*)]

(*Excercise 2: Write a “Bellman operator” module called bellmanIteration that takes a
distance matrix,Q,and current guess of the ‘cost to go’ function Jn and returns an
updated guess,Jn+1 using the algorithm in section 37.4.1 on the website.Hint:It’s
easiest to implement Jn as a vector.For example if Jn={2,5,1,2,0,3},then each
entry is interpreted as the’cost to go’ at a node(i.e.Jn[[1]]=2,Jn[[2]]=5 etc)*)
(*Bellman operator module*)
bellmanIteration[Q_,Jn_List]:=Module[{numNodes,nextJ,Qlist},
numNodes=Length[Q[[1]]];(*Number of nodes from length of Q*)
Qlist=Q[[1]];(*Convert matrix Q into list of lists*)
(*Compute next cost-to-go function,skipping Infinity entries*)
(*For each node v,compute the minimum cost-to-go for reaching other nodes*)
(*Check if the current edge has an infinite weight (no connection)*)
(*If there's no connection,keep the cost as Infinity*)
(*Otherwise,add the edge cost to Jn at node w*)
(*Loop through all possible destination nodes w*)
(*Loop through all nodes v to compute their minimum cost-to-go*)
nextJ=Table[Min[Table[If[Qlist[[v+1,w+1]]===Infinity,Infinity,Qlist[[v+1,w+1]]+Jn[[w+1]]],{w,0,numNodes-1}]],{v,0,numNodes-1}];
nextJ](*Return the updated cost-to-go function nextJ*)

(*Excercise 3: Write a module findCostToGo that takes a distance matrix,Q,and iterates
the corresponding “Bellman operator” module written above until a final cost-to-go
function (i.e.J) is found.Hint:As before,J should be a vector!*)
(*Allow user to enter maximum iterations and desired tolerance however have default values set if nothing is inputed*)
(*Cost-to-go module with handling for Infinity values*)
findCostToGo[Q_,maxIter_Integer:500,tol_:10^-6]:=Module[{numNodes,Jn,nextJn,finiteJn,finiteNextJn,i},
numNodes=Length[Q[[1]]];(*Determine number of nodes from the length of Q*)
Jn=ConstantArray[0,numNodes];(*Initial vector Jn filled with zeros*)
For[i=1,i<=maxIter,i++,
nextJn=bellmanIteration[Q,Jn];(*Compute next cost-to-go vector*)
finiteJn=Select[NumericQ]@*DeleteCases[Infinity]@*Jn;
finiteNextJn=Select[NumericQ]@*DeleteCases[Infinity]@*nextJn;(*Remove infinity elements for comparison*)
If[Norm[finiteNextJn-finiteJn,Infinity]<tol,Break[]];(*Check if the norm of the difference is within tolerance*)
Jn=nextJn(*Update Jn for the next iteration*);];
J=Jn (*Return the final cost-to-go function*)]

(*Excercise 4: Write a module findPathAndTotalCost that takes a distance matrix,Q and
a cost-to-go function J and uses them to find the optimal (cheapest) path from start
to end and its cost.Test your code on the data in the graph.txt file by showing the
optimal path and finding its minimum cost.Hint:Your findPathAndTotalCost should
of course make use of the findCostToGo module.*)
(*Allow user to enter start node however have default value set to 0 if nothing is inputed*)
findPathAndTotalCost[Q_,J_List,startNode_Integer:0]:=Module[{path,currentNode,totalCost,numNodes,nextNode,Qlist},(*Define local variables*)
(*Initialize the path and cost*)
path={startNode};
totalCost=0;
numNodes=Length[J];(*Get number of nodes from the length of J*)
currentNode=startNode;(*Set current node to startNode*)
Qlist=Q[[1]];  (*Change matrix Q into list of lists for calculations*)
(*Traverse the graph based on the cost-to-go function J*)
While[currentNode!=numNodes-1,
(*Find the next node that minimizes the cost-to-go function*)
nextNode=First[Ordering[Table[Qlist[[currentNode+1,w+1]]+J[[w+1]],{w,0,numNodes-1}],1]]-1;
totalCost+=Qlist[[currentNode+1,nextNode+1]];(*Update total cost by adding the cost to the next node*)
AppendTo[path,nextNode];(*Append the next node to the path*)
currentNode=nextNode;];(*Move to the next node*)
(*Return the path and total cost*)
Print["Optimal Path: ",path];
Print["Minimum Cost: ",totalCost];]

dataToMatrix["/Users/janwejchert/Library/CloudStorage/OneDrive-UniversityofStAndrews/nodesProject.docx"];(*Input your data file here*)
bellmanIteration[Q,ConstantArray[0,Length[Q[[1]]]]];
findCostToGo[Q];
findPathAndTotalCost[Q,J,17]