Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

pl:prolog:pllib:trees_spanning_2 [2019/06/27 15:50] (aktualna)
Linia 1: Linia 1:
 +====== Trees spanning 2 ======
 +{{tag>​trees}}
 +===== 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 =====
 +<code prolog>
 +% 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).
 +
 +
 +</​code>​
 +===== Comments =====
  
pl/prolog/pllib/trees_spanning_2.txt · ostatnio zmienione: 2019/06/27 15:50 (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