Trees spanning 2

Description

Finding a spanning tree of a graph

Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.

Download

Program source code: trees_spanning_2.pl

Listing

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

Comments

pl/prolog/pllib/trees_spanning_2.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0