0

I'm trying to code a program in prolog that says true if all the paths from a to b are the same size. Example : we have a path from a to b and another from a to c to b, here it's false because there are two paths from a to b with different sizes, the first is 1 and the other is 2. They all must be the same size otherwise it's false.

I started doing this to get the length of each path, but I'm stuck here, I just need to compare if there are two same paths or not, if yes then we compare the two results if they are the same length then true otherwise false, but I don't know how to do it in Prolog :

chemin1(X, Y):-
    arete(X,Y).
chemin1(X, Y):-
    arete(X,Z),
    chemin1(Z,Y).

chemin2(X, Y, N):-
    arete(X, Y),
    N is 1.
chemin2(X, Y, N):-
    arete(X, Z),
    N1 is 1,
    chemin2(Z, Y, N2),
    N is N1+N2.
Nobody
  • 103
  • 8

2 Answers2

1
chemin2(X0,X, N) :-
   path(arete, Path, X0,X),
   length(Path, N).

allequallength(X0, X) :-
   setof(N, chemin2(X0,X, N), [_]).

Using path/4.

With this definition you can also ask a more general question using the facts you indicated:

arete(a, b).
arete(b, d).
arete(b, c).
arete(a, c).

?- allequallength(X0,X).
   X0 = X
;  X0 = a, X = b
;  X0 = a, X = d
;  X0 = b, X = c
;  X0 = b, X = d.
false
  • 10,264
  • 13
  • 101
  • 209
  • thank you for your help, but it does not work, chemin2 has 3 parameters and you used 2 and when I tried with these paths it didn't work, it should return false of course because there are two paths from a to c : arete(a, b). arete(b, d). arete(b, c). arete(a, c). – Nobody Dec 09 '21 at 22:29
  • Thanks that was an error of mine, it has been corrected. – false Dec 10 '21 at 09:02
1

I'm assuming you have an acyclic directed graph and that a path is represented by a vertex list.

%   b
%  / \
% a   d
%  \ / \
%   c---e

arete(a, b).
arete(a, c).
arete(b, d).
arete(c, d).
arete(c, e).
arete(d, e).

chemin(X, X, [X]).
chemin(X, Z, [X|Xs]):- arete(X, Y), chemin(Y, Z, Xs).

Examples:

?- chemin(a, d, C).
C = [a, b, d] ;
C = [a, c, d] ;
false.

?- chemin(a, e, C).
C = [a, b, d, e] ;
C = [a, c, d, e] ;
C = [a, c, e] ;
false.

Then, all paths between two vertices X and Y are of the same size, if there are no two paths between vertices X and Y that are of different sizes.

% all_same_size(+X, +Y)

  all_same_size(X, Y) :-
      not( ( chemin(X, Y, Xs),
             chemin(X, Y, Ys),
             not( same_size(Xs, Ys) ) ) ).

same_size([], []).
same_size([_|Xs], [_|Ys]) :- same_size(Xs, Ys).

Examples:

?- all_same_size(a, d).
true.

?- all_same_size(a, e).
false.
slago
  • 5,025
  • 2
  • 10
  • 23
  • The generalization `all_same_size(a,Y).` fails, although there is at least one solution. – false Dec 10 '21 at 09:19
  • @false Thanks, but I already knew this. That's why I've indicated the mode `all_same_size(+X, +Y)`, for which the query `all_same_size(a,Y)` makes no sense. – slago Dec 10 '21 at 09:57
  • Does OP know it? – false Dec 10 '21 at 20:29
  • @false I don't know if OP know it, but I think OP should know it, as this is the convention used in every Prolog compiler manual. – slago Dec 10 '21 at 20:48