[gecode-users] Graph Connectivity Problem
Christian Schulte
cschulte at kth.se
Tue May 19 09:47:06 CEST 2009
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-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/
_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
More information about the gecode-users
mailing list