Computes exact separation matrices by evaluating the average separation over all the linear extensions of the input poset. The linear extensions are generated according to the algorithm given in Habib M, Medina R, Nourine L and Steiner G (2001).
ExactSeparation(poset, output_every_sec = NULL, type, ...)A list containing: 1) the required type of approximated separation matrices, according to the parameter type used
to build the generator (see function BuildBubleyDyerSeparationGenerator); 2) the number of generated linear extensions.
Object of S4 class POSet representing the poset whose separation matrix is computed.
Argument poset must be created by using any function contained in the package aimed at building object of S4 class POSet
(e.g. POSet(), LinearPOSet(), ProductPOSet(), ...) .
Integer specifying a time interval (in seconds).
By specifying this argument, during the execution of BubleyDyerSeparation, a message reporting the number of linear extensions
progressively generated is printed on the R-Console, every output_every_sec seconds.
type of separation to be computed. Possible choices are: "symmetric", "asymmetricLower", "asymmetricUpper", "vertical", "horizontal".
additional types of Separations to be computed. Possible choices are: "symmetric", "asymmetricLower", "asymmetricUpper", "vertical", "horizontal".
The symmetric separation associated to two elements \(a\) and \(b\) of the input poset, is the average absolute difference between the positions of \(a\) and \(b\) observed over all linear extensions (whose elements are arranged in ascending order):
\(Sep_{ab}=\frac{1}{n}\sum_{i^1}^{n}|Pos_{l_i}(a)-Pos_{l_i}(b)|\),
where \(n\) is the numbers of linear extensions of the input poset; \(l_i\) represents a single linear extension and \(Pos_{l_i}(\cdot)\) stands for the position of element \(\cdot\) into the sequence of poset elements arranged in increasing order according to \(l_i\).
Asymmetric lower and upper separations are defined as: \(Sep_{a < b}=\frac{1}{n}\sum_{i^1}^{n}(Pos_{l_i}(b)-Pos_{l_i}(a))\mathbb{1}(a <_{l_i} b)\), \(Sep_{b < a}=\frac{1}{n}\sum_{i^1}^{n}(Pos_{l_i}(a)-Pos_{l_i}(b))\mathbb{1}(b <_{l_i} a)\), where \(a\leq_{l_i} b\) means that \(a\) is lower or equal to \(b\) in the linear order defined by linear extension \(l_i\) and \(\mathbb{1}\) is the indicator function. Note that \(Sep_{ab}=Sep_{a < b}+Sep_{a < b}\).
Vertical and horizontal separations (\(vSep\) and \(hSep\), respectively) are defined as
\(vSep_{ab}=|Sep_{a < b}-Sep_{b < a}|\) and #' \(hSep_{ab}=Sep_{ab}-vSep_{ab}|\).
For a detailed explanation on why \(vSep\) and \(hSep\) can be interpreted as vertical and horizontal components of the separation between poset elements, see Fattore et. al (2024).
Habib M, Medina R, Nourine L and Steiner G (2001). Efficient algorithms on distributive lattices. Discrete Applied Mathematics, 110, 169-187. https://doi.org/10.1016/S0166-218X(00)00258-4.
Fattore, M., De Capitani, L., Avellone, A., and Suardi, A. (2024). A fuzzy posetic toolbox for multi-criteria evaluation on ordinal data systems. Annals of Operations Research, https://doi.org/10.1007/s10479-024-06352-3.
el <- c("a", "b", "c", "d")
dom <- matrix(c(
"a", "b",
"c", "b",
"b", "d"
), ncol = 2, byrow = TRUE)
pos <- POSet(elements = el, dom = dom)
SEP_matrices <- ExactSeparation(pos, output_every_sec=5, "symmetric","asymmetricUpper", "vertical")
Run the code above in your browser using DataLab