% Figure 9.23   Finding a spanning tree of a graph: a `declarative' 
% program. Relations node and adjacent are as in Figure 9.22.


% Finding a spanning tree
% Graphs and trees are represented as lists of edges.

% stree( Graph, Tree): Tree is a spanning tree of Graph

stree( Graph, Tree)  :-
  subset1( Graph, Tree),
  tree( Tree),
  covers( Tree, Graph).

tree( Tree)  :-
  connected( Tree),
  not( hasacycle( Tree)).

% connected( Graph): there is a path between any two nodes in Graph

connected( Graph)  :-
  not( ( node( A, Graph), node( B, Graph), not( path( A, B, Graph, _)) )).

hasacycle( Graph)  :-
   adjacent( Node1, Node2, Graph),
   path( Node1, Node2, Graph, [Node1, _, _ | _] ). % Path of length > 1 

% covers( Tree, Graph): every node of Graph is in Tree

covers( Tree, Graph)  :-
  not( ( node( Node, Graph), not( node( Node, Tree)) )).

% subset( List1, List2): List2 represents a subset of List1

subset1( [], [] ). 

subset1( [_ | Set], Subset)  :-            % X not in subset
  subset1( Set, Subset).

subset1( [X | Set], [X | Subset])  :-      % X included in subset
  subset1( Set, Subset).

% path( A, Z, Graph, Path): Path is an acyclic path from A to Z in Graph
path( A, Z, Graph, Path)  :-
  path1( A, [Z], Graph, Path).

% path1( A, Path1, G, Path) if there is an acyclic Path 
% that starts from A and ends with Path1 
path1( A, [A | Path1], _, [A | Path1] ).

path1( A, [Y | Path1], Graph, Path)  :-
  adjacent( X, Y, Graph),
  not( member( X, Path1)),                        % No-cycle condition
  path1( A, [X, Y | Path1], Graph, Path).

% adjacent for graphs represented by lists of edges
adjacent( X,Y,Graph) :-  
  member( X-Y,Graph)
  ;
  member( Y-X,Graph).

node(X,Graph) :-
 member(X-Y,Graph)
 ;
 member(Y-X,Graph).

% example
test(Graph, Tree) :-
 Graph = [ a-b,b-c,b-d,c-d],  % Note the "list of edges" representation
 stree( Graph,Tree).