2

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?

logi-kal
  • 7,107
  • 6
  • 31
  • 43
Chrizzoh
  • 35
  • 5

1 Answers1

2

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)
logi-kal
  • 7,107
  • 6
  • 31
  • 43