5.337. tree

DESCRIPTIONLINKSGRAPH
Origin

N.Β Beldiceanu

Constraint

πšπš›πšŽπšŽ(π™½πšƒπšπ™΄π™΄πš‚,π™½π™Ύπ™³π™΄πš‚)

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

Cover a digraph G by a set of trees in such a way that each vertex of G belongs to one distinct tree. The edges of the trees are directed from their leaves to their respective roots.

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

The πšπš›πšŽπšŽ constraint holds since the graph associated with the items of the π™½π™Ύπ™³π™΄πš‚ collection corresponds to two trees (i.e.,Β π™½πšƒπšπ™΄π™΄πš‚=2): each tree respectively involves the vertices {1,2,3,5,6,8} and {4,7}. They are depicted by FigureΒ 5.337.1.

Figure 5.337.1. The two trees associated with the example
ctrs/tree1
Symmetry

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

Remark

Given a complete digraph of n vertices as well as an unrestricted number of trees π™½πšƒπšπ™΄π™΄πš‚, the total number of solutions of the corresponding πšπš›πšŽπšŽ constraint corresponds to the sequence A000272 of the On -Line Encyclopedia of Integer SequencesΒ [Sloane10].

Extension of the πšπš›πšŽπšŽ constraint to the minimum spanning tree constraint is described inΒ [DoomsKatriel06], [Regin08], [ReginRousseauRueherHoeve10].

Algorithm

An arc-consistency filtering algorithm for the πšπš›πšŽπšŽ constraint is described inΒ [BeldiceanuFlenerLorca05]. This algorithm is based on a necessary and sufficient condition that we now depict.

To any πšπš›πšŽπšŽ constraint we associate the digraph G=(V,E), where:

  • To each item π™½π™Ύπ™³π™΄πš‚[i] of the π™½π™Ύπ™³π™΄πš‚ collection corresponds a vertex v i of G.

  • For every pair of items (π™½π™Ύπ™³π™΄πš‚[i],π™½π™Ύπ™³π™΄πš‚[j]) of the π™½π™Ύπ™³π™΄πš‚ collection, where i and j are not necessarily distinct, there is an arc from v i to v j in E if j is a potential value of π™½π™Ύπ™³π™΄πš‚[i].𝚜𝚞𝚌𝚌.

A strongly connected component C of G is called a sink component if all the successors of all vertices of C belong to C. Let π™Όπ™Έπ™½πšƒπšπ™΄π™΄πš‚ and π™Όπ™°πš‡πšƒπšπ™΄π™΄πš‚ respectively denote the number of sink components of G and the number of vertices of G with a loop.

The πšπš›πšŽπšŽ constraint has a solution if and only if:

  • Each sink component of G contains at least one vertex with a loop,

  • The domain of π™½πšƒπšπ™΄π™΄πš‚ has at least one value within interval [π™Όπ™Έπ™½πšƒπšπ™΄π™΄πš‚,π™Όπ™°πš‡πšƒπšπ™΄π™΄πš‚].

Most likely, the worst case complexity of the algorithm proposed inΒ [BeldiceanuFlenerLorca05] may be enhanced by using the linear time algorithm presented inΒ [ItalianoLauraSantaroni10] for computing the strong articulation points of the digraph G.

Reformulation

