ASP Hamiltonian Cycle Story

Question

Hello I am new to answer-set-programming. I have done a little prolog in the past! I am trying to solve this problem I believe it can be solved with hamiltonian-cycle, let me know your opinion. If you are not familiar with ASP you can visit this site [clingo and gringo][1]. You can run the files in terminal with this command clingo name_of_the_file.lp or clingo name_of_the_file.lp4 I tested it in Ubuntu.

(these are .lp or .lp4 files) The first code I read and understood was that which has 3 results

% Generating part
% ---------------
% Cardinality constraint:
% For any ground fact cycle(X,Y) in the answer set:
% - there must be a corresponding edge(X,Y)
% - there must be exactly 1 of cycle(X,Y) for any X
% - there must be exactly 1 of cycle(X,Y) for any Y

{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).

% Define
reached(Y) :- cycle(1,Y).
reached(Y) :- cycle(X,Y), reached(X).

% Testing part
% ------------
% It is a contradiction to that have a "node" that is not "reached"

:- node(Y), not reached(Y).

% Defining part
% -------------

% 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)).

% Edge Costs cost(X,Y,Cost)
cost(1,2,2).  cost(1,3,3).  cost(1,4,1).
cost(2,4,2).  cost(2,5,2).  cost(2,6,4).
cost(3,1,3).  cost(3,4,2).  cost(3,5,2).
cost(4,1,1).  cost(4,2,2).
cost(5,3,2).  cost(5,4,2).  cost(5,6,1).
cost(6,2,4).  cost(6,3,3).  cost(6,5,1).

% Optimize minimum cost and cycle 
#minimize { C,X,Y : cycle(X,Y), cost(X,Y,C) }.

% Displaying part
% ---------------
#show cycle/2.

I get this result:

clingo version 5.4.0
Reading from cycle_hamilt.lp4
Solving...
Answer: 1
cycle(1,4) cycle(4,2) cycle(3,1) cycle(2,6) cycle(6,5) cycle(5,3)
Optimization: 13
Answer: 2
cycle(1,4) cycle(4,2) cycle(3,1) cycle(2,5) cycle(6,3) cycle(5,6)
Optimization: 12
Answer: 3
cycle(1,2) cycle(4,1) cycle(3,4) cycle(2,5) cycle(6,3) cycle(5,6)
Optimization: 11
OPTIMUM FOUND

Models       : 3
  Optimum    : yes
Optimization : 11
Calls        : 1
Time         : 0.003s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.003s

I tried to convert this code in this:

% Generate
{ cycle(X,Y) : edge(X,Y) } = street1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = street1 :- node(Y).
% Define
reached(Y) :- cycle(street1,Y).
reached(Y) :- cycle(X,Y), reached(X).
% Test
:- node(Y), not reached(Y).

% Nodes
%node(1..6).

node(street1..street6).

%node(street1).
%node(street2).
%node(street3).
%node(street4).
%node(street5).
%node(street6).
%node(street1;street2;street3;street4;street5;street6).

% (Directed) Edges
edge(street1,(street2;street3;street4)).  
edge(street2,(street4;street5;street6)).  
edge(street3,(street1;street4;street5)).
edge(street4,(street1;street2)).    
edge(street5,(street3;street4;street6)).  
edge(street6,(street2;street3;street5)).

% Edge Costs
cost(street1,street2,2).  cost(street1,street3,3).  cost(street1,street4,1).
cost(street2,street4,2).  cost(street2,street5,2).  cost(street2,street6,4).
cost(street3,street1,3).  cost(street3,street4,2).  cost(street3,street5,2).
cost(street4,street1,1).  cost(street4,street2,2).
cost(street5,street3,2).  cost(street5,street4,2).  cost(street5,street6,1).
cost(street6,street2,4).  cost(street6,street3,3).  cost(street6,street5,1).


% Optimize minimum cost and cycle 
#minimize { C,X,Y : cycle(X,Y), cost(X,Y,C) }.

