I'm currently learning answer set programming with clingo and I'm really struggling with calculating the distance between nodes in a directed graph.
I would know how to hardcode it for every distance but that's no real way to do it.
I currently have this:
node(X) :- edge(X,_).
node(Y) :- edge(_,Y).
edge(X,Y) :- edge(X,Z), edge(Z,Y).
distance(X,Y,1) :- edge(X,Y).
distance(X,Y,2) :- distance(X,Z,_), distance(Z,Y,_), X != Z, Y != Z.
%distance(X,Y,D) :- ?
I know which nodes reach other nodes from the third line but how can I calculate the distance between them in the directed graph?
This is the program:
node(X) :- edge(X,_) .
node(Y) :- edge(_,Y) .
num(N) :- N = #count{ X : node(X) }. % compute the number of nodes (see below)
edge(Y,X) :- edge(X,Y) .
distance(X,Y,1) :- edge(X,Y) .
distance(X,Y,D) :- distance(X,Z,D1), distance(Z,Y,D2),
X!=Y, % for not allowing self-reaching paths (that are always of length 2)
D=D1+D2, % sum the edges' distances
D<N, num(N) . % the distance is less than the number of nodes (otherwise it would loop infinitely)
min_distance(X,Y,D) :- distance(X,Y,_), #min {DD : distance(X,Y,DD)} = D .
If you want to impose 0 as distance from a node to itself, just add the following rule:
distance(X,X,0) :- node(X) .
Take now the following EDB instance:
edge(a,b) .
edge(b,c) .
edge(a,c) .
edge(a,d) .
edge(d,e) .
The execution produces only these ground atoms for the predicate min_distance/3:
min_distance(a,b,1) min_distance(b,c,1) min_distance(a,c,1) min_distance(a,d,1) min_distance(d,e,1) min_distance(e,d,1) min_distance(d,a,1) min_distance(c,a,1) min_distance(c,b,1) min_distance(b,a,1) min_distance(e,a,2) min_distance(a,e,2) min_distance(c,d,2) min_distance(b,d,2) min_distance(d,c,2) min_distance(d,b,2) min_distance(e,b,3) min_distance(e,c,3) min_distance(c,e,3) min_distance(b,e,3)
If you want to restrict the results to "one-way" distance, you can add X<=Y in the body of the last rule, obtaining:
min_distance(a,b,1) min_distance(b,c,1) min_distance(a,c,1) min_distance(a,d,1) min_distance(d,e,1) min_distance(a,e,2) min_distance(c,d,2) min_distance(b,d,2) min_distance(c,e,3) min_distance(b,e,3)