5.52. circuit
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
circuit(NODES)
- Synonym(s)
- Argument(s)
-
NODES collection(index−int,succ−dvar) - Restriction(s)
-
required(NODES,[index,succ]) NODES.index≥1 NODES.index≤|NODES| distinct(NODES,index) NODES.succ≥1 NODES.succ≤|NODES| - Purpose
Enforce to cover a digraph G described by the NODES collection with one circuit visiting once all vertices of G.
- Example
-
(
)〈
〉index−1 succ−2, index−2 succ−3, index−3 succ−4, index−4 succ−1 The circuit constraint holds since its NODES argument depicts the following Hamiltonian circuit visiting successively the vertices 1, 2, 3, 4 and 1.
- Remark
In the original circuit constraint of CHIP the index attribute was not explicitly present. It was implicitly defined as the position of a variable in a list.
Within the context of linear programming [AlthausBockmayrElfKasperJungerMehlhorn02] this constraint was introduced under the name atour. In the same context [Hooker07book] provides continuous relaxations of the circuit constraint.
Within the KOALOG constraint system this constraint is called cycle.
- Algorithm
Since all succ variables of the NODES collection have to take distinct values one can reuse the algorithms associated with the alldifferent constraint. A second necessary condition is to have no more than one strongly connected component. When the number of vertices is odd (i.e., |NODES| is odd) a third necessary condition is to have a bipartite graph (see the Algorithm slot of the bipartite constraint).
Further necessary conditions (useful when the graph is sparse) combining the fact that we have a perfect matching and one single strongly connected component can be found in [ShufetBerliner94]. These conditions forget about the orientation of the arcs of the graph and characterise new required elementary chains. A typical pattern involving four vertices is depicted by Figure 5.52.1 where we assume that:
There is an elementary chain between c and d (depicted by a dashed arc),
b has exactly 3 neighbours.
In this context the edge between a and b is mandatory in any covering (i.e., the arc from a to b or the arc from b to a) since otherwise a small circuit involving b, c and d would be created.
Figure 5.52.1. Reasoning about elementary chains and degrees: if we have an elementary chain between c and d and if b has 3 neighbours then the edge (a,b) is mandatory.
When the graph is planar [HopcroftTarjan74][Deo76] one can also use as a necessary condition discovered by Grinberg [Grinberg68] for pruning.
Finally, an other approach based an the notion of 1 -toughness [Chvatal73] was proposed in [KayaHooker06] and evaluated for small graphs (i.e., graphs with up to 15 vertices).
- Systems
- See also
- Key words
combinatorial object: permutation.
constraint type: graph constraint, graph partitioning constraint.
filtering: linear programming, planarity test, DFS-bottleneck.
- Arc input(s)
NODES
- Arc generator
-
CLIQUE↦collection(nodes1,nodes2) - Arc arity
-
2 - Arc constraint(s)
-
nodes1.succ=nodes2.index - Graph property(ies)
-
• MIN_NSCC=|NODES| • MAX_ID=1 - Graph class
-
ONE_SUCC
- Graph model
The first graph property enforces to have one single strongly connected component containing |NODES| vertices. The second graph property imposes to only have circuits. Since each vertex of the final graph has only one successor we don't need to use set variables for representing the successors of a vertex.
Parts (A) and (B) of Figure 5.52.2 respectively show the initial and final graph associated with the Example slot. The circuit constraint holds since the final graph consists of one circuit mentioning once every vertex of the initial graph.
Figure 5.52.2. Initial and final graph of the circuit constraint
(a) (b) - Signature
Since the initial graph contains |NODES| vertices the final graph contains at most |NODES| vertices. Therefore we can rewrite the graph property MIN_NSCC=|NODES| to MIN_NSCC≥|NODES|. This leads to simplify to .
Because of the graph property MIN_NSCC=|NODES| the final graph contains at least one vertex. Since a vertex v belongs to the final graph only if there is an arc that has v as one of its extremities the final graph contains at least one arc. Therefore MAX_ID is greater than or equal to 1. So we can rewrite the graph property MAX_ID=1 to MAX_ID≤1. This leads to simplify to .