Preference structures
First we configure the notebook so we can use auto-completion.
[1]:
%config Completer.use_jedi = False
Then we can import all relations utilities.
[2]:
from pandas import Series
from mcda.relations import *
from mcda.matrices import *
from mcda.values import CommensurableValues
Relations
In the package, a relation aXb is defined by a Relation instance: * the first element of the relation a * the second element of the relation b * the relation type X (P, I, R) which is the Relation class chosen
So you can easily create relations and bundle them in a list:
[3]:
relations0 = [P(0, 1), R(0, 1), I(0, 0)]
Relation’s validity w.r.t the reflexivity property of their relation type are checked on instanciation:
[4]:
try:
P(0, 0)
except ValueError as e:
print(repr(e))
ValueError('Preference relations are irreflexive: 0 == 0')
Relations comparisons
Compare relations elements pairs
[5]:
relations0[0].same_elements(relations0[1])
[5]:
True
Equality
Two relations are equal if they have the same relation type, and same meaning (w.r.t the relation type symmetry property).
[6]:
P(1, 0) == P(1, 0)
[6]:
True
Indifference and incomparable relations are symmetric.
[7]:
I(1, 0) == I(0, 1)
[7]:
True
[8]:
R(1, 0) == R(0, 1)
[8]:
True
Preference relations though are antisymmetric.
[9]:
P(1, 0) == P(0, 1)
[9]:
False
Of course relations that don’t involve the same elements cannot be equal.
[10]:
I(1, 0) == I(0, 2)
[10]:
False
Compatibility of relations
We can check if two relations are compatible i.e their union can coexist.
This is the case if they don’t involve the same pair of elements.
[11]:
P(0, 1).compatible(P(0, 2))
[11]:
True
But also if they are equal (they are redundant but compatible).
[12]:
P(0, 1).compatible(P(0, 1))
[12]:
True
[13]:
I(1, 0).compatible(I(0, 1))
[13]:
True
Two different relations on the same elements pair are incompatible.
[14]:
P(0, 1).compatible(I(1, 0))
[14]:
False
[15]:
P(1, 0).compatible(P(0, 1))
[15]:
False
Preference structure
We can simply create a relations structure by bundling all relations in a list.
[16]:
relations = PreferenceStructure(
[
I(1, 0),
P(0, 2),
P(2, 4),
I(4, 3),
P(4, 5),
R(5, 6),
]
)
You can also create a preference structure by adding relations together:
[17]:
relations1 = I(1, 0)
relations1 += P(0, 2)
relations1 += P(2, 4)
relations1 += I(4, 3)
relations1 += P(4, 5)
relations1 += I(5, 6)
relations1
[17]:
PreferenceStructure([IndifferenceRelation(1, 0), PreferenceRelation(0, 2), PreferenceRelation(2, 4), IndifferenceRelation(4, 3), PreferenceRelation(4, 5), IndifferenceRelation(5, 6)])
Upon instanciation, invalid preference structure will raise an error:
[18]:
try:
PreferenceStructure(
[
I(1, 0),
P(0, 2),
P(2, 4),
I(4, 3),
P(4, 5),
R(0, 1),
]
)
except ValueError as e:
print(repr(e))
ValueError('incompatible relations: 1 I 0, 0 R 1')
[19]:
try:
relations + R(0, 1)
except ValueError as e:
print(repr(e))
ValueError('incompatible relations: 1 I 0, 0 R 1')
We can iterate over the relations in a preference structure:
[20]:
for r in relations:
print(r)
1 I 0
0 P 2
2 P 4
4 I 3
4 P 5
5 R 6
[21]:
rc = relations.copy()
rc -= relations.typed_structures[R]
rc
[21]:
PreferenceStructure([IndifferenceRelation(1, 0), PreferenceRelation(0, 2), PreferenceRelation(2, 4), IndifferenceRelation(4, 3), PreferenceRelation(4, 5)])
[22]:
rc + R(5, 6)
[22]:
PreferenceStructure([IndifferenceRelation(1, 0), PreferenceRelation(0, 2), PreferenceRelation(2, 4), IndifferenceRelation(4, 3), PreferenceRelation(4, 5), IncomparableRelation(5, 6)])
We can plot the relations:
[23]:
relations.plot()
[23]:
[24]:
relations.typed_structures[P].plot()
[24]:
Relation membership
[25]:
I(0, 1) in relations
[25]:
True
Elements list
[26]:
relations.elements
[26]:
[0, 1, 2, 3, 4, 5, 6]
Relation between elements (if existing)
[27]:
relations.elements_pairs_relations[(0, 2)]
[27]:
PreferenceRelation(0, 2)
[28]:
relations.elements_pairs_relations[(7, 1)]
Relations of an element
[29]:
relations.elements_structures[4]
[29]:
PreferenceStructure([PreferenceRelation(4, 5), PreferenceRelation(2, 4), IndifferenceRelation(4, 3)])
Typed relations
[30]:
relations.typed_structures[P]
[30]:
PreferenceStructure([PreferenceRelation(4, 5), PreferenceRelation(0, 2), PreferenceRelation(2, 4)])
[31]:
relations.substructure(types=[P, I])
[31]:
PreferenceStructure([IndifferenceRelation(1, 0), PreferenceRelation(0, 2), PreferenceRelation(2, 4), IndifferenceRelation(4, 3), PreferenceRelation(4, 5)])
Check if relations define a total preorder
[32]:
relations.is_total_preorder
[32]:
False
[33]:
relations1 = PreferenceStructure([
I(1, 0),
P(0, 2),
P(2, 4),
I(4, 3),
P(4, 5),
])
[34]:
relations1.is_total_preorder
[34]:
True
Check if relations define a total order
[35]:
relations1.is_total_order
[35]:
False
[36]:
relations1 = PreferenceStructure([P(0, 2), P(2, 4), P(4, 5)])
relations1.is_total_order
[36]:
True
[37]:
relations1 = PreferenceStructure([
I(1, 0),
P(0, 2),
I(4, 3),
P(4, 5),
])
relations1.is_total_order
[37]:
False
Add all transitive relations
[38]:
res = relations.transitive_closure
res
[38]:
PreferenceStructure([IndifferenceRelation(0, 1), PreferenceRelation(0, 2), PreferenceRelation(0, 3), PreferenceRelation(0, 4), PreferenceRelation(0, 5), IncomparableRelation(0, 6), PreferenceRelation(1, 2), PreferenceRelation(1, 3), PreferenceRelation(1, 4), PreferenceRelation(1, 5), IncomparableRelation(1, 6), PreferenceRelation(2, 3), PreferenceRelation(2, 4), PreferenceRelation(2, 5), IncomparableRelation(2, 6), IndifferenceRelation(3, 4), PreferenceRelation(3, 5), IncomparableRelation(3, 6), IncomparableRelation(4, 6), IncomparableRelation(5, 6), PreferenceRelation(4, 5)])
Remove all transitive relations
This function actually computes a condensed graph from the relations list, the compute transitive reduction on it.
This means the elements of the relation structure could be bundled together in categories!
[39]:
res.transitive_reduction
[39]:
PreferenceStructure([IncomparableRelation((0, 1), (6,)), IncomparableRelation((5,), (0, 1)), PreferenceRelation((0, 1), (2,)), IncomparableRelation((3, 4), (0, 1)), IncomparableRelation((3, 4), (6,)), IncomparableRelation((5,), (6,)), PreferenceRelation((2,), (3, 4)), IncomparableRelation((2,), (6,)), IncomparableRelation((5,), (2,)), PreferenceRelation((3, 4), (5,))])
Outranking matrices
We can convert the relations list to an outranking matrix.
[40]:
mat = relations.outranking_matrix
mat.data
[40]:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
| 3 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 4 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
[41]:
mat.plot()
[41]:
We can of course convert back:
[42]:
PreferenceStructure.from_outranking_matrix(mat)
[42]:
PreferenceStructure([IndifferenceRelation(0, 1), PreferenceRelation(0, 2), IncomparableRelation(0, 3), IncomparableRelation(0, 4), IncomparableRelation(0, 5), IncomparableRelation(0, 6), IncomparableRelation(1, 2), IncomparableRelation(1, 3), IncomparableRelation(1, 4), IncomparableRelation(1, 5), IncomparableRelation(1, 6), IncomparableRelation(2, 3), PreferenceRelation(2, 4), IncomparableRelation(2, 5), IncomparableRelation(2, 6), IndifferenceRelation(3, 4), IncomparableRelation(3, 5), IncomparableRelation(3, 6), IncomparableRelation(4, 6), IncomparableRelation(5, 6), PreferenceRelation(4, 5)])
An outranking matrix cannot contain non-binary values:
[43]:
try:
create_outranking_matrix([[0, 1],[1, -2]])
except TypeError as e:
print(str(e))
<class 'mcda.core.scales.BinaryScale'> can only fit binary data
Transitive closure
We can compute the transitive closure of the graph represented by the matrix.
[44]:
trans_mat = mat.transitive_closure
trans_mat.data
[44]:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| 2 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| 3 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| 4 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
[45]:
trans_mat.plot()
[45]:
Transitive reduction
We can compute the transitive reduction of the matrix. This is the general version of the function that makes no assumptions on the graph (cyclic graphs are accepted). However to remove potential cycles, elements may be bundled together to obtain an acyclic graph in the end.
[46]:
new_matrix = trans_mat.transitive_reduction
new_matrix.data
[46]:
| (5,) | (3, 4) | (2,) | (0, 1) | (6,) | |
|---|---|---|---|---|---|
| (5,) | 0 | 0 | 0 | 0 | 0 |
| (3, 4) | 1 | 0 | 0 | 0 | 0 |
| (2,) | 0 | 1 | 0 | 0 | 0 |
| (0, 1) | 0 | 0 | 1 | 0 | 0 |
| (6,) | 0 | 0 | 0 | 0 | 0 |
[47]:
new_matrix.plot()
[47]:
We can convert back to see what relations it represents (note the presence of incomparable relations though they are redundant in the traditional model).
[48]:
PreferenceStructure.from_outranking_matrix(new_matrix)
[48]:
PreferenceStructure([IncomparableRelation((0, 1), (6,)), IncomparableRelation((5,), (0, 1)), PreferenceRelation((0, 1), (2,)), IncomparableRelation((3, 4), (0, 1)), IncomparableRelation((3, 4), (6,)), IncomparableRelation((5,), (6,)), PreferenceRelation((2,), (3, 4)), IncomparableRelation((2,), (6,)), IncomparableRelation((5,), (2,)), PreferenceRelation((3, 4), (5,))])
We can plot the relations to see how it looks.
[49]:
PreferenceStructure.from_outranking_matrix(new_matrix).plot()
[49]:
If we need to, we can replace the indexes of the outranking matrix by single labels that concatenate the labels of the elements in each category:
[50]:
categories = dict(
(", ".join([str(a) for a in cat]), cat) for cat in new_matrix.vertices
)
categories
[50]:
{'5': (5,), '3, 4': (3, 4), '2': (2,), '0, 1': (0, 1), '6': (6,)}
[51]:
new_matrix.data.index = categories.keys()
new_matrix.data.columns = categories.keys()
new_matrix.data
[51]:
| 5 | 3, 4 | 2 | 0, 1 | 6 | |
|---|---|---|---|---|---|
| 5 | 0 | 0 | 0 | 0 | 0 |
| 3, 4 | 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 0 | 0 | 0 |
| 0, 1 | 0 | 0 | 1 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 0 |
[52]:
PreferenceStructure.from_outranking_matrix(new_matrix).plot()
[52]:
Kernel
[53]:
mat.plot()
[53]:
There is no kernel in this graph (as the only stable set of alternative is {6} but it is not dominant). Indeed if 0 and 1 appears as good candidates, they outrank each other and are rejected from the kernel.
[54]:
mat.kernel
[54]:
[]
We can solve this problem by removing cycles inside the graph, that way it becomes a directed acyclic graph and those are guaranteed to present a kernel.
[55]:
mat.cycle_reduction_matrix.plot()
[55]:
[56]:
mat.cycle_reduction_matrix.kernel
[56]:
[0, 1, 3, 4, 6]
If we assume the transitivity of outranking relation, this makes little sense to consider alternatives 3 and 4 as dominant as they are dominated by alternative 2 itself dominated by two kernel alternatives (0 and 1). We can then apply transitive closure to add this information about the transitivity of the relation.
N.B: when applying both cycle reduction and transitive closure, you can apply them in any order
[57]:
mat.cycle_reduction_matrix.transitive_closure.plot()
[57]:
[58]:
mat.transitive_closure.cycle_reduction_matrix.plot()
[58]:
[59]:
mat.cycle_reduction_matrix.transitive_closure.kernel
[59]:
[0, 1, 6]
Ranking
We can also convert ranking into a preference structure:
[60]:
PreferenceStructure.from_ranking(
CommensurableValues(
Series({
0: 1,
1: 1,
2: 2,
3: 3
})
)
)
[60]:
PreferenceStructure([IndifferenceRelation(0, 1), PreferenceRelation(2, 0), PreferenceRelation(2, 1), PreferenceRelation(3, 0), PreferenceRelation(3, 1), PreferenceRelation(3, 2)])
Sort relations
There can be multiple ways to sort relations in a structure.
[61]:
from mcda.set_functions import HashableSet
Lexicographic order
[62]:
alts = sorted(res.elements)
alts
[62]:
[0, 1, 2, 3, 4, 5, 6]
[63]:
from itertools import product
[64]:
sets = [(a, b) for a, b in product(alts, alts)]
[65]:
sorted(
res,
key=lambda r: (
sets.index(r.elements)
)
)
[65]:
[IndifferenceRelation(0, 1),
PreferenceRelation(0, 2),
PreferenceRelation(0, 3),
PreferenceRelation(0, 4),
PreferenceRelation(0, 5),
IncomparableRelation(0, 6),
PreferenceRelation(1, 2),
PreferenceRelation(1, 3),
PreferenceRelation(1, 4),
PreferenceRelation(1, 5),
IncomparableRelation(1, 6),
PreferenceRelation(2, 3),
PreferenceRelation(2, 4),
PreferenceRelation(2, 5),
IncomparableRelation(2, 6),
IndifferenceRelation(3, 4),
PreferenceRelation(3, 5),
IncomparableRelation(3, 6),
PreferenceRelation(4, 5),
IncomparableRelation(4, 6),
IncomparableRelation(5, 6)]
Cardinality of its elements
[66]:
sets = [s for s in HashableSet.natural_order(alts)]
[67]:
sorted(
res,
key=lambda r: (
sets.index(
HashableSet(r.elements)
)
)
)
[67]:
[IndifferenceRelation(0, 1),
PreferenceRelation(0, 2),
PreferenceRelation(0, 3),
PreferenceRelation(0, 4),
PreferenceRelation(0, 5),
IncomparableRelation(0, 6),
PreferenceRelation(1, 2),
PreferenceRelation(1, 3),
PreferenceRelation(1, 4),
PreferenceRelation(1, 5),
IncomparableRelation(1, 6),
PreferenceRelation(2, 3),
PreferenceRelation(2, 4),
PreferenceRelation(2, 5),
IncomparableRelation(2, 6),
IndifferenceRelation(3, 4),
PreferenceRelation(3, 5),
IncomparableRelation(3, 6),
PreferenceRelation(4, 5),
IncomparableRelation(4, 6),
IncomparableRelation(5, 6)]
Relation type and cardinality of elements
[68]:
order = [P, I, R]
sorted(
res,
key=lambda r: (
order.index(r.__class__),
sets.index(
HashableSet(r.elements)
)
)
)
[68]:
[PreferenceRelation(0, 2),
PreferenceRelation(0, 3),
PreferenceRelation(0, 4),
PreferenceRelation(0, 5),
PreferenceRelation(1, 2),
PreferenceRelation(1, 3),
PreferenceRelation(1, 4),
PreferenceRelation(1, 5),
PreferenceRelation(2, 3),
PreferenceRelation(2, 4),
PreferenceRelation(2, 5),
PreferenceRelation(3, 5),
PreferenceRelation(4, 5),
IndifferenceRelation(0, 1),
IndifferenceRelation(3, 4),
IncomparableRelation(0, 6),
IncomparableRelation(1, 6),
IncomparableRelation(2, 6),
IncomparableRelation(3, 6),
IncomparableRelation(4, 6),
IncomparableRelation(5, 6)]
Elements pair order (as binary mask)
[69]:
sets = [HashableSet.from_index(s, alts) for s in range(2**len(alts))]
sorted(
res,
key=lambda r: (
sets.index(
set(r.elements)
)
)
)
[69]:
[IndifferenceRelation(0, 1),
PreferenceRelation(0, 2),
PreferenceRelation(1, 2),
PreferenceRelation(0, 3),
PreferenceRelation(1, 3),
PreferenceRelation(2, 3),
PreferenceRelation(0, 4),
PreferenceRelation(1, 4),
PreferenceRelation(2, 4),
IndifferenceRelation(3, 4),
PreferenceRelation(0, 5),
PreferenceRelation(1, 5),
PreferenceRelation(2, 5),
PreferenceRelation(3, 5),
PreferenceRelation(4, 5),
IncomparableRelation(0, 6),
IncomparableRelation(1, 6),
IncomparableRelation(2, 6),
IncomparableRelation(3, 6),
IncomparableRelation(4, 6),
IncomparableRelation(5, 6)]