The πšπš›πšŽπšŽ constraint can be expressed in term of (1)Β a set of |π™½π™Ύπ™³π™΄πš‚| 2 reified constraints for avoiding circuit between more than one node and of (2)Β |π™½π™Ύπ™³π™΄πš‚| reified constraints and of one sum constraint for counting the trees:

  1. For each vertex π™½π™Ύπ™³π™΄πš‚[i] (i∈[1,|π™½π™Ύπ™³π™΄πš‚|]) of the π™½π™Ύπ™³π™΄πš‚ collection we create a variable R i that takes its value within interval [1,|π™½π™Ύπ™³π™΄πš‚|]. This variable represents the rank of vertex π™½π™Ύπ™³π™΄πš‚[i] 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 π™½π™Ύπ™³π™΄πš‚[i],π™½π™Ύπ™³π™΄πš‚[j] (i,j∈[1,|π™½π™Ύπ™³π™΄πš‚|]) of the π™½π™Ύπ™³π™΄πš‚ collection we create a reified constraint of the form π™½π™Ύπ™³π™΄πš‚[i].𝚜𝚞𝚌𝚌=π™½π™Ύπ™³π™΄πš‚[j].πš’πš—πšπšŽπš‘βˆ§iβ‰ jβ‡’R i <R j . The purpose of this constraint is to express the fact that, if there is an arc from vertex π™½π™Ύπ™³π™΄πš‚[i] to another vertex π™½π™Ύπ™³π™΄πš‚[j], then R i should be strictly less than R j .

  2. For each vertex π™½π™Ύπ™³π™΄πš‚[i] (i∈[1,|π™½π™Ύπ™³π™΄πš‚|]) of the π™½π™Ύπ™³π™΄πš‚ collection we create a 0-1 variable B i and state the following reified constraint π™½π™Ύπ™³π™΄πš‚[i].𝚜𝚞𝚌𝚌=π™½π™Ύπ™³π™΄πš‚[i].πš’πš—πšπšŽπš‘β‡”B i in order to force variable B i to be set to value 1 if and only if there is a loop on vertex π™½π™Ύπ™³π™΄πš‚[i]. Finally we create a constraint π™½πšƒπšπ™΄π™΄πš‚=B 1 +B 2 +...+B |π™½π™Ύπ™³π™΄πš‚| for stating the fact that the number of trees is equal to the number of loops of the graph.

Systems

tree in Choco.

See also

common keyword: πšŒπš’πšŒπš•πšŽ, πšπš›πšŠπš™πš‘_πšŒπš›πš˜πšœπšœπš’πš—πš, πš–πšŠπš™Β (graph partitioning constraint), πš™πš›πš˜πš™πšŽπš›_πšπš˜πš›πšŽπšœπšΒ (connected component,tree).

implied by: πš‹πš’πš—πšŠπš›πš’_πšπš›πšŽπšŽ.

related: πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™_πš—πš˜_πš•πš˜πš˜πš™, πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš—πš˜_πš•πš˜πš˜πš™Β (can be used for restricting number of children since discard loops associated with tree roots).

shift of concept: πšœπšπšŠπš‹πš•πšŽ_πšŒπš˜πš–πš™πšŠπšπš’πš‹πš’πš•πš’πšπš’, πšπš›πšŽπšŽ_πš›πšŠπš—πšπšŽ, πšπš›πšŽπšŽ_πš›πšŽπšœπš˜πšžπš›πšŒπšŽ.

specialisation: πš‹πš’πš—πšŠπš›πš’_πšπš›πšŽπšŽΒ (no limit on the number of children replaced by at most two children), πš™πšŠπšπš‘Β (no limit on the number of children replaced by at most one child).

uses in its reformulation: πšπš›πšŽπšŽ_πš›πšŠπš—πšπšŽ, πšπš›πšŽπšŽ_πš›πšŽπšœπš˜πšžπš›πšŒπšŽ.

Keywords

constraint type: graph constraint, graph partitioning constraint.

filtering: strong articulation point, arc-consistency.

final graph structure: connected component, tree, one_succ.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌=πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘
Graph property(ies)
β€’ πŒπ€π—_𝐍𝐒𝐂𝐂≀1
β€’ 𝐍𝐂𝐂=π™½πšƒπšπ™΄π™΄πš‚

Graph model

We use the graph property πŒπ€π—_𝐍𝐒𝐂𝐂≀1 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 one single vertex. The second graph property 𝐍𝐂𝐂=π™½πšƒπšπ™΄π™΄πš‚ enforces the number of trees to be equal to the number of connected components.

PartsΒ (A) andΒ (B) of FigureΒ 5.337.2 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐂𝐂 graph property, we display the two connected components of the final graph. Each of them corresponds to a tree. The πšπš›πšŽπšŽ constraint holds since all strongly connected components of the final graph have no more than one vertex and since π™½πšƒπšπ™΄π™΄πš‚=𝐍𝐂𝐂=2.

Figure 5.337.2. Initial and final graph of the πšπš›πšŽπšŽ constraint
ctrs/treeActrs/treeB
(a) (b)