% Display
#show cycle/2.

and this one seems a bit awkward I get this result:

clingo version 5.4.0
Reading from cleaning_street_names.lp4
Solving...
UNSATISFIABLE

Models       : 0
Calls        : 1
Time         : 0.003s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.003s

I tried to correct it like you told me in the comments :

% Generate
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).
% Define
reached(Y) :- cycle(1,Y).
reached(Y) :- cycle(X,Y), reached(X).
% Test
:- node(Y), not reached(Y).

% Nodes
%node(1..6).

node(street1..street6).

%node(street1).
%node(street2).
%node(street3).
%node(street4).
%node(street5).
%node(street6).
%node(street1;street2;street3;street4;street5;street6).

% (Directed) Edges
edge(street1,(street2;street3;street4)).  
edge(street2,(street4;street5;street6)).  
edge(street3,(street1;street4;street5)).
edge(street4,(street1;street2)).    
edge(street5,(street3;street4;street6)).  
edge(street6,(street2;street3;street5)).

% Edge Costs
cost(street1,street2,2).  cost(street1,street3,3).  cost(street1,street4,1).
cost(street2,street4,2).  cost(street2,street5,2).  cost(street2,street6,4).
cost(street3,street1,3).  cost(street3,street4,2).  cost(street3,street5,2).
cost(street4,street1,1).  cost(street4,street2,2).
cost(street5,street3,2).  cost(street5,street4,2).  cost(street5,street6,1).
cost(street6,street2,4).  cost(street6,street3,3).  cost(street6,street5,1).


% Optimize minimum cost and cycle 
#minimize { C,X,Y : cycle(X,Y), cost(X,Y,C) }.

% Display
#show cycle/2.

and I got this result:

clingo version 5.4.0
Reading from cleaning_street_names.lp4
cleaning_street_names.lp4:30:6-22: info: interval undefined:
  street1..street6

Solving...
Answer: 1

SATISFIABLE

Models       : 1
Calls        : 1
Time         : 0.002s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.002s

