% 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).