5.315. path
DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Arguments
- Restrictions
- Purpose
Cover the digraph described by the collection with paths in such a way that each vertex of belongs to exactly one path.
- Example
-
The first constraint holds since its second argument corresponds to the 3 (i.e.,Β the first argument of the constraint) paths depicted by FigureΒ 5.315.1.
Figure 5.315.1. The three paths corresponding to the first example of the Example slot; each vertex contains the information where is the index of its successor in the path (by convention one of the extremities of a path points to itself).
- Typical
- Symmetry
Items of are permutable.
- Arg. properties
Functional dependency: determined by .
- Reformulation
The constraint can be expressed in term of (1)Β a set of reified constraints for avoiding circuit between more than one node and of (2)Β reified constraints and of one sum constraint for counting the paths and of (3)Β a set of reified constraints and of inequalities constraints for enforcing the fact that each vertex has at most two children.
For each vertex of the collection we create a variable that takes its value within interval . This variable represents the rank of vertex within a solution. It is used to prevent the creation of circuit involving more than one vertex as explained now. For each pair of vertices of the collection we create a reified constraint of the form . The purpose of this constraint is to express the fact that, if there is an arc from vertex to another vertex , then should be strictly less than .
For each vertex of the collection we create a 0-1 variable and state the following reified constraint in order to force variable to be set to value 1 if and only if there is a loop on vertex . Finally we create a constraint for stating the fact that the number of paths is equal to the number of loops of the graph.
For each pair of vertices of the collection we create a 0-1 variable and state the following reified constraint . Variable is set to value 1 if and only if there is an arc from to . Then for each vertex we create a constraint of the form .
- Counting
-
Length () 2 3 4 5 6 7 8 Solutions 3 13 73 501 4051 37633 394353 Number of solutions for : domains
Length () 2 3 4 5 6 7 8 Total 3 13 73 501 4051 37633 394353 Parameter value 1 2 6 24 120 720 5040 40320 2 1 6 36 240 1800 15120 141120 3 - 1 12 120 1200 12600 141120 4 - - 1 20 300 4200 58800 5 - - - 1 30 630 11760 6 - - - - 1 42 1176 7 - - - - - 1 56 8 - - - - - - 1 Solution count for : domains
- See also
common keyword: Β (graph partitioning constraint, one_succ), Β (path), Β (path, select an induced subgraph so that there is a path from a given vertex to an other given vertex), Β (graph partitioning constraint, one_succ).
generalisation: Β (at most one child replaced by at most two children), Β (vertices are located in time, and to each arc corresponds a precedence constraint), Β (at most one child replaced by no limit on the number of children).
implies: .
related: Β (counting number of paths versus controlling how balanced the paths are).
- Keywords
-
constraint type: graph constraint, graph partitioning constraint.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph class
-
- Graph model
We use the same graph constraint as for the constraint, except that we replace the graph property , which constraints the maximum in-degree of the final graph to not exceed 2 by . does not consider loops: This is why we do not have any problem with the final node of each path.
PartsΒ (A) andΒ (B) of FigureΒ 5.315.2 respectively show the initial and final graph associated with the first example of the Example slot. Since we use the graph property, we display the three connected components of the final graph. Each of them corresponds to a path. Since we use the graph property, we also show with a double circle a vertex that has a maximum number of predecessors.
The constraint holds since all strongly connected components of the final graph have no more than one vertex, since and since .
Figure 5.315.2. Initial and final graph of the constraint
(a) (b)