(if I put node(1..6). the result it's UNSATISFIABLE)

Answer 1

The problem is here in this piece of code:

{ cycle(X,Y) : edge(X,Y) } = street1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = street1 :- node(Y).

You have replaced the 1 by the atom street1.

But 1 in the original program is not an identifier for a "street" (more like an intersection: nodes are intersections, edges are streets because conceptually it is difficult to reach one street from another street in a one-way fashion with an affixed cost, isn't it?), but a value: It is the cardinality constraint. The correct expression is:

{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).

which expresses that:

For any ground fact cycle(X,Y) in the answer set:

• there must be a corresponding edge(X,Y)
• there must be exactly 1 of cycle(X,Y) for any X
• there must be exactly 1 of cycle(X,Y) for any Y

I don't know why clingo doesn't protest? I haven't tried to run this.

"Hamiltonian" cycle or "Chinese Postman Problem" cycle?

Note that you write;

The above problem can be modeled by representing the map of the city with a directed graph and the challenge is to visit all the edges (ie roads) at least once

This is exactly right: The edges are the roads/streets, so it is conceptually wrong (though syntactically equivalent) to relabel nodes called 1..6 as street1..street6.

The program as given then proceeds to solve the Hamiltonian Path problem (every node visted exactly once) whereas it should solve the (comnplexity-wise simpler) Route Inspection/Chinese Postman problem (every edge visited at least once, optimally exactly once).

The original's program's constraint

{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).

expresses a constraint for a Hamiltonian Path (not yet a Hamiltonian Cycle starting and ending at the same node, just a path). For any node, there is exactly one incoming edge that belongs to the cycle and there is exactly one outgoing edge that belongs to the cycle. Hence, every node is visited exactly once => Hamiltonian Path.

(I wonder if reached is superfluous? If not, why not?)

Graph of the original Problem

• Nodes are blue circles.
• Costs are white ovals.
• Start node for cycle is 1.
• Arrows indicate how the edge can be traversed (as is the custom)
• One solution indicated.

Update: My attempt at ASP

This ASP stuff is tricky. I'm not sure how to express the problem properly. A big problem is that we don't know how deep to search, and the only way I have found to attack that is to run the program with successively larger max_time values until SATISFIABLE is output. The problem is that we generate possible paths with "exactly one literal at every time T" through

1 { path(e(X,Y),t(T)) : edge(X,Y) } 1 :- time(T).

these sets of path/2 literals are then checked against constraints. Unlike in Prolog, we thus cannnot "terminate when we reach node 1 and all edges have been visited". How is this done correctly? I though about "parking the path" on a edge(1,1) with cost 0 at the end, but this makes the program messy and I didn't succeed in specifying a global constraint about the path structure, which then consists of a "good part", a "hit node 1 one last time" and a "tail part to be disregarded".

% ===
% Attempt at the "Chinese Postman Problem" / "Route Inspection Problem"
% ===
% https://en.wikipedia.org/wiki/Route_inspection_problem

% Original statement:
%
% "Find a shortest closed path or circuit that visits every edge of an
% (connected) undirected graph."
%
% Here:
%
% "Find a closed path (cycle) starting from node 1 that visits every pair
% (X,Y) of nodes of a directed graph where that pair is connected by an edge
% (X->Y) or (Y->X) or both. Every edge has an associated
% cost. Find the cycle with the minimum cost."
%
% "max_time" is the length of the resulting path. Sadly, one has to manually
% reduce "max_time" in a stepwise fashion until the shortest path is found.
% How can that be done programmatically?

#const max_time=13.

time(1..max_time).

% ---
% Generating part
% ---

% For every time "T", there is exactly one path/2 literal indicating that
% the path element for time T goes via edge(X,Y).

1 { path(e(X,Y),t(T)) : edge(X,Y) } 1 :- time(T).

% ---
% Defining part
% ---

% "Start at node 1", alias:
% "The path/2 literal for time=1 cannot be based on an edge/2 literal that
% does not start at node 1"

:- path(e(X,Y),t(1)), edge(X,Y), X!=1.

% "Path literals must be connected", alias
% "The path/2 literals for time=T and time=T+1 cannot have edges ending and
% starting at different nodes"

:- path(e(X,N1),t(T)), path(e(N2,Y),t(TT)), TT=T+1, N1!=N2.

% "Every street must have been visited at least once before time T", alias:
% "It is not possible for edge/2 to exist between node pair (X,Y) and
% visited(X,Y) not to be true"
% and 
% "visited(X,Y) is true if edge(X,Y) or the edge(Y,X) (or both) are the path"

visited(X,Y,T) :- time(T),path(e(X,Y),t(Tx)), Tx <= T.
visited(X,Y,T) :- time(T),path(e(Y,X),t(Tx)), Tx <= T.

:- edge(X,Y), not visited(X,Y,max_time).

% "The path must be a cycle, returning to node 1 at exactly max_time"

:- path(e(X,Y),t(max_time)), Y!=1.

% Compute cumulative cost of path

acc_cost(C,1) :- path(e(X,Y),t(1)),cost(edge(X,Y),C).
acc_cost(C,T) :- time(T),T>1,path(e(X,Y),t(T)),cost(edge(X,Y),Cx),Tp=T-1,acc_cost(Cp,Tp),C=Cp+Cx.

% ---
% Define the graph itself
% ---

% Nodes are street intersections, just labeled node(1) .. node(6).
% Note that this is different from using atoms as names as in 
% node_1, node_2, ....
% What we are saying here is that "certain integers 1 ... 6 can appear
% as labels of nodes" or "integer  1 ... 6 have the attribute 'node'"

node(1..6).

% Directed edges are streets, linking the nodes, i.e. the intersections.
% If there is an edge A->B and an edge B->A then it's a two-way-street.
% If there is an edge A->B but no edge B->A then it's a one-way street.
% What we are saying here is that "certain tuples of integers (X,Y) can
% appear as labels of 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)).

% Not made explicit is the fact that X and Y in edge(X,Y) must be labels
% of nodes. For good measure, we add an integrity constraint. Also,
% disallow reflexivity.

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

% Driving down a street has a cost, so associate a cost with each edge.
% Let's be explicit in naming and use the "edge/2" predicate inside of the
% cost/2 predicate.

cost(edge(1,2),2).  cost(edge(1,3),3).  cost(edge(1,4),1).
cost(edge(2,4),2).  cost(edge(2,5),2).  cost(edge(2,6),4).
cost(edge(3,1),3).  cost(edge(3,4),2).  cost(edge(3,5),2).
cost(edge(4,1),1).  cost(edge(4,2),2).
cost(edge(5,3),2).  cost(edge(5,4),2).  cost(edge(5,6),1).
cost(edge(6,2),4).  cost(edge(6,3),3).  cost(edge(6,5),1).

:- cost(edge(X,Y),C), not edge(X,Y).
:- edge(X,Y), not cost(edge(X,Y),_).
:- cost(edge(X,Y),C1), cost(edge(Y,X),C2), C1 != C2.

% ---
% Optimization
% ---

#minimize { C: acc_cost(C,max_time) }.

% ---
% Displaying part
% ---

#show path/2.
% #show acc_cost/2.

So by setting max_time to 13, we find:

Solving...
Answer: 1
path(e(1,3),t(1)) path(e(3,1),t(2)) path(e(1,2),t(3))
path(e(2,5),t(4)) path(e(5,4),t(5)) path(e(4,2),t(6))
path(e(2,6),t(7)) path(e(6,3),t(8)) path(e(3,5),t(9))
path(e(5,6),t(10)) path(e(6,3),t(11)) path(e(3,4),t(12))
path(e(4,1),t(13))
Optimization: 30
OPTIMUM FOUND

And this looks as follows:

Nice.

Answer 2

Inspired from a change of @David I did it we have 2 answers!

%hamilltonian cycles

% Generate
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).
% Define
cleaned(Y) :- cycle(X,Y).
cleaned(Y) :- cycle(X,Y), cleaned(X).
% Test
:- node(Y), not cleaned(Y).

% Nodes
%node(1..6).
%node(street1..street6).

node(street1;street2;street3;street4;street5;street6).


% (Directed) Edges
edge(street1,(street2;street3;street4)).  
edge(street2,(street4;street5;street6)).  
edge(street3,(street1;street4;street5)).
edge(street4,(street1;street2)).    
edge(street5,(street3;street4;street6)).  
edge(street6,(street2;street3;street5)).

% Edge Costs
cost(street1,street2,2).  cost(street1,street3,3).  cost(street1,street4,1).
cost(street2,street4,2).  cost(street2,street5,2).  cost(street2,street6,4).
cost(street3,street1,3).  cost(street3,street4,2).  cost(street3,street5,2).
cost(street4,street1,1).  cost(street4,street2,2).
cost(street5,street3,2).  cost(street5,street4,2).  cost(street5,street6,1).
cost(street6,street2,4).  cost(street6,street3,3).  cost(street6,street5,1).


% Optimize minimum cost and cycle 
#minimize { C,X,Y : cycle(X,Y), cost(X,Y,C) }.

% Display
#show cycle/2.

Running the above

Solving...
Answer: 1
cycle(street1,street4) cycle(street2,street5) cycle(street3,street1) cycle(street4,street2) cycle(street5,street6) cycle(street6,street3)
Optimization: 12
Answer: 2
cycle(street1,street2) cycle(street2,street4) cycle(street3,street5) cycle(street4,street1) cycle(street5,street6) cycle(street6,street3)
Optimization: 11
OPTIMUM FOUND

The graph for the second answer above is not connected: