[gecode-users] Graph Connectivity Problem

[Grégoire Dooms]

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 <cschulte at kth.se> 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: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
> Of Halit Erdogan
> Sent: Monday, May 18, 2009 6:42 PM
> To: users at 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   : halit at su.sabanciuniv.edu
> phone   : +90 505 476 75 76
> webpage : http://students.sabanciuniv.edu/~halit/<http://students.sabanciuniv.edu/%7Ehalit/>
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>
>
> _______________________________________________
> 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.ps.uni-sb.de/pipermail/users/attachments/20090519/04da3de5/attachment.htm>