5.89. cycle

DESCRIPTIONLINKSGRAPH
Origin

[BeldiceanuContejean94]

Constraint

πšŒπš’πšŒπš•πšŽ(π™½π™²πšˆπ™²π™»π™΄,π™½π™Ύπ™³π™΄πš‚)

Arguments
π™½π™²πšˆπ™²π™»π™΄πšπšŸπšŠπš›
π™½π™Ύπ™³π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,𝚜𝚞𝚌𝚌-πšπšŸπšŠπš›)
Restrictions
π™½π™²πšˆπ™²π™»π™΄β‰₯1
π™½π™²πšˆπ™²π™»π™΄β‰€|π™½π™Ύπ™³π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(π™½π™Ύπ™³π™΄πš‚,[πš’πš—πšπšŽπš‘,𝚜𝚞𝚌𝚌])
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰₯1
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰€|π™½π™Ύπ™³π™΄πš‚|
πšπš’πšœπšπš’πš—πšŒπš(π™½π™Ύπ™³π™΄πš‚,πš’πš—πšπšŽπš‘)
π™½π™Ύπ™³π™΄πš‚.𝚜𝚞𝚌𝚌β‰₯1
π™½π™Ύπ™³π™΄πš‚.πšœπšžπšŒπšŒβ‰€|π™½π™Ύπ™³π™΄πš‚|
Purpose

Consider a digraph G described by the π™½π™Ύπ™³π™΄πš‚ collection. π™½π™²πšˆπ™²π™»π™΄ is equal to the number of circuits for covering G in such a way that each vertex of G belongs to one single circuit. π™½π™²πšˆπ™²π™»π™΄ can also be interpreted as the number of cycles of the permutation associated with the successor variables of the π™½π™Ύπ™³π™΄πš‚ collection.

Example
2,πš’πš—πšπšŽπš‘-1𝚜𝚞𝚌𝚌-2,πš’πš—πšπšŽπš‘-2𝚜𝚞𝚌𝚌-1,πš’πš—πšπšŽπš‘-3𝚜𝚞𝚌𝚌-5,πš’πš—πšπšŽπš‘-4𝚜𝚞𝚌𝚌-3,πš’πš—πšπšŽπš‘-5𝚜𝚞𝚌𝚌-4

In this example we have the following 2 (π™½π™²πšˆπ™²π™»π™΄=2) cycles: 1β†’2β†’1 and 3β†’5β†’4β†’3. Consequently, the πšŒπš’πšŒπš•πšŽ constraint holds.

Typical
|π™½π™Ύπ™³π™΄πš‚|>2
π™½π™²πšˆπ™²π™»π™΄<|π™½π™Ύπ™³π™΄πš‚|
Symmetry

Items of π™½π™Ύπ™³π™΄πš‚ are permutable.

Usage

The PhD thesis of Γ‰ricΒ BourreauΒ [Bourreau99] mentions the following applications of extensions of the πšŒπš’πšŒπš•πšŽ constraint:

  • The balanced Euler knight problem where one tries to cover a rectangular chessboard of size NΒ·M by C knights that all have to visit between 2·⌊⌊(NΒ·M)/CβŒ‹/2βŒ‹ and 2·⌈⌈(NΒ·M)/CβŒ‰/2βŒ‰ distinct locations. For some values of N, M and C there does not exist any solution to the previous problem. This is for instance the case when N=M=C=6. FigureΒ 5.89.1 depicts the graph associated with the 6Γ—6 chessboard as well as examples of balanced solutions with respectively 1, 2, 3, 4 and 5 knights.

  • Some pick-up delivery problems where a fleet of vehicles has to transport a set of orders. Each order is characterised by its initial location, its final destination and its weight. In addition one also has to take into account the capacity of the different vehicles.

Figure 5.89.1. Graph of potential moves of the 6Γ—6 chessboard and corresponding balanced tours
ctrs/cycle1
Remark

In the original πšŒπš’πšŒπš•πšŽ constraint of CHIP the πš’πš—πšπšŽπš‘ attribute was not explicitly present. It was implicitly defined as the position of a variable in a list.

In an early version of the CHIP there was a constraint named πšŒπš’πš›πšŒπšžπš’πš that, from a declarative point of view, was equivalent to πšŒπš’πšŒπš•πšŽ(1,π™½π™Ύπ™³π™΄πš‚). In ALICE [Lauriere78] the πšŒπš’πš›πšŒπšžπš’πš constraint was also present.

Given a complete digraph of n vertices as well as an unrestricted number of circuits π™½π™²πšˆπ™²π™»π™΄, the total number of solutions of the corresponding πšŒπš’πšŒπš•πšŽ constraint corresponds to the sequence A000142 of the On -Line Encyclopedia of Integer SequencesΒ [Sloane10]. Given a complete digraph of n vertices as well as a fixed number of circuits π™½π™²πšˆπ™²π™»π™΄ between 1 and n, the total number of solutions of the corresponding πšŒπš’πšŒπš•πšŽ constraint corresponds to the so called Stirling number of first kind.

Algorithm

Since all 𝚜𝚞𝚌𝚌 variables have to take distinct values one can reuse the algorithms associated with the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint. A second necessary condition is to have no more than π™½π™²πšˆπ™²π™»π™΄ Β― strongly connected components. Pruning for enforcing this condition, as soon as we have π™½π™²πšˆπ™²π™»π™΄ Β― strongly connected components, can be done by forcing all strong bridges to belong to the final solution, since otherwise we would have more than π™½π™²πšˆπ™²π™»π™΄ Β― strongly connected components. Since all the vertices of a circuit belong to the same strongly connected component an arc going from one strongly connected component to another strongly connected component has to be removed.

See also

common keyword: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (permutation),

πšŒπš’πš›πšŒπšžπš’πš_πšŒπš•πšžπšœπšπšŽπš›Β (graph constraint, one_succ),

πšŒπš’πšŒπš•πšŽ_πšŒπšŠπš›πš_πš˜πš—_πš™πšŠπšπš‘Β (permutation,graph partitioning constraint),

πšŒπš’πšŒπš•πšŽ_πš˜πš›_πšŠπšŒπšŒπšŽπšœπšœπš’πš‹πš’πš•πš’πšπš’Β (graph constraint),

πšŒπš’πšŒπš•πšŽ_πš›πšŽπšœπš˜πšžπš›πšŒπšŽΒ (graph partitioning constraint),

πšπšŽπš›πšŠπš—πšπšŽπš–πšŽπš—πšΒ (permutation),

πšπš›πšŠπš™πš‘_πšŒπš›πš˜πšœπšœπš’πš—πšΒ (graph constraint,graph partitioning constraint),

πš’πš—πšŸπšŽπš›πšœπšŽΒ (permutation),

πš–πšŠπš™Β (graph partitioning constraint),

πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (permutation),

πšπš˜πšžπš›Β (graph constraint),

πšπš›πšŽπšŽΒ (graph partitioning constraint).

implies: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

specialisation: πšŒπš’πš›πšŒπšžπš’πšΒ (π™½π™²πšˆπ™²π™»π™΄ set to 1).

Keywords

characteristic of a constraint: core.

combinatorial object: permutation.

constraint arguments: business rules.

constraint type: graph constraint, graph partitioning constraint.

filtering: strong bridge, DFS-bottleneck.

final graph structure: circuit, connected component, strongly connected component, one_succ.

modelling: cycle.

problems: pick-up delivery.

puzzles: Euler knight.

Arc input(s)

π™½π™Ύπ™³π™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš—πš˜πšπšŽπšœ1,πš—πš˜πšπšŽπšœ2)

Arc arity
Arc constraint(s)
πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌=πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘
Graph property(ies)
β€’ 𝐍𝐓𝐑𝐄𝐄=0
β€’ 𝐍𝐂𝐂=π™½π™²πšˆπ™²π™»π™΄

Graph class
𝙾𝙽𝙴_πš‚πš„π™²π™²

Graph model

From the restrictions and from the arc constraint, we deduce that we have a bijection from the successor variables to the values of interval [1,|π™½π™Ύπ™³π™΄πš‚|]. With no explicit restrictions it would have been impossible to derive this property.

In order to express the binary constraint that links two vertices one has to make explicit the identifier of the vertices. This is why the πšŒπš’πšŒπš•πšŽ constraint considers objects that have two attributes:

  • One fixed attribute πš’πš—πšπšŽπš‘ that is the identifier of the vertex,

  • One variable attribute 𝚜𝚞𝚌𝚌 that is the successor of the vertex.

The graph property 𝐍𝐓𝐑𝐄𝐄 = 0 is used in order to avoid having vertices that both do not belong to a circuit and have at least one successor located on a circuit. This concretely means that all vertices of the final graph should belong to a circuit.

PartsΒ (A) andΒ (B) of FigureΒ 5.89.2 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐂𝐂 graph property, we show the two connected components of the final graph. The constraint holds since all the vertices belong to a circuit (i.e., 𝐍𝐓𝐑𝐄𝐄 = 0) and since π™½π™²πšˆπ™²π™»π™΄ = 𝐍𝐂𝐂 = 2.

Figure 5.89.2. Initial and final graph of the πšŒπš’πšŒπš•πšŽ constraint
ctrs/cycleActrs/cycleB
(a) (b)