Różnice

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

Odnośnik do tego porównania

pl:prolog:pllib:graph_path_2 [2019/06/27 15:50] (aktualna)
Linia 1: Linia 1:
 +====== Graph path 2 ======
 +{{tag>​graphs}}
 +===== Description =====
 +Testing connectivity breadth-first in a graph
 +
 +**Source**: ​ The Art of Prolog
 +===== Download =====
 +Program source code: {{graph_path_2.pl}}
 +===== Listing =====
 +<code prolog>
 +/* 
 +    connected(X,​Y) :-
 + Node X is connected to node Y in the graph defined by edge/2 facts.
 +*/
 + :- op(40,​xfx,​\).
 +
 + connected(X,​Y) :- enqueue(X,​Q\Q,​Q1),​ connected_bfs(Q1,​Y,​[X]).
 +
 + connected_bfs(Q,​Y,​Visited) :- empty(Q), !, fail.
 + connected_bfs(Q,​Y,​Visited) :- dequeue(X,​Q,​Q1),​ X=Y.
 + connected_bfs(Q,​Y,​Visited) :- 
 +    ​dequeue(X,​Q,​Q1), ​
 +    ​findall(N,​edge(X,​N),​Edges),​
 +    ​filter(Edges,​Visited,​Visited1,​Q1,​Q2),​
 +    ​connected_bfs(Q2,​Y,​Visited1).
 +
 + filter([N|Ns],​Visited,​Visited1,​Q,​Q1) :-
 +    ​member(N,​Visited),​ !, filter(Ns,​Visited,​Visited1,​Q,​Q1).
 + filter([N|Ns],​Visited,​Visited1,​Q,​Q2) :-
 +    not member(N,​Visited),​ !, 
 +    ​enqueue(N,​Q,​Q1), ​
 +    ​filter(Ns,​[N|Visited],​Visited1,​Q1,​Q2).
 + filter([],​Visited,​Visited,​Q,​Q).
 +
 + enqueue(X,​Qh\[X|Qt],​Qh\Qt).
 + dequeue(X,​[X|Qh]\Qt,​Qh\Qt).
 + empty([]\[]).
 +
 +% Data
 +
 +     ​edge(a,​b). ​  ​edge(a,​c). ​  ​edge(a,​d). ​ edge(a,​e). ​ edge(d,​j).  ​
 +     ​edge(c,​f). ​  ​edge(c,​g). ​  ​edge(f,​h). ​ edge(e,​k). ​ edge(f,​i).  ​
 +     ​edge(x,​y). ​  ​edge(y,​z). ​  ​edge(z,​x). ​ edge(y,​u). ​ edge(z,​v).  ​
 +
 +% Program 16.5: Testing connectivity breadth-first in a graph
 +</​code>​
 +===== Comments =====
  
pl/prolog/pllib/graph_path_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