% P83 (**) Construct all spanning trees 

% s_tree(G,T) :- T is a spanning tree of the graph G
%    (graph-term graph-term) (+,?)

:- ensure_loaded(p80).  % conversions

s_tree(graph([N|Ns],GraphEdges),graph([N|Ns],TreeEdges)) :- 
   transfer(Ns,GraphEdges,TreeEdgesUnsorted),
   sort(TreeEdgesUnsorted,TreeEdges).

% transfer(Ns,GEs,TEs) :- transfer edges from GEs (graph edges)
%    to TEs (tree edges) until the list NS of still unconnected tree nodes
%    becomes empty. An edge is accepted if and only if one end-point is 
%    already connected to the tree and the other is not.

transfer([],_,[]).
transfer(Ns,GEs,[GE|TEs]) :- 
   select(GE,GEs,GEs1),        % modified 15-May-2001
   incident(GE,X,Y),
   acceptable(X,Y,Ns),
   delete(Ns,X,Ns1),
   delete(Ns1,Y,Ns2),
   transfer(Ns2,GEs1,TEs).

incident(e(X,Y),X,Y).
incident(e(X,Y,_),X,Y).

acceptable(X,Y,Ns) :- memberchk(X,Ns), \+ memberchk(Y,Ns), !.
acceptable(X,Y,Ns) :- memberchk(Y,Ns), \+ memberchk(X,Ns).

% An almost trivial use of the predicate s_tree/2 is the following
% tree tester predicate:
 
% is_tree(G) :- the graph G is a tree
is_tree(G) :- s_tree(G,G), !.


% Another use is the following connectivity tester:

% is_connected(G) :- the graph G is connected
is_connected(G) :- s_tree(G,_), !.

% Example graph p83.dat

test :-  
   see('p83.dat'), read(G), seen,
   human_gterm(H,G),
   write(H), nl, 
   setof(T,s_tree(G,T),Ts), length(Ts,N),
   write(N).