Linear vertices of a directed graph - Prolog

Question

Linear vertices of a directed graph - Prolog

Does anyone 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 loop through the graph and write a list of those two leaf nodes (node 1 and 5)?

Thanks for any answer!

Edit:

Ok, I have the 1st predicate written and working:

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

but now I have no idea how to navigate the graphic and write the output list of leaf nodes. I know it's pretty easy, but I have no experience with this way of thinking and programming :(

+1

prolog

Tony May 19 '09 at 8:16

a source to share

2 answers

Consider what you would do the other way around, that is, formulate a predicate that can tell you if a node is a branch.

From this it should be pretty easy to write a predicate that traverses the plot, print and backtrack if the current node is a leaf.

0

Christoffer May 19 '09 at 8:25

a source to share

Kaarel · Accepted Answer · 2009-05-19T12:06:59+0000

You need to define a predicate is_leaf/1

that is a generator, that is, it instantiates an input variable with possible solutions.

Something like that:

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

Examples of using:

?- 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 calls immediately not

. (Btw, SWI-Prolog recommends using \+

instead not

.)

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

This means that yours is isLeaf/2

not a generator: it either fails or succeeds (once), and never binds the input argument if it is a variable. Also, it never checks if the input is a leaf, it just checks to see if it is the 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.

Linear vertices of a directed graph - Prolog

More articles: