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 ===== | ||
| + | <code prolog> | ||
| + | /* | ||
| + | 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 | ||
| + | </code> | ||
| + | ===== Comments ===== | ||
