5.48. balance_path
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Arguments
- Restrictions
- Purpose
Consider a digraph described by the collection. Partition into a set of vertex disjoint paths in such a way that each vertex of belongs to a single path. is equal to the difference between the number of vertices of the largest path and the number of vertices of the smallest path.
- Example
-
In the first example we have the following four paths: , , 4, and 7. Since is the difference between the number of vertices of the largest path (i.e.,Β 4) and the number of vertices of the smallest path (i.e.,Β 1) the corresponding constraint holds.
- All solutions
FigureΒ 5.48.1 gives all solutions to the following non ground instance of the constraint: , , , , , , , .
Figure 5.48.1. All solutions corresponding to the non ground example of the constraint of the All solutions slot; the attribute is displayed as indices of the attribute and all vertices of a same path are coloured by the same colour.
- Typical
- Symmetry
Items of are permutable.
- Arg. properties
Functional dependency: determined by .
- 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 0 3 7 37 121 1201 5041 62161 1 - 6 12 200 210 8862 24416 2 - - 24 60 1560 5250 97776 3 - - - 120 360 10920 62160 4 - - - - 720 2520 87360 5 - - - - - 5040 20160 6 - - - - - - 40320 Solution count for : domains
- See also
implies: .
related: Β (equivalence classes correspond to vertices in same path rather than variables assigned to the same value), Β (do not care how many paths but 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
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.
We use the graph property in order to specify the fact that the size of the largest strongly connected component should not exceed one. In fact each root of a tree is a strongly connected component with a single vertex. The graph property constraints the maximum in-degree of the final graph to not exceed 1. 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.48.2 respectively show the initial and final graph associated with the first example of the Example slot. Since we use the graph property, we show the connected components of the final graph. The constraint holds since all the vertices belong to a path and since 3.
Figure 5.48.2. Initial and final graph of the constraint
(a) (b)