Hi Halit, unfortunately there is no predefined constraint for that. There are two options for pulling that of: use reification or implement a propagator to enforce connectedness. I think I haven't seen a special constraint for that in any system.
Anyway, you might want to not encode that as 0/1 but set variables: in a sequence of n variables x, the set for x_n contains the adjacent nodes. That should be more efficient. If you are interested in building a propagator, that should be pretty easy. The implementation of the circuit constraint will give much of what needs to be done. Christian -- Christian Schulte, www.ict.kth.se/~cschulte/ -----Original Message----- From: users-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf Of Halit Erdogan Sent: Monday, May 18, 2009 6:42 PM To: us...@gecode.org Subject: [gecode-users] Graph Connectivity Problem Dear All, Although it seems a very common problem I could not find any information on forcing graph connectedness neither in documentation nor in the web archive. The problem is: I have a matrix "m" representing an undirected graph. m(i,j) = 1 means there is an edge between the vertices i and j. I want m to represent a connected graph (every pair of distinct vertices in the graph ( (i,j) in m) is connected through some path). How can I write this as a constraint in gecode? thanks in advance, -halit -- Halit Erdogan B.S. Sabanci University Computer Science and Engineering email : ha...@su.sabanciuniv.edu phone : +90 505 476 75 76 webpage : http://students.sabanciuniv.edu/~halit/ _______________________________________________ Gecode users mailing list us...@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users _______________________________________________ Gecode users mailing list us...@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
