/*
Heath Logan Campbell
hcam630
*/
% six_cities(RoadNetwork) :-
%   [
%     (a, [(b, 5), (f, 6)]),
%     (b, [(a, 5), (e, 1), (c, 4)]),
%     (c, [(b, 4), (f, 9), (d, 2)]),
%     (d, [(e, 3), (c, 2), (f, 7)]),
%     (e, [(b, 1), (d, 2)]),
%     (f, [(a, 6), (c, 6), (d, 7)])
%   ] = RoadNetwork.


% single_cities(SingleState) :-
%   (c, [(b, 4), (f, 9), (d, 2)]) = SingleState.


findEdges(Road, Parent, Edge) :-
   member((EdgeNode, List) , Road),
   member((Parent, Cost), List),
   edge(EdgeNode, Cost) = Edge.

/*
These function will return the smallest of the two
minWeight(edge(a, 1), edge(b, 3), Min)
*/
minWeight(EdgeOne, EdgeTwo, EdgeTwo) :-
  edge(_, Cost) = EdgeOne,
  edge(_, CurCheapestCost) = EdgeTwo,
  Cost >= CurCheapestCost.

minWeight(EdgeOne, EdgeTwo, EdgeOne) :-
  edge(_, Cost) = EdgeOne,
  edge(_, CurCheapestCost) = EdgeTwo,
  Cost < CurCheapestCost.

/*
this function will return the smallest edge in a list

Example:
  smallestWeight([edge(a, 1), edge(b, 2), edge(c, 3)], MinEdge).
*/
smallestWeight([LastItem], LastItem).

smallestWeight([ H | T ], CheapestEdge) :-
  smallestWeight(T, SubCheapestEdge),
  minWeight(H, SubCheapestEdge, CheapestEdge).


findSmallestInEdge(Road, Parent, EdgesList) :-
  findall(X, (findEdges(Road, Parent, X)), EdgesList).

sumUpCost([ edge(Node, Cost) ], Cost).

sumUpCost( [ H | T ], Sum) :-
  sumUpCost( T, SubSum),
  edge(Node, Cost) = H,
  Sum is Cost + SubSum.

h(state(_, []), _, 0).
h(state(X, [X]), _, 0).

% h(state(a, [a]), [a, [(a, [(b, 5), (f, 6)]), (b, [(a, 5), (e, 1), (c, 4)]), (c, [(b, 4), (f, 9), (d, 2)]), (d, [(e, 3), (c, 2), (f, 7)]), (e, [(b, 1), (d, 2)]),(f, [(a, 6), (c, 9), (d, 7)])]], Result).

h(State, Action, HValue) :-
  state(_, UnvisitedNodes) = State,
  findall(CheapestNode, (
    member(Parent, UnvisitedNodes),
    findSmallestInEdge(Action, Parent, EdgeList),
    smallestWeight(EdgeList, CheapestNode))
  , CheapestPaths),
  sumUpCost(CheapestPaths, HValue).