answer-set-programmingclingo

append an atom with exisiting variables and create new set in clingo


I am totally new in asp, I am learning clingo and I have a problem with variables. I am working on graphs and paths in the graphs so I used a tuple such as g((1,2,3)). what I want is to add new node to the path in which the tuple sequence holds. for instance the code below will give me (0, (1,2,3)) but what I want is (0,1,2,3). Thanks in advance.

g((1,2,3)).
g((0,X)):-g(X).

Solution

  • Naive fix:

    g((0,X,Y,Z)) :- g((X,Y,Z)).
    

    However I sense that you want to store the path in the tuple as is it is a list. Bad news: unlike prolog clingo isn't meant to handle lists as terms of atoms (like your example does). Lists are handled by indexing the elements, for example the list [a,b,c] would be stored in predicates like p(1,a). p(2,b). p(3,c).. Why? Because of grounding: you aim to get a small ground program to reduce the complexity of the solving process. To put it in numbers: assuming you are searching for a path which includes all n nodes. This sums up to n!. For n=10 this are 3628800 potential paths, introducing 3628800 predicates for a comparively small graph. Numbering the nodes as mentioned will lead to only n*n potential predicates to represent the path. For n=10 these are just 100, in comparison to 3628800 a huge gain.

    To get an impression what you are searching for, run the following example derived from the potassco website:

    % generating path: for every time exactly one node
    { path(T,X) : node(X) } = 1 :- T=1..6. 
    % one node isn't allowed on two different positions
    :- path(T1,X), path(T2,X), T1!=T2. 
    % there has to be an edge between 2 adjascent positions
    :- path(T,X), path(T+1,Y), not edge(X,Y). 
    #show path/2.
    
    % Nodes
    node(1..6).
    % (Directed) Edges
    edge(1,(2;3;4)).  edge(2,(4;5;6)).  edge(3,(1;4;5)).
    edge(4,(1;2)).    edge(5,(3;4;6)).  edge(6,(2;3;5)).
    

    Output:

    Answer: 1
    path(1,1) path(2,3) path(3,4) path(4,2) path(5,5) path(6,6)
    Answer: 2
    path(1,1) path(2,3) path(3,5) path(4,4) path(5,2) path(6,6)
    Answer: 3
    path(1,6) path(2,2) path(3,5) path(4,3) path(5,4) path(6,1)
    Answer: 4
    path(1,1) path(2,4) path(3,2) path(4,5) path(5,6) path(6,3)
    Answer: 5
    ...