如何在序言中编写程序，对图形进行比较

Question

我正在尝试在 prolog 中编写一个程序，如果从 a 到 b 的所有路径都相同大小，则为 true。示例：我们有一条从 a 到 b 的路径，另一条从 a 到 c 再到 b 的路径，这里它是假的，因为从 a 到 b 有两条不同大小的路径，第一个是 1，另一个是 2。它们都必须是大小相同，否则为假。

我开始这样做是为了获得每条路径的长度，但我被困在这里，我只需要比较是否有两条相同的路径，如果是，那么我们比较两个结果，如果它们是相同的长度则为 true 否则为 false，但我不知道如何在 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.

Answer 1

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

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

使用 path/4.

根据这个定义，您还可以使用您指出的事实提出更一般的问题：

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.

Answer 2

我假设你有一个无环有向图并且路径由顶点列表表示。

%   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).

示例：

?- 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.

那么，两个顶点X和Y之间的所有路径都是相同大小的，如果顶点X和Y之间没有两条大小不同的路径。

% 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).

示例：

?- all_same_size(a, d).
true.

?- all_same_size(a, e).
false.

如何在序言中编写程序，对图形进行比较

How to code a program in prolog, that does comparison on graphs

prolog