Home > Archive > Prolog > August 2005 > propagation for the cycle constraint
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
propagation for the cycle constraint
|
|
| Neng-Fa Zhou 2005-08-09, 10:01 pm |
|
Hi,
I am implementing the cycle constraint in B-Prolog.
cycle(L):
L a list of variables X1,X2,...,Xn in the domain of 1..n. A valuation
for the variables
X1->a1,X2->a2,...,Xn->an must form a Hamilton cycle. For example,
cycle([X,Y,Z]) has two solutions: [2,3,1] and [3,1,2].
Here is my current implementation:
cycle(L):-
all_distinct(L),
no_subcycle(L).
where all_distinct(L) maintains a weak-form of hyper-arc consistency and
no_subcylce(L) ensures that the end of any path cannot be connected to the
start unless the path is of length n. Does anybody know any better
propagation algorithms for this constraint? I know that the propagation
would be more powerful if Regin's filtering algorithm is used for
all_distinct, but the algorithm seems not easy to implement.
Cheers,
--Neng-Fa
| |
| Luis Quesada 2005-08-10, 5:06 pm |
| It seems that my first message did not make it. It must be for the size
of the attachment. Sorry for that!
Neng-Fa Zhou wrote:
> Hi,
>
> I am implementing the cycle constraint in B-Prolog.
>
> cycle(L):
> L a list of variables X1,X2,...,Xn in the domain of 1..n. A valuation
> for the variables
> X1->a1,X2->a2,...,Xn->an must form a Hamilton cycle. For example,
> cycle([X,Y,Z]) has two solutions: [2,3,1] and [3,1,2].
>
You might be interested in having a look at Bourreau's PhD thesis (I got
a soft-copy of the document in case you are interested). The thesis
presents the implementation of the cycle constraint in CHIP and its
applications in several domains. However, the algorithms have been
dropped for confidential reasons...
I have tried to contact the author but he seems to be unreachable.
> Here is my current implementation:
>
> cycle(L):-
> all_distinct(L),
> no_subcycle(L).
>
> where all_distinct(L) maintains a weak-form of hyper-arc consistency and
> no_subcylce(L) ensures that the end of any path cannot be connected to the
> start unless the path is of length n. Does anybody know any better
> propagation algorithms for this constraint? I know that the propagation
> would be more powerful if Regin's filtering algorithm is used for
> all_distinct, but the algorithm seems not easy to implement.
We have been working on a related problem: Simple path with mandatory
nodes (SPMN). It is related because Hamiltonian path is a specific case
of SPMN. SPMN is Hamiltonian Path if all the nodes are mandatory.
However, SPMN can not be trivially reduced to Hamiltonian Path
(http://www.info.ucl.ac.be/~luque/CICLOPS2005/paper.pdf).
In fact, I would like to take advantage of this opportunity to raise the
following issue: our propagator is based on the computation of cut nodes
and bridges in *directed* graphs. A drawback of our approach is that cut
nodes and bridges are computed from scratch in each propagation step, so
we would like to find an incremental way of computing this.
Let me be more precise about the (non-incremental) algorithm that we
currently have: we need to compute the vector CN, where
CN(i)=CutNodes(g,source,i) (i.e., the set of vertexes appearing in all
paths from source to i in the directed graph g). The algorithm that we
have is the following:
T0:=DFS(g,source)
for i \in vertexes(g) do
CN(i):= if i \in vertexes(T0) then \emptyset else vertexes(g) end
end
for i \in vertexes(T0) do
T1:=DFS(RemoveVertex(g,i),source)
for j \in vertexes(T0)-vertexes(T1) do
CN(j):=CN(j) \cup {i}
end
end
Assume that DFS returns the reachability tree. CN(i) is initialized with
\emptyset or vertexes(g) depending on whether i is reached from the
source (the point is that, under our definition, any vertex is a cut
node between the source and i if i is not reached from the source).
Then, we simply try each potential cut node and update the corresponding
sets. So our computation of cut nodes is O(V*(V+E)).
Actually, our computation of bridges is O(V*(V+E)) too since we only
consider the edges in the reachability tree (whose cardinality is
proportional to |V|). Indeed, we take advantage of the fact that e \in
Bridges(g,source,i) implies that e \in edges(DFS(g,souce)):
T0:=DFS(g,source)
for i \in vertexes(g) do
BE(i):= if i \in vertexes(T0) then \emptyset else edges(g) end
end
for e \in edges(T0) do
T1:=DFS(RemoveEdge(g,e),source)
for i \in vertexes(T0)-vertexes(T1) do
BE(i):=BE(i) \cup {e}
end
end
However, as mentioned before, these two algorithms are not incremental.
How can I update CN and BE after removing a set of edges without
starting from scratch?
I think one way is by implementing DFS incrementally since we only need
to look at the DFS tree. But I still don't know how to implement DFS
incrementally...
Luis
| |
|
| On Wed, 10 Aug 2005 22:13:10 +0200, Luis Que a
<luque@info.ucl.ac.be> wrote:
>
>
>You might be interested in having a look at Bourreau's PhD thesis (I got
>a soft-copy of the document in case you are interested). The thesis
>presents the implementation of the cycle constraint in CHIP and its
>applications in several domains. However, the algorithms have been
>dropped for confidential reasons...
Interesting... And he was able to defend the thesis with critical
algorithm "underground"?...
A.L.
| |
| Luis Quesada 2005-08-10, 10:02 pm |
| A.L. wrote:
> On Wed, 10 Aug 2005 22:13:10 +0200, Luis Quea
> <luque@info.ucl.ac.be> wrote:
>
>
>
>
> Interesting... And he was able to defend the thesis with critical
> algorithm "underground"?...
>
I put the copy I got from Hadrien Cambazard in:
http://www.info.ucl.ac.be/~luque/re...reau-THESIS.pdf
Luis
| |
| Neng-Fa Zhou 2005-08-12, 4:02 am |
| Hi Luis,
Thanks for your response. I don't know how your algorithm can be used in an
implementation of the cycle constraint. But certainly there is something
interesting in your algorithm that does not exist in Regin's algorithm. For
example, in Regin's algorithm arcs that do not belong to any maximum
matching are excluded from the bipartite graph, and on contrary, your
algorithm finds bridges that appear in all paths. The difficult part is that
your algorithm is not incremental but Regin's algorithm has an incremental
version.
After a little thought, I realized that my implementation of cycle can be
improved:
cycle(L):-
all_distinct_for_cycle(L),
no_subcycle(L).
all_distinct_for_cycle(L) is the same as all_distinct(L) except that it
fails immediately whenever a Hall set is found (A set is a Hall set if the
number of variables whose domains are subsets of the set is equal to the
size of the set). Can anybody propose further improvements upon this?
Cheers,
Neng-Fa
"Luis Quea" <luque@info.ucl.ac.be> wrote in message
news:42FA5FD6.2020203@info.ucl.ac.be...
> It seems that my first message did not make it. It must be for the size of
> the attachment. Sorry for that!
>
> Neng-Fa Zhou wrote:
>
> You might be interested in having a look at Bourreau's PhD thesis (I got a
> soft-copy of the document in case you are interested). The thesis presents
> the implementation of the cycle constraint in CHIP and its applications in
> several domains. However, the algorithms have been dropped for
> confidential reasons...
>
> I have tried to contact the author but he seems to be unreachable.
>
>
> We have been working on a related problem: Simple path with mandatory
> nodes (SPMN). It is related because Hamiltonian path is a specific case of
> SPMN. SPMN is Hamiltonian Path if all the nodes are mandatory. However,
> SPMN can not be trivially reduced to Hamiltonian Path
> (http://www.info.ucl.ac.be/~luque/CICLOPS2005/paper.pdf).
>
> In fact, I would like to take advantage of this opportunity to raise the
> following issue: our propagator is based on the computation of cut nodes
> and bridges in *directed* graphs. A drawback of our approach is that cut
> nodes and bridges are computed from scratch in each propagation step, so
> we would like to find an incremental way of computing this.
>
> Let me be more precise about the (non-incremental) algorithm that we
> currently have: we need to compute the vector CN, where
> CN(i)=CutNodes(g,source,i) (i.e., the set of vertexes appearing in all
> paths from source to i in the directed graph g). The algorithm that we
> have is the following:
>
> T0:=DFS(g,source)
> for i \in vertexes(g) do
> CN(i):= if i \in vertexes(T0) then \emptyset else vertexes(g) end
> end
> for i \in vertexes(T0) do
> T1:=DFS(RemoveVertex(g,i),source)
> for j \in vertexes(T0)-vertexes(T1) do
> CN(j):=CN(j) \cup {i}
> end
> end
>
> Assume that DFS returns the reachability tree. CN(i) is initialized with
> \emptyset or vertexes(g) depending on whether i is reached from the source
> (the point is that, under our definition, any vertex is a cut node between
> the source and i if i is not reached from the source). Then, we simply try
> each potential cut node and update the corresponding sets. So our
> computation of cut nodes is O(V*(V+E)).
>
> Actually, our computation of bridges is O(V*(V+E)) too since we only
> consider the edges in the reachability tree (whose cardinality is
> proportional to |V|). Indeed, we take advantage of the fact that e \in
> Bridges(g,source,i) implies that e \in edges(DFS(g,souce)):
>
> T0:=DFS(g,source)
> for i \in vertexes(g) do
> BE(i):= if i \in vertexes(T0) then \emptyset else edges(g) end
> end
> for e \in edges(T0) do
> T1:=DFS(RemoveEdge(g,e),source)
> for i \in vertexes(T0)-vertexes(T1) do
> BE(i):=BE(i) \cup {e}
> end
> end
>
> However, as mentioned before, these two algorithms are not incremental.
> How can I update CN and BE after removing a set of edges without starting
> from scratch?
>
> I think one way is by implementing DFS incrementally since we only need to
> look at the DFS tree. But I still don't know how to implement DFS
> incrementally...
>
> Luis
| |
| Luis Quesada 2005-08-12, 4:02 am |
| Hi Neng-Fa,
> Thanks for your response. I don't know how your algorithm can be used in an
> implementation of the cycle constraint.
I am assuming that we are reducing Hamiltonian Cycle to Hamiltonian Path
in the preprocessing phase, so I just speak about Hamiltonian Path.
My point is that Reachability could be a redundant constraint that can
anticipate violations of the subcycle constraint.
Let us consider the problem of finding a Hamiltonian path from node 1 to
node 52 in Figure 7 (in
http://www.info.ucl.ac.be/~luque/CICLOPS2005/paper.pdf). Let us also
assume that we are not helped by the labeling strategy (i.e., that we go
from the source to the destination considering the left most viable
successor). Without the extra-pruning that Reachability offers, you will
spend a while before realizing that there is not way of finding a
Hamiltonian path starting from the left most subgraph.
> But certainly there is something
> interesting in your algorithm that does not exist in Regin's algorithm. For
> example, in Regin's algorithm arcs that do not belong to any maximum
> matching are excluded from the bipartite graph, and on contrary, your
> algorithm finds bridges that appear in all paths. The difficult part is that
> your algorithm is not incremental but Regin's algorithm has an incremental
> version.
>
Fortunately, this will be soon no longer the case thanks to Eugene
Ressler. Yesterday, in comp.theory, he made me realize that our cut
nodes are actually dominators. Indeed, j \in CutNode(g,source,i) means
that j dominates i. So what we are computing are dominators trees.
The good news is that there are incremental algorithms for computing
these trees. And there are more efficient non-incremental algorithms
than the one I am currently considering.
Something that I noticed is that, if we replace the edges by new nodes
(and connect the new nodes accordingly), we only need to compute cut
nodes. So our computation of cut nodes and bridges reduces to computing
dominators trees.
Cheers,
Luis
| |
| Neng-Fa Zhou 2005-08-19, 4:18 pm |
| I agree with you. Reachability testing is important. I have implemented the
cycle constraint (called circuit/1) in B-Prolog 6.7 #4, which combines
hall-set testing with reachability testing. It works quite well on the
benchmarks I have.
I am curious about how reachability can be used to prune search space in a
priori way and how it can be done incrementally.
Cheers,
--Neng-Fa
"Luis Quea" <luque@info.ucl.ac.be> wrote in message
news:42FC5D4D.9040306@info.ucl.ac.be...
> I am assuming that we are reducing Hamiltonian Cycle to Hamiltonian Path
> in the preprocessing phase, so I just speak about Hamiltonian Path.
>
> My point is that Reachability could be a redundant constraint that can
> anticipate violations of the subcycle constraint.
>
> Let us consider the problem of finding a Hamiltonian path from node 1 to
> node 52 in Figure 7 (in
> http://www.info.ucl.ac.be/~luque/CICLOPS2005/paper.pdf). Let us also
> assume that we are not helped by the labeling strategy (i.e., that we go
> from the source to the destination considering the left most viable
> successor). Without the extra-pruning that Reachability offers, you will
> spend a while before realizing that there is not way of finding a
> Hamiltonian path starting from the left most subgraph.
>
>
> Fortunately, this will be soon no longer the case thanks to Eugene
> Ressler. Yesterday, in comp.theory, he made me realize that our cut nodes
> are actually dominators. Indeed, j \in CutNode(g,source,i) means that j
> dominates i. So what we are computing are dominators trees.
>
> The good news is that there are incremental algorithms for computing these
> trees. And there are more efficient non-incremental algorithms than the
> one I am currently considering.
>
> Something that I noticed is that, if we replace the edges by new nodes
> (and connect the new nodes accordingly), we only need to compute cut
> nodes. So our computation of cut nodes and bridges reduces to computing
> dominators trees.
>
> Cheers,
> Luis
| |
| Luis Quesada 2005-08-20, 7:57 am |
| The idea is to take advantage of the dynamic algorithms for computing
transitive closure and dominator trees.
In fact, we just submitted a paper where we explain our approach that is
basically based on three notions: graph variables, dominators and
transitive closure. In that paper we also show how we reduce the Ordered
disjoint path problem to the Ordered simple path problem with mandatory
nodes. Please send me a personal e-mail in case you are interested.
By the way, we decided to re-name the propagator. Now its name is
DomReachability (which sounds like Mr Reachability in Spanish :-)). The
point is that we decided to emphasize that this is not a simple
reachability constraint. This is a smart reachability constraint due to
the the computation of dominators.
Cheers,
Luis
Neng-Fa Zhou wrote:
> I agree with you. Reachability testing is important. I have implemented the
> cycle constraint (called circuit/1) in B-Prolog 6.7 #4, which combines
> hall-set testing with reachability testing. It works quite well on the
> benchmarks I have.
>
> I am curious about how reachability can be used to prune search space in a
> priori way and how it can be done incrementally.
>
> Cheers,
> --Neng-Fa
>
> "Luis Quea" <luque@info.ucl.ac.be> wrote in message
> news:42FC5D4D.9040306@info.ucl.ac.be...
>
>
>
>
>
>
| |
|
| On Sat, 20 Aug 2005 12:32:02 +0200, Luis Quea
<luque@info.ucl.ac.be> wrote:
>The idea is to take advantage of the dynamic algorithms for computing
>transitive closure and dominator trees.
>
>In fact, we just submitted a paper...
Where?...
A.L.
| |
| Luis Quesada 2005-08-23, 3:57 am |
| A.L. wrote:
> On Sat, 20 Aug 2005 12:32:02 +0200, Luis Quea
> <luque@info.ucl.ac.be> wrote:
>
>
>
>
> Where?...
>
PADL'06
Luis
| |
|
| On Tue, 23 Aug 2005 10:18:55 +0200, Luis Quea
<luque@info.ucl.ac.be> wrote:
>A.L. wrote:
>PADL'06
>
Is pdf/ps available?...
A.L.
| |
| Luis Quesada 2005-08-23, 7:00 pm |
| A.L. wrote:
>Is pdf/ps available?...
>
>
>
The submitted version is available at the following address:
http://www.info.ucl.ac.be/~luque/PADL06/paper.pdf
As I said before, in this paper we have reformulated our propagator.
DomReachability has now three arguments: (1) a flow graph, i.e., a
directed graph with a source node; (2) the dominance relation graph on
nodes and edges of the flow graph; and (3) the transitive closure of the
flow graph. Thanks to the existing dynamic algorithms for transitive
closure and dominator trees, DomReachability can be implemented
efficiently.
In this paper we have also reduced the ordered disjoint paths
problem(ODP) to the ordered simple path problem with mandatory nodes
(OSPMN) in order to show that OSPMN is indeed an interesting problem
since problems like ODP can be easily reduced to it.
Cheers,
Luis
| |
|
| On Tue, 23 Aug 2005 18:11:30 +0200, Luis Quea
<luque@info.ucl.ac.be> wrote:
>A.L. wrote:
>
>The submitted version is available at the following address:
>
>http://www.info.ucl.ac.be/~luque/PADL06/paper.pdf
Thx. There are more papers mentioned on your page in Bibliography
section and related to path problem. However, there are no pointers to
online version. Are at least some available as pdf/ps?...
A.L.
| |
| Luis Quesada 2005-08-23, 7:00 pm |
| A.L. wrote:
> On Tue, 23 Aug 2005 18:11:30 +0200, Luis Quea
>
> Thx. There are more papers mentioned on your page in Bibliography
> section and related to path problem. However, there are no pointers to
> online version. Are at least some available as pdf/ps?...
>
Indeed, my page is still under construction. I will make them available
in the near future.
Luis
|
|
|
|
|