Nœuds feuille de graphe orienté - Prolog

Question

Quelqu'un sait-il, comment obtenir une liste de nœuds feuilles dans Prolog?

Disons que j'ai un graphique simple dirigé décrit par ces arêtes orientées:

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

Maintenant, comment parcourir récursive le graphique et écrire une liste de ces 2 nœuds feuilles (nœud 1 & 5)?

Merci pour toute réponse!

Edit:

Eh bien, j'ai 1er prédicat écrit & travail:

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

mais maintenant, je ne sais pas comment traverser le graphique et écrire la liste de sortie des nœuds feuilles. Je sais, il est assez facile, mais je n'ai pas l'expérience de cette façon de penser et la programmation :(

Answer 1

Vous devez définir un prédicat is_leaf/1 qui est un générateur , -à-dire qu'il instancie la variable d'entrée avec des solutions possibles

Quelque chose comme ceci:

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

Exemples d'utilisation:

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

Votre solution appelle immédiatement not. (BTW, recommande SWI-Prolog à l'aide \+ au lieu de not.)

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

Cela signifie que votre isLeaf/2 n'est pas un générateur : il a échoué ou réussi (une fois), et se fixe jamais l'argument d'entrée si elle arrive à être une variable. En outre, il ne teste jamais que l'entrée est une feuille, il teste simplement s'il ne s'agit pas d'un nœud parent.

% 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

Pensez à vous faire le contraire avait, à savoir formuler un prédicat qui peut vous dire si un nœud est une branche.

a partir de ce qu'il devrait être assez simple d'écrire un prédicat qui traverse le graphique, l'impression et faire marche arrière si le noeud courant est une feuille.