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

From: Bart Demoen (bmd_at_cs.kuleuven.ac.be)
Date: 03/25/05 

Date: Fri, 25 Mar 2005 16:52:04 +0100

Chema wrote:
>
>> 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

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

Relevant Pages

  • Re: circular relationships ok?
    ... So you DO allow constraints that are cyclical. ... Concept graph visualizes what the database will manage and nothing else. ... if A reference B then we draw an upward arrow from A to B. ... may have any structure including cycles. ...
    (comp.databases.theory)
  • Re: circular relationships ok?
    ... So you DO allow constraints that are cyclical. ... Concept graph visualizes what the database will manage and nothing else. ... if A reference B then we draw an upward arrow from A to B. ... may have any structure including cycles. ...
    (comp.databases.theory)
  • Re: CLP(FD) Prolog: help needed with a simple problem
    ... >, state that the sum ... > constraints to prevent cycles. ... Thank you for your replay and suggestion. ... The problem is just to find this constraints. ...
    (comp.lang.prolog)
  • Re: circular relationships ok?
    ... We still can impose any constraints just ... The only difference is that we avoid cycles in referencing. ... In RM, foreign key references ARE ... same cycles in constraints but you call them "indirect" for some ...
    (comp.databases.theory)
  • Re: circular relationships ok?
    ... on the other hand don't seem to model constraints - they show something ... This can be viewed as a reference structure: if A reference B then we draw an upward arrow from A to B. You are probably talking about informal relationships in the sense of ER model. ... Since these relationships are not managed by the database they may have any structure including cycles. ...
    (comp.databases.theory)