Листовые узлы ориентированного графа - Пролог

Question

Кто-нибудь знает, как получить список листовых узлов в Прологе?

Допустим, у меня есть простой ориентированный граф, описываемый этими ориентированными ребрами:

de(0,1).
de(0,2).
de(2,3).
de(2,4).
de(3,4).
de(4,5).

Теперь, как рекурсивно просмотреть график и написать список этих двух конечных узлов (узлы 1 и 5)?

Спасибо за любой ответ!

Edit:

Хорошо, у меня есть 1-й предикат, написанный и работающий:

isLeaf(Node) :-
not(de(Node,_)).

но сейчас я понятия не имею, как пройти по графику и написать выходной список конечных узлов. Я знаю, это довольно просто, но у меня нет опыта в этом мышлении и программировании :(

Answer 1

Вам нужно определить предикат is_leaf/1, который является генератором , то есть он создает экземпляр входной переменной с возможными решениями.

Примерно так:

% Directed graph
de(0,1).
de(0,2).
de(2,3).
de(2,4).
de(3,4).
de(4,5).

% If Node is ground,
%         then test if it is a child node that is not a parent node.
% If Node is not ground,
%         then bind it to a child node that is not a parent node.
is_leaf(Node) :-
    de(_, Node),
    \+ de(Node, _).

Примеры использования:

?- is_leaf(Node).
Node = 1 ;
Node = 5.

?- is_leaf(Node), writeln(Node), fail ; true.
1
5
true.

?- findall(Node, is_leaf(Node), Leaf_Nodes).
Leaf_Nodes = [1, 5].

Ваше решение немедленно вызывает not. (Кстати, SWI-Prolog рекомендует использовать \+ вместо not.)

isLeaf(Node) :-
    not(de(Node,_)).

Это означает, что ваш isLeaf/2 не является генератором : он либо завершается ошибкой, либо завершается успешно (один раз) и никогда не связывает входной аргумент, если он оказывается переменной. Кроме того, он никогда не проверяет, является ли вход листом, он просто проверяет, не является ли он родительским узлом.

% Is it false that 1 is a parent? YES
?- isLeaf(1).
true.

% Is it false that blah is a parent? YES
?- isLeaf(blah).
true.

% Is it false that 2 is a parent? NO
?- isLeaf(2).
false.

% Basically just tests if the predicate de/2 is in the knowledge base,
% in this sense quite useless.
?- isLeaf(Node).
false.

Answer 2

Подумайте о том, что вы сделаете противоположное, то есть сформулируете предикат, который может сказать вам, является ли узел ветвью.

Исходя из этого, довольно просто написать предикат, который пересекает график, печатать и возвращать, если текущий узел является листом.