Graph path

Description

Finding a path by depth-first search.

Source: The Art of Prolog

Download

Program source code: graph_path.pl

Listing

/*
	connected(X,Y) :-
		Node X is connected to node Y,
		given an edge/2 relation describing a DAG.
*/
 
     connected(X,X).
     connected(X,Y) :- edge(X,N), connected(N,Y).
 
  /*  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).  
 
/*  path(X,Y,Path) :-
		Path is a path between two nodes X and Y in the
		DAG defined by the relation edge/2
*/
     path(X,X,[X]).
     path(X,Y,[X|P]) :- edge(X,N), path(N,Y,P).
 
%	Program 14.9: Finding a path by depth-first search

Comments

pl/prolog/pllib/graph_path.txt · ostatnio zmienione: 2019/06/27 15:50 (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