Różnice między wybraną wersją a wersją aktualną.
|
pl:prolog:pllib:graph_path_2 [2019/06/27 15:50] |
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 ===== | ||
