|
| Hi, I am a begginer with Prolog and I need some help making a directed weighted graph program. What i want to do is write a predicate which answers yes if there is a path connecting two nodes a,b with a weight W. My code until now is:
edge(a,b,8).
edge(b,d,4).
edge(d,e,6).
edge(c,a,3).
edge(e,b,7).
edge(c,f,9).
edge(h,f,5).
edge(h,g,1).
edge(g,c,8).
edge(e,g,2).
edge(f,i,9).
edge(i,f,3).
edge(X,Y):-edge(X,Y,W).
path(X,Y):-edge(X,Y).
path(X,Y):-edge(Z,Y),path(X,Z).
path(X,Y,W):-edge(X,Y,W).
path(X,Y,W):-edge(Z,Y,W1),path(X,Z,W2),W is W1+W2.
The problem is at the last line, if for example the query is ?-path(a,b,10) which must answer No,the program falls into an infinite loop because of the cycles in the graph.
I also tried
path(X,Y,W):-edge(Z,Y,W1),path(X,Z,W2),((W=nil)->true;(W1=<W,W2=<W)),W is W1+W2.
but it's not working. What i'm trying to do is forcing the search to stop when W1 or W2 is greater than W in queries like path(a,b,10) but not stop when W is a variable in queries like path(a,b,W).
I also want to write a predicate npath(X,Y,N) which answers yes if N is the number of different paths between X and Y. |
|