% Figure 9.23 Finding a spanning tree of a graph: a `declarative'
% program. Relations node and adjacent are as in Figure 9.22.
:- op( 900, fy, not).
% not Goal): negation as failure;
% Note: This is often available as a built-in predicate,
% often written as prefix operator "\+", e.g. \+ likes(mary,snakes)
not Goal :-
Goal, !, fail
;
true.
% 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) :-
subset( 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, X, Y | _] ). % 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
subset( [], [] ).
subset( [X | Set], Subset) :- % X not in subset
subset( Set, Subset).
subset( [X | Set], [X | Subset]) :- % X included in subset
subset( Set, Subset).