Blattknoten von gerichteten Graphen - Prolog

Question

Weiß jemand, wie man eine Liste von Blattknoten in Prolog bekommt?

Lasst uns sagen, ich habe einen einfachen gerichteten Graphen durch diese gerichteten Kanten beschrieben:

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

Nun, wie rekursiv die Grafik durchsuchen und eine Liste dieser zwei Blattknoten (Knoten 1 & 5) schreiben?

Danke für jede Antwort!

Edit:

Nun, ich habe erstes Prädikat geschrieben & Arbeits:

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

aber jetzt habe ich keine Ahnung, wie das Diagramm zu durchqueren und die Ausgabeliste von Blattknoten schreiben. Ich weiß, es ist ziemlich einfach, aber ich habe keine Erfahrung in dieser Denkweise und Programmierung :(

Answer 1

Sie benötigen ein Prädikat is_leaf/1 zu definieren, die ein Generator ist, dh es instanziiert die Eingangsvariable mit möglichen Lösungen

Etwas wie folgt aus:

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

Anwendungsbeispiele:

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

Ihre Lösung sofort not nennt. (Btw, SWI-Prolog empfiehlt \+ statt not verwenden.)

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

Das bedeutet, dass Ihr isLeaf/2 kein Generator ist: entweder sie versagt oder erfolgreich ist (einmal) und bindet nie das Eingabeargument, wenn es ist zufällig eine Variable. Es testet auch nie, dass die Eingabe ein Blatt ist, es testet nur, ob es kein Elternknoten ist.

% 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

von Ihnen denken das Gegenteil tun würde, also formuliert ein Prädikat, das man sagen kann, ob ein Knoten ein Zweig ist.

Von dass es ziemlich einfach sein sollte, ein Prädikat zu schreiben, die die Grafik, Druck und Rückzieher durchläuft, wenn der aktuelle Knoten ein Blatt ist.