5.95. dag

DESCRIPTIONLINKSGRAPH
Origin

[Dooms06]

Constraint

𝚍𝚊𝚐(π™½π™Ύπ™³π™΄πš‚)

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

Consider a digraph G described by the π™½π™Ύπ™³π™΄πš‚ collection. Select a subset of arcs of G so that the corresponding graph does not contain any circuit.

Example
πš’πš—πšπšŽπš‘-1𝚜𝚞𝚌𝚌-{2,4},πš’πš—πšπšŽπš‘-2𝚜𝚞𝚌𝚌-{3,4},πš’πš—πšπšŽπš‘-3𝚜𝚞𝚌𝚌-βˆ…,πš’πš—πšπšŽπš‘-4𝚜𝚞𝚌𝚌-βˆ…,πš’πš—πšπšŽπš‘-5𝚜𝚞𝚌𝚌-{6},πš’πš—πšπšŽπš‘-6𝚜𝚞𝚌𝚌-βˆ…

The 𝚍𝚊𝚐 constraint holds since the π™½π™Ύπ™³π™΄πš‚ collection depicts a graph without circuit.

Typical
|π™½π™Ύπ™³π™΄πš‚|>2
Symmetry

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

Algorithm

A filtering algorithm for the 𝚍𝚊𝚐 constraint is given in [Dooms06]. It removes potential arcs that would create a circuit of mandatory arcs.

See also

used in graph description: πš’πš—_𝚜𝚎𝚝.

Keywords

constraint arguments: constraint involving set variables.

constraint type: graph constraint.

Arc input(s)

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

Arc generator
π‘†πΈπΏπΉβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš—πš˜πšπšŽπšœ)

Arc arity
Arc constraint(s)
πš’πš—_𝚜𝚎𝚝(πš—πš˜πšπšŽπšœ.πš”πšŽπš’,πš—πš˜πšπšŽπšœ.𝚜𝚞𝚌𝚌)
Graph property(ies)
𝐍𝐀𝐑𝐂=0

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πš’πš—_𝚜𝚎𝚝(πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘,πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌)
Graph property(ies)
πŒπ€π—_𝐍𝐒𝐂𝐂≀1

Graph model

The first graph constraint removes the loop of each vertex. The second graph constraint forbids the creation of circuits involving more than one vertex.

Part (A) of Figure 5.95.1 shows the initial graph associated with the second graph constraint of the Example slot. This initial graph from which we start is derived from the set associated with each vertex. Each set describes the potential values of the 𝚜𝚞𝚌𝚌 attribute of a given vertex. Part (B) of Figure 5.95.1 gives the final graph associated with the Example slot.

Figure 5.95.1. Initial and final graph of the 𝚍𝚊𝚐 set constraint
ctrs/dagActrs/dagB
(a) (b)