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

Question

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

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

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

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

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

Edit:

Ну, я первый предикат написал & работы:

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

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

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