Hi Halit, You should find the description of a propagator for this constraint on undirected graphs (as a sub-component of a larger propagator) in this paper: http://www.springerlink.com/content/25503116766r373x/ In summary, a simple propagator consists in doing a DFS in the graph of all possible edges and computing all bridges and cutnodes. Include those which join two biconnected components which you know belong to the graph must belong to the graph. Discard the connected components which are disjoint from the main connected component of your graph.
Best, -- Greg On Tue, May 19, 2009 at 8:47 AM, Christian Schulte <[email protected]> wrote: > 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/<http://www.ict.kth.se/%7Ecschulte/> > > > -----Original Message----- > From: [email protected] [mailto:[email protected]] On Behalf > Of Halit Erdogan > Sent: Monday, May 18, 2009 6:42 PM > To: [email protected] > 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 : [email protected] > phone : +90 505 476 75 76 > webpage : > http://students.sabanciuniv.edu/~halit/<http://students.sabanciuniv.edu/%7Ehalit/> > > _______________________________________________ > Gecode users mailing list > [email protected] > https://www.gecode.org/mailman/listinfo/gecode-users > > > _______________________________________________ > Gecode users mailing list > [email protected] > https://www.gecode.org/mailman/listinfo/gecode-users >
_______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
