Coverage for /home/simon/Git/preflibtools/preflibtools/properties/singlecrossing.py: 91%
22 statements
« prev ^ index » next coverage.py v6.4.4, created at 2022-09-22 11:34 +0200
« prev ^ index » next coverage.py v6.4.4, created at 2022-09-22 11:34 +0200
1""" This module provides procedures to check if an instance describes preferences that are single-crossing.
2"""
5def is_single_crossing(instance):
6 """ Tests whether the instance describe a profile of single-crossed preferences.
8 :param instance: The instance to take the orders from.
9 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
11 :return: A boolean indicating whether the instance is single-crossed or no.
12 :rtype: bool
13 """
15 def prefers(a, b, o):
16 return o.index(a) < o.index(b)
18 def conflict_set(o1, o2):
19 res = set([])
20 for i in range(len(o1)):
21 for j in range(i + 1, len(o1)):
22 if ((prefers(o1[i], o1[j], o1) and prefers(o1[j], o1[i], o2)) or
23 (prefers(o1[j], o1[i], o1) and prefers(o1[i], o1[j], o2))):
24 res.add((min(o1[i][0], o1[j][0]), max(o1[i][0], o1[j][0])))
25 return res
27 def is_SC_with_first(i, profile):
28 for j in range(len(profile)):
29 for k in range(len(profile)):
30 conflict_ij = conflict_set(profile[i], profile[j])
31 conflict_ik = conflict_set(profile[i], profile[k])
32 if not (conflict_ij.issubset(conflict_ik) or conflict_ik.issubset(conflict_ij)):
33 return False
34 return True
36 for i in range(len(instance.orders)):
37 if is_SC_with_first(i, instance.orders):
38 return True
39 return False