How to check for membership in a list in CLINGO?

Question

Having a background in Prolog, I'm struggling to convert this DLV (which has builtin predicates to handle lists similarly to Prolog) program into CLINGO.

path(X,Y,[X|[Y]]) :- rel(X,Y).
path(X,Y,[X|T]) :- rel(X,Z), path(Z,Y,T), not #member(X,T).

rel(X,Y) :- edge(X,Y).
rel(X,Y) :- edge(Y,X).

edge(a,b).
edge(a,c). 
edge(b,a). 
edge(b,c).
edge(e,c).

So far I managed to achieve this:

path(X,Y,cons(X,cons(Y,empty))) :- edge(X,Y).
path(X,Y,cons(X,L)) :- edge(X,Z), path(Z,Y,L), not member(X,path(Z,Y,L)).

member(X,path(X,T,cons(X,Y))) :- path(X,T,cons(X,Y)).
member(X,path(S,X,cons(S,L))) :- path(S,X,cons(S,L)).
member(X,path(S,T,cons(S,cons(Z,L)))) :- member(X,path(Z,T,cons(Z,L))).

% same edges    

but I get the error unsafe variables in in file - at line 7 and column 1-72 and I don't fully understand why. I was wondering if anyone could help.

Answer 1

You never defined what S could be.

Add edge(S,Z) to the rule body on line 7 to get rid of that error. Or if you want to define a vertex predicate you could use vertex(S) as well.

---

So I fixed your code with the cons-lists. This approach is unusual because lists are not a key feature in asp like they are in prolog. Ok, here is my solution (works for directed graphs):

edge(a,b).
edge(a,c). 
edge(b,c). 
edge(c,a). 
edge(c,d). 
edge(d,b).

node(X) :- edge(X,_). % get nodes
node(X) :- edge(_,X). % get nodes
num(N):- {node(X)} == N. % count nodes
step(1..N) :- num(N). % mark possible steps

path(X,Y,2,cons(X,cons(Y,empty))) :- edge(X,Y).
path(A,C,NN+1,cons(A,L)) :- edge(A,B), path(B,C,NN,L), step(NN+1).

member(X,path(X,Y,N,cons(X,L))) :- path(X,Y,N,cons(X,L)).
member(Y,path(X,Y,N,cons(X,L))) :- path(X,Y,N,cons(X,L)).   
member(M,path(S,T,NN+1,cons(S,cons(Z,L)))) :- member(M,path(Z,T,NN,cons(Z,L))), path(S,T,NN+1,cons(S,cons(Z,L))).   

track(Y,Z,N,L):- {member(X,path(Y,Z,N,L)):node(X)} == N, path(Y,Z,N,L).

#show track/4.

At first you need to know all the of vertices to calculate their number. Also I introduced the predicate step to validate a depth for the path. path also has a depth-counter now as third argument. All possible paths are stored within path/4, cycles are allowed. The member/2 predicate is generated to show all the member vertices within a path/4. In a last step all path's are forwarded to the predicate track/4 if and only if the number of distinct member vertices equals the path length. Since duplicates will not be counted this condition makes sure that only paths without cycles are forwarded. Please note that all of the above steps are forced. There is exactly one answer set for every graph.

So let's have a look at a more ASP like solution. Normally you would ask a specific question ('path from a to b with length n') instead of a generic one ('all possible paths from all nodes to all nodes with every possible length'). The following code needs to have a start node (start/1) and an end node (end/1). The program forces a (random) order by assigning exactly one index number to each vertex within the predicate order/2. The order predicate is copied to the path predicate as long as the index is not larger than the index of the end node (path(S,N):- order(S,N), maxZ(Z), S<=Z.). The only constrains is that within the order of path every 2 neighboring vertices are connected with an edge. The constraint line is read as It can not ne the case that there is a node S1 on position N within a path and a node S2 on position N+1 within a path and there is no edge from S1 to S2.

edge(a,b).
edge(a,c). 
edge(b,c). 
edge(c,a). 
edge(c,d). 
edge(d,b).

start(a).
end(d).

node(X) :- edge(X,_). % get nodes
node(X) :- edge(_,X). % get nodes
num(N):- {node(X)} == N. % count nodes
step(1..N) :- num(N). % mark possible steps
order(1,A):- start(A). % start has index 1
maxZ(Z):- end(E), order(Z,E), step(Z). % end has index maxZ

{order(S,N):node(N)} == 1 :- step(S). % exactly one assignment per step
{order(S,N):step(S)} == 1 :- node(N). % exactly one assignment per node

path(S,N):- order(S,N), maxZ(Z), S<=Z. % copy order when index is not largter than end node index
:- path(N, S1), path(N+1, S2), not edge(S1,S2). % successing indices are connected through edges
        
#show path/2.