5.381. strongly_connected
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Argument
- Restrictions
- Purpose
Consider a digraph described by the collection. Select a subset of arcs of so that we have a single strongly connected component involving all vertices of .
- Example
-
The constraint holds since the collection depicts a graph involving a single strongly connected component (i.e.,Β since we have a circuit visiting successively the vertices 1, 2, 3, 5, and 4).
- Typical
- Symmetry
Items of are permutable.
- Algorithm
The sketch of a filtering algorithm for the constraint is given inΒ [Dooms06].
- See also
common keyword: Β (constraint involving set variables).
related: Β (one single strongly connected component in the final solution).
- Keywords
constraint arguments: constraint involving set variables.
constraint type: graph constraint.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
PartΒ (A) of FigureΒ 5.381.1 shows the initial graph from which we start. It is derived from the set associated with each vertex. Each set describes the potential values of the attribute of a given vertex. PartΒ (B) of FigureΒ 5.381.1 gives the final graph associated with the Example slot. The constraint holds since the final graph contains a single strongly connected component mentioning every vertex of the initial graph.
Figure 5.381.1. Initial and final graph of the set constraint
(a) (b) - Signature
Since the maximum number of vertices of the final graph is equal to we can rewrite the graph property to and simplify to .