% P84 (**) Construct the minimal spanning tree of a labelled graph 

% ms_tree(G,T,S) :- T is a minimal spanning tree of the graph G.
%    S is the sum of the edge values. Prim's algorithm.
%    (graph-term graph-term) (+,?)

:- ensure_loaded(p80).  % conversions
:- ensure_loaded(p83).  % transfer/3, incident/3, and accept/3

ms_tree(graph([N|Ns],GraphEdges),graph([N|Ns],TreeEdges),Sum) :- 
   predsort(compare_edge_values,GraphEdges,GraphEdgesSorted),
   transfer(Ns,GraphEdgesSorted,TreeEdgesUnsorted),
   sort(TreeEdgesUnsorted,TreeEdges),
   edge_sum(TreeEdges,Sum).

compare_edge_values(Order,e(X1,Y1,V1),e(X2,Y2,V2)) :- 
	compare(Order,V1+X1+Y1,V2+X2+Y2).

edge_sum([],0).
edge_sum([e(_,_,V)|Es],S) :- edge_sum(Es,S1), S is S1 + V. 

% Example graph p84.dat

test :-  
   see('p84.dat'), read(G), seen,
   human_gterm(H,G),
   write(H), nl, 
   ms_tree(G,T,S),
	human_gterm(TH,T),
   write(S), nl,
	write(TH).