[gecode-users] Graph Connectivity Problem

[Denys Duchier]

Halit Erdogan <halit at su.sabanciuniv.edu> writes:

> 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?

You could use the set-based encoding which I have been using for years.
The idea is to model the notions of successors -> and its transitive ->+
and reflexive transitive ->* closures.

Let V be the set of all nodes, and ->(w) be the set of immediate
successors of node w.

    ->+(w) = \cup< ->*(w') | w'\in V >[->(w)]

the above uses the "union select" constraint (one instance of gecode's
"element" constraint on set variables).

    ->*(w) = {w} \cup ->+(w)
or  ->*(w) = {w} \uplus ->+(w) if the graph should be acyclic

if the graph is undirected and connected:

    ->*(w) = V  \forall w \in V

since all nodes must be reachable from any node.

Cheers,

--Denys