[gecode-users] Reachability in a graph structure.

[Tobias Pankrath]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: main.cpp
Type: text/x-c++src
Size: 2278 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20140110/a0ab20aa/attachment-0001.cpp>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: t.dot.pdf
Type: application/pdf
Size: 11061 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20140110/a0ab20aa/attachment-0001.pdf>