# Różnice

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

 — pl:prolog:pllib:graph_path_3 [2019/06/27 15:50] (aktualna) Linia 1: Linia 1: + ====== Graph path 3 ====== + {{tag>​graphs}} + ===== Description ===== + Testing connectivity breadth-first in a DAG + + **Source**: ​ The Art of Prolog + ===== Download ===== + Program source code: {{graph_path_3.pl}} + ===== Listing ===== + + /* + connected(X,​Y) :- + Node X is connected to node Y in the DAG defined + by edge/2 facts. + */ + :- op(40,​xfx,​\). + + connected(X,​Y) :- enqueue(X,​Q\Q,​Q1),​ connected_bfs(Q1,​Y). + + connected_bfs(Q,​Y) :- empty(Q), !, fail. + connected_bfs(Q,​Y) :- dequeue(X,​Q,​Q1),​ X=Y. + connected_bfs(Q,​Y) :- + ​dequeue(X,​Q,​Q1),​ enqueue_edges(X,​Q1,​Q2),​ connected_bfs(Q2,​Y). + + enqueue(X,​Qh\[X|Qt],​Qh\Qt). + dequeue(X,​[X|Qh]\Qt,​Qh\Qt). + empty([]\[]). + + enqueue_edges(X,​Xs\Ys,​Xs\Zs) :- find_all_dl(N,​edge(X,​N),​Ys\Zs),​ !. + + %  findall_dl/​3 ​ :-  see Program 16.3 + + % 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.4:  Testing connectivity breadth-first in a DAG + ​ + ===== Comments =====
pl/prolog/pllib/graph_path_3.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)