CODEWITHSUNDEEP
prolog
Tony
Tony

Reputation: 25

Leaf nodes of directed graph - Prolog

Does anybody know, how to get a list of leaf nodes in Prolog?

Let's say, I have a simple directed graph described by these directed edges:

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

Now, how to recursively browse the graph and write a list of those 2 leaf nodes (node 1 & 5)?

Thanks for any answer!

Edit:

Well, I have 1st predicate written & working:

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

but now, i have no idea how to traverse the graph and write the output list of leaf nodes. I know, it's quite easy but I have no experience in this way of thinking and programming:(

Upvotes: 1

Views: 1997

Answers (2)

Kaarel
Kaarel

Reputation: 10672

You need to define a predicate is_leaf/1 that is a generator, i.e. it instantiates the input variable with possible solutions.

Something like this:

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

Usage examples:

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

Your solution immediately calls not. (Btw, SWI-Prolog recommends using \+ instead of not.)

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

This means that your isLeaf/2 is not a generator: it either fails or succeeds (once), and never binds the input argument if it happens to be a variable. Also, it never tests that the input is a leaf, it just tests if it's not a parent node.

% 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.

Upvotes: 4

Christoffer
Christoffer

Reputation: 12910

Think of you'd do the opposite, i.e. formulate a predicate that can tell you if a node is a branch.

From that it should be pretty straightforward writing a predicate that traverses the graph, printing and backtracking if the current node is a leaf.

Upvotes: 0

Related Questions