Add loop edges in datalog (bddbddb)

Question

I have the following rules that find all the paths among a graph.

path(X,Y) :- edge(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y).

But, I want also for each node n, to add the edge n->n if not already present.

How can I do this without having any relation of the nodes?

score 3 · Answer 1 · edited May 23 '17 at 12:33

3

In Prolog alone, you would write:

path(X,X).
path(X,Y) :- false, edge(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y).

or somewhat shorter and more terminating using closure0/3.

path(X,Y) :-
   closure0(edge, X,Y).

In (many definitions of) Datalog as a subset of Prolog, facts like path(X,X). are not permitted, since they admit an infinite set of solutions.

So you need to restrict that fact to a finite set of nodes. However, since you do not have an explicit definition of nodes, you need to make up one based on the edges you have:

node(X) :-
   edge(X,_).
node(Y) :_
   edge(_,Y).

which now leads to:

path(X,X) :-
   node(X).
path(X,Y) :-
   edge(X,Z),
   path(Z,Y).

edited May 23 '17 at 12:33

Community

1
1

answered Mar 31 '16 at 14:16

false

10,264
13
101
209

Error on line : 'path(X,X) :- node(X).' ^ Variable repeated multiple times in a single term – eternalStudent Mar 31 '16 at 14:26
1

emma: So you are really using another system, and this is entirely unrelated to Prolog. You should indicate the name of this system in your question. – false Mar 31 '16 at 14:40
It's the datalog language of bddbddb system. Is it so different?! – eternalStudent Mar 31 '16 at 14:42
2

@emma: Yes. It is a "subset" of Prolog only in a very, very special sense. – false Mar 31 '16 at 14:43

Add loop edges in datalog (bddbddb)

1 Answers1