5.330. symmetric

DESCRIPTIONLINKSGRAPH
Origin

[Dooms06]

Constraint

πšœπš’πš–πš–πšŽπšπš›πš’πšŒ(π™½π™Ύπ™³π™΄πš‚)

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

Consider a digraph G described by the π™½π™Ύπ™³π™΄πš‚ collection. Select a subset of arcs of G so that the corresponding graph is symmetric (i.e.,Β if there is an arc from i to j, there is also an arc from j to i).

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

The πšœπš’πš–πš–πšŽπšπš›πš’πšŒ constraint holds since the π™½π™Ύπ™³π™΄πš‚ collection depicts a symmetric graph.

Symmetry

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

Algorithm

The filtering algorithm for the πšœπš’πš–πš–πšŽπšπš›πš’πšŒ constraint is given inΒ [Dooms06]. It removes (respectively imposes) the arcs (i,j) for which the arc (j,i) is not present (respectively is present). It has an overall complexity of O(n+m) where n and m respectively denote the number of vertices and the number of arcs of the initial graph.

See also

common keyword: πšŒπš˜πš—πš—πšŽπšŒπšπšŽπšΒ (symmetric).

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

Keywords

constraint arguments: constraint involving set variables.

constraint type: graph constraint.

final graph structure: symmetric.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πš’πš—_𝚜𝚎𝚝(πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘,πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌)
Graph class
πš‚πšˆπ™Όπ™Όπ™΄πšƒπšπ™Έπ™²

Graph model

Part (A) of Figure 5.330.1 shows the initial graph from which we start. It 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.330.1 gives the final graph associated with the Example slot.

Figure 5.330.1. Initial and final graph of the πšœπš’πš–πš–πšŽπšπš›πš’πšŒ set constraint
ctrs/symmetricActrs/symmetricB
(a) (b)