# Różnice

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

 — 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 ===== + + % 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: 2019/06/27 15:50 (edycja zewnętrzna)