noeuds de feuille de graphe orienté - Prolog

Question

Quelqu'un sait-il, comment obtenir une liste des nœuds feuilles en 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 récursive parcourir le graphique et écrire une liste de ces 2 nœuds feuilles (nœud 1 et 5)?

Merci pour toute réponse!

Edit:

Eh bien, je l'ai écrit et 1er prédicats travail:

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

mais maintenant, je ne sais pas comment parcourir 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 de la programmation :(

Answer 1

Vous devez définir un is_leaf/1 sous-jacente 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, SWI-Prolog recommande d'utiliser \+ au lieu de not.)

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

Cela signifie que votre isLeaf/2 est pas générateur : il a échoué ou réussi (une fois), et se fixe jamais l'argument d'entrée si elle se trouve être une variable. En outre, il teste jamais que l'entrée est une feuille, il teste simplement si ce n'est pas 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 que vous feriez le contraire, à 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.