Проверка связности графа

Я проверяю, связан ли график и по какой-то причине становится ложным, когда это должно быть правдой.

allConnected([]).
allConnected(A|L) :- checkConnect(A,L), allConnected(L).

checkConnect([],[]).
checkConnect(X, Head|Y) :- isConnected(X,Head), checkConnect(X,Y).
isConnected(X,Y) :- edge(X,Y); edge(Y,X).

edge(a,b).
edge(b,c).
edge(c,a).

Что я делаю для своего предиката, так это проверяю, подключен ли каждый узел в allConnected([a,b,c]). Я должен получить истину, но не могу определить свою ошибку, я пытался использовать трассировку, но это не помогает.


prolog transitive-closure
person John Smith    schedule 18.03.2016    source источник
comment
измените на allConnected([A|L]) :- ..., иначе он никогда не будет совпадать. После этого он будет зацикливаться навсегда :)   -  person CapelliC    schedule 18.03.2016
comment
@CapelliC: эта проблема характерна для SWI. Только SWI разрешает операторы, превышающие 1000 в аргументах.   -  person false    schedule 18.03.2016

Ответы (1)


arrow_upward
0
arrow_downward

Как сказал CapelliC выше, вы захотите добавить квадратные скобки вокруг ваших списков: [A|L] вместо A|L и [Head|Y] вместо Head|Y.

Вторая проблема — это условие завершения в checkConnect:

checkConnect([],[]).

Вы указываете, что это истинно, когда оба аргумента могут быть сопоставлены с пустыми списками. Однако первый параметр checkConnect используется для вызова isConnected и, таким образом, будет означать, что он является символом, а не списком, как вы указываете в своем условии завершения. Другими словами, checkConnect никогда не будет соответствовать своему условию остановки.

То, что вы ищете, это:

checkConnect(_,[]).

(мы используем подстановочный знак _, так как в этот момент нам не нужен доступ к переменной)

person SND    schedule 18.03.2016