Graph path 3

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: 2017/07/17 08:08 (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