2

`I want to print all the ways to reach Node e from Node a in a weighted unidrected acyclic graph. but my program misses a few long routes.

This is my program.

%Declare all the edges
edge(a,b,1). 
edge(a,c,6). 
edge(b,c,4). 
edge(b,d,3). 
edge(b,e,1). 
edge(c,d,1). 
edge(d,e,1).

% Two nodes are adjacent if there exists a edge between them
adj(X, Y, W) :- edge(X, Y, W).
adj(Y, X, W) :- edge(Y, X, W).

% return 0 weight and empty path because path is empty to reach the same node 
% from the node itself and therefor no wirght as well.
findpath(X, X, 0, []).

% if X and Y are adjacent then append Y to X into the Path Variable
findpath(X,Y,Weight,Path) :- adj(X,Y,Weight),
                             append([X],[Y],Path). 

% if X and Y are not adjacent, then consider nodes who are adjacent to Y with 
% weight W2 ,  recursively call path predicate replacing Y with A and W1 with W2
% add their weight - W as W1 + W2 and append to Path. 
findpath(X,Y,Weight,Path) :- not(adj(X,Y,Weight)), 
                             edge(A,Y,Weight1), 
                             findpath(X,A,Weight2,P1),
                             Weight is Weight1+Weight2, 
                             append(P1,[Y],Path).

Output

`2 ?- findpath(a, e, W, P).
W = 2,
P = [a, b, e] ;
W = 2,
P = [a, b, e] ;
W = 5,
P = [a, b, d, e] ;
W = 5,
P = [a, b, d, e] ;
W = 8,
P = [a, c, d, e] ;
W = 8,
P = [a, c, d, e] ;
false.

My program missed a, b, c, e and a, b, c, d ,e. I dont understand why ? Also , it repeats the output as well.`

false
  • 10,264
  • 13
  • 101
  • 209
Hardik Sakhuja
  • 21
  • 2
  • 1
    undirected graphs with more than one connected nodes are by definition cyclic, since a-b-a is a cycle. so the only way for an undirected graph to be acyclic is to be wholly disjoint. unconnected. to have no edges, only nodes. – Will Ness Mar 03 '23 at 13:01
  • 1
    you meant to write `adj(X, Y, W) :- edge(Y, X, W).` as the second clause of `adj/3`. – Will Ness Mar 03 '23 at 13:36

2 Answers2

2

(There is no path "abce" since there is no connection between c and e)

adj/3 describes the very same solutions that edge/3 does. You exchanged arguments both in the head and the goal. Exchange them only once. Using path/4 gives you all acyclic paths. Then you need to add a weight.

:- set_prolog_flag(double_quotes, chars).

adj(X, Y, W) :- edge(X, Y, W).
adj(X, Y, W) :- edge(Y, X, W).

adj(X,Y) :-
   adj(X,Y,_).

?- path(adj, Path, a,e).
   Path = "abcde"
;  Path = "abde"
;  Path = "abe"
;  Path = "acde"
;  Path = "acdbe"
;  Path = "acbde"
;  Path = "acbe"
;  false.

?- setof(t,path(adj, Path, a,e),_).
   Path = "abcde"
;  Path = "abde"
;  Path = "abe"
;  Path = "acbde"
;  Path = "acbe"
;  Path = "acdbe"
;  Path = "acde".
?- path(adj, Path, a,Y).
   Path = "a", Y = a
;  Path = "ab", Y = b
;  Path = "abc", Y = c
;  Path = "abcd", Y = d
;  Path = "abcde", Y = e
;  Path = "abd", Y = d
;  Path = "abde", Y = e
;  Path = "abdc", Y = c
;  Path = "abe", Y = e
;  Path = "abed", Y = d
;  Path = "abedc", Y = c
;  Path = "ac", Y = c
;  Path = "acd", Y = d
;  Path = "acde", Y = e
;  Path = "acdeb", Y = b
;  Path = "acdb", Y = b
;  Path = "acdbe", Y = e
;  Path = "acb", Y = b
;  Path = "acbd", Y = d
;  Path = "acbde", Y = e
;  Path = "acbe", Y = e
;  Path = "acbed", Y = d
;  false.
false
  • 10,264
  • 13
  • 101
  • 209
0

You need to keep a "visited" list of edges if you don't want to go in circles. And you need to fix your adj/3 (this is what is giving you the double answers!)

adj(X,Y,D):-edge(X,Y,D);edge(Y,X,D).

path(X,Y,D,P):-p(X,Y,[],D,P).

p(X,X,_,0,[X]).
p(X,Y,V,D,[X|P]):-adj(X,Z,W),\+memberchk(Z,V),p(Z,Y,[X|V],E,P),D is E+W.
TA_intern
  • 2,222
  • 4
  • 12