# Różnice

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

 — 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 ===== + + /* + 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 + ​ + ===== Comments =====
pl/prolog/pllib/graph_path_2.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)