[gecode-users] Reachability in a graph structure.
Jean-Noël Monette
jean-noel.monette at it.uu.se
Fri Jan 10 13:47:07 CET 2014
Hi,
I think that the element constraint does not exactly encode your
purpose. You write:
y ? g1_reach[x] and z ? g1_reach[y] ==> z ? g1_reach[x]
while your element constraint represents something like (if I am correct)
y ? g1_reach[x] and z ? g1_reach[y] <=> z ? g1_reach[x]
i.e., this is an equivalence.
I do not know why you would have thousands of solution, though. Neither
why they do not respect the "superset" constraint.
Hope it helps anyway,
JN Monette
On 01/10/2014 10:35 AM, Tobias Pankrath wrote:
> Hello,
>
> I'm quite new to constraint programming and gecode in particular and
> ran into some issue
>
> I have to directed graphs G1=(V1,V1×V1), G2=(V2, V2×V2) and I am
> searching for a mapping h: V1 ? V2, that mantains reachability. I.e.
> if there is a path v1 -*> v2 (v1,v2 ? V1) than there must also be a
> path h(v1) -*> h(v2).
>
> To model this using gecode, I am using 4 SetVarArrays:
>
> SetVarArray g1_edges; // y ? g1_edges[x]: there is an edge from v_x to
> v_y in G1
> SetVarArray g2_edges; // like above for G2
>
> SetVarArray g1_reach; // y ? g1_reach[x]: there is a path from v_x to
> v_y in G1
> SetVarArray g2_reach; // like above for G2.
>
> Now I want gecode to calculate the reachability of those graphs. Thus
> I tried to fix the graph by the following domain constraints. A
> picture of the desired graph is attached to this mail.
>
> // define edges between nodes
> dom(*this, g1_edges[0], SRT_EQ, IntSet(1, 2));
> dom(*this, g1_edges[1], SRT_EQ, 5 );
> dom(*this, g1_edges[2], SRT_EQ, IntSet(3,4));
> dom(*this, g1_edges[3], SRT_EQ, 5);
> dom(*this, g1_edges[4], SRT_EQ, 5 );
> dom(*this, g1_edges[5], SRT_EQ, IntSet::empty);
>
> Then I want to encode the following relations:
> * y ? g1_reach[x], if y ? g1_edges[x] (direct neighbours)
> * if y ? g1_reach[x] and z ? g1_reach[y] then z ? g1_reach[x]
> (transitivity)
>
> Thus I do:
> for(int x = 0; x < 6; ++x)
> {
> rel(*this, g1_reach[x] >= g1_edges[x]); // superset
> element(*this, g1_reach, SOT_UNION, g1_reach[x], g1_reach[x]);
> // call to element taken from the manual, section 5.2.4
> // is it correct?
> }
>
> Then I'll branch on g1_reach, like this:
> branch(*this, g1_reach, SET_VAR_NONE(), SET_VAL_MIN_INC());
>
> However this gives me a >1000 solutions and all look like
> g1_edges {{1,2}, {5}, {3,4}, {5}, {5}, {}}
> g1_reach {}
>
> What is the correct way to model this?
>
> With my best regards,
> Tobias
>
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20140110/3256210c/attachment.html>
More information about the users
mailing list