Prolog - CLP(FD) Prolog: help needed with a simple problem

Author

CLP(FD) Prolog: help needed with a simple problem

Chema

2005-03-20, 3:57 am

Hi everybody.
I'm a Prolog user, but newbie in constrain programming using
CLP(FD) (with sicstus prolog).

I'm looking for good documentation and examples, unluckily, right
now, I've found a bit useful only sicstus manual.
Can anybody suggest me some good link?

I've to solve a simple problem: given a Graph, find out its
spanning tree. I can do it in Prolog, but I've no idea in CLP.
Any suggestion is welcome (I don't want code, just an idea).

Thanks in advance

Best regards

Chema

Markus Triska

2005-03-21, 3:57 am

Chema wrote:

> I've to solve a simple problem: given a Graph, find out its
> spanning tree. I can do it in Prolog, but I've no idea in CLP.
> Any suggestion is welcome (I don't want code, just an idea).

One way would be to introduce a variable X_e in 0..1 for each edge e
(denoting whether it is to be an element of the ST), state that the sum
over all these variables must equal |V| - 1, and add additional
constraints to prevent cycles.

All the best,
Markus.

Markus Triska

2005-03-21, 3:57 am

Chema

2005-03-25, 3:58 pm

> One way would be to introduce a variable X_e in 0..1 for each edge e
> (denoting whether it is to be an element of the ST), state that the sum
> over all these variables must equal |V| - 1, and add additional
> constraints to prevent cycles.

Thank you for your replay and suggestion.
The problem is just to find this constraints.
Using this kind of integer programming, I only know if edge X is
in the spanning tree (1) or not (0), but I have not realized yet
a way for knowing from which node to wich node edge X goes.
Right now, I've used a kind of incidence matrix, then I've
imposed that for each node u, uv in edge, sum x_uv = 1 (exactly
one edge have to enter in a node, except root), but that doesn't
prevent cycles.

Chema

Markus Triska

2005-03-25, 3:58 pm

Chema wrote:

> Right now, I've used a kind of incidence matrix, then I've
> imposed that for each node u, uv in edge, sum x_uv = 1 (exactly
> one edge have to enter in a node, except root), but that doesn't
> prevent cycles.

I hope you find the following code useful - it is easily adjustable to
other representations:

% example graph
edge(e1,1,2).
edge(e2,2,3).
edge(e3,3,1).
edge(e4,1,4).
edge(e5,3,4).

cycle(Es) :-
reachable(X,X,[],Es).

reachable(X,Y,Visited0,Visited) :-
edge(E,X,Y),
append(Visited0,[E],Visited).
reachable(X,Y,Visited0,Visited) :-
edge(E,X,Z),
\+ member(E,Visited0),
append(Visited0,[E],Visited1),
reachable(Z,Y,Visited1,Visited).

Now you can query the edges that participate in a (directed) cycle:

?- setof(Es,cycle(Es),Ess).

Es = _G180
Ess = [[e1, e2, e3], [e2, e3, e1], [e3, e1, e2]] ;

(More work is needed to limit equivalent cycles to one representative
for each equivalence class.)

Hence, you can bound the sum over the (0/1-)edges participating in a
cycle C to |C| - 1.

All the best,
Markus.

Bart Demoen

2005-03-25, 3:58 pm

Chema wrote:
>
>
>
> Thank you for your replay and suggestion.
> The problem is just to find this constraints.
> Using this kind of integer programming, I only know if edge X is
> in the spanning tree (1) or not (0), but I have not realized yet
> a way for knowing from which node to wich node edge X goes.
> Right now, I've used a kind of incidence matrix, then I've
> imposed that for each node u, uv in edge, sum x_uv = 1 (exactly
> one edge have to enter in a node, except root), but that doesn't
> prevent cycles.
>
> Chema

You prevent cycles by imposing the constraint that each node is on at least
edge in the subgraph.
E.g.

/*

think of a graph with edges (a,b) (a,c) (b,c)

as [A-[AB,AC], B-[AB,BC], C-[AC,BC]] (just another representation of
the incidence matrix)

the part A- is actually redundant - just a reminder that you
group de edges by node

now impose:

[AB,AC,BC] in 0..1

and the condition that AB+AC+CD = (|V|-1) (2 in this case)

and AB=1 \/ AC=1 && AB=1 \/ BC=1 && AC=1 \/ BC=1

in SW-Prolog this would become ...

*/

:- use_module(library('clp/bounds')).

t([AB,AC,BC]) :-
[AB,AC,BC] in 0..1,
AB+AC+BC #= 2,
AB+AC #>= 1,
AB+BC #>= 1,
AC+BC #>= 1,
label([AB,AC,BC]).

Generalize that to any graph.

Cheers

Bart Demoen

Chema

2005-03-29, 8:58 am

Bart Demoen wrote:

> now impose:
>
> [AB,AC,BC] in 0..1
>
> and the condition that AB+AC+CD = (|V|-1) (2 in this case)
>
> and AB=1 \/ AC=1 && AB=1 \/ BC=1 && AC=1 \/ BC=1

I got the point, but the problem is: I've to impose this kind of
condition for each subgraph. Consider an undirected graph G=(V,E)
with E = (a,b), (b,c), (c,d), (d,h), (e,h), (a,e), (b,e), (b,h),
(c,h), (e,f), (f,h), (h,g), (d,g), (f,g)
You see, I should include at least two constrains for each cycle.
This is an NP hard problem, and this constrains grow in an
esponential way... I can't do that "manually".

An idea should be Markus's one, to query in "standard" prolog
cycles in G, but now my problem is: if I query the edges that
participate in a cycle, I get a "grounded" answer, not variables
anymore. And I can I set a domain [0..1] in a grounded set?

I'm

:-)

Anyway, thank you for your help.

Regards

Bart Demoen

2005-03-29, 8:58 am

Chema wrote:

> I got the point, but the problem is: I've to impose this kind of
> condition for each subgraph. Consider an undirected graph G=(V,E)
> with E = (a,b), (b,c), (c,d), (d,h), (e,h), (a,e), (b,e), (b,h),
> (c,h), (e,f), (f,h), (h,g), (d,g), (f,g)
> You see, I should include at least two constrains for each cycle.
> This is an NP hard problem, and this constrains grow in an
> esponential way... I can't do that "manually".

Let's first get things straight: you are trying to solve the problem
"given a graph, find a spanning tree"
That problem is not NP hard. The algorithms of Kruskal and Prim give
you a minimal spanning tree in a weighted graph in polynomial
time. You can use these algorithms with weight 1 for each edge. Those
algorithms avoid cycles, but not by trying to represent each of
them explicitly.

You want to solve CLP for solving that problem - fine. Don't set up
constraints for cycles. There is some simple piece of graph theory that
says: for a connected graph with n nodes, the spanning tree contains
(n-1) edges and of course also the n nodes.
So the following will work: give a distinct variable name to every edge,
say Ei, and keep track for each node Vi on which edges it lies;
now generate the constraints

all Ei in [0,1]
the sum of all Ei equals n-1
for every Vi there is some Ej (which Vi lies on) which is 1

That's the generalisation of what I wrote for the very simple example.
The structure of your program could be something like:

st(Edges) :-
all_edges(Edges),
all_nodes_on_edges(Edges,NodesOnEdges),
length(NodesOnEdges,N),
Edges in 0..1,
sum(Edges,N-1),
foreach(Node-ItsEdges,member(Node- ItsEdges,NodesOnEdges),(sum(ItsEdges,M),
M>0)),
label(Edges).

Code not tested. You still need to keep track of the association between
the edge variables and the actual edges (I ignored that completely above).

Cheers

Bart Demoen

Sponsored Links