Coverage for /home/simon/Git/preflibtools/preflibtools/properties/basic.py: 83%
75 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 describes several procedures to check for basic procedures of PrefLib instances.
2"""
5def pairwise_scores(instance):
6 """ Returns a dictionary of dictionaries mapping every alternative a to the number of times it beats
7 every other alternative b (the number of voters preferring a over b).
9 :param instance: The instance.
10 :type instance: preflibtools.instance.preflibinstance.PreflibInstance
12 :return: A dictionary of dictionaries storing the scores.
13 :rtype: dict
14 """
15 if instance.data_type in ["soc", "toc", "soi", "toi"]:
16 scores = {alt: {a: 0 for a in instance.alternatives_name if a != alt} for alt in instance.alternatives_name}
17 for order in instance.orders:
18 alternatives_before = []
19 for indif_class in order:
20 # Every alternative appearing before are beating the ones in the current indifference class
21 for alt_beaten in indif_class:
22 for alt_winning in alternatives_before:
23 scores[alt_winning][alt_beaten] += instance.multiplicity[order]
24 alternatives_before += [alt for alt in indif_class]
25 return scores
28def copeland_scores(instance):
29 """ Returns a dictionary of dictionaries mapping every alternative a to their Copeland score against every other
30 alternative b (the number of voters preferring a over b minus the number of voters preferring b over a).
32 :param instance: The instance.
33 :type instance: preflibtools.instance.preflibinstance.PreflibInstance
35 :return: A dictionary of dictionaries storing the scores.
36 :rtype: dict
37 """
38 if instance.data_type in ["soc", "toc", "soi", "toi"]:
39 scores = {alt: {a: 0 for a in instance.alternatives_name if a != alt} for alt in instance.alternatives_name}
40 for order in instance.orders:
41 alternatives_before = []
42 for indif_class in order:
43 # Every alternative appearing before are beating the ones in the current indifference class
44 for alt_beaten in indif_class:
45 for alt_winning in alternatives_before:
46 scores[alt_winning][alt_beaten] += instance.multiplicity[order]
47 scores[alt_beaten][alt_winning] -= instance.multiplicity[order]
48 alternatives_before += [alt for alt in indif_class]
49 return scores
52def has_condorcet(instance):
53 """ Checks whether the instance has a Condorcet winner, using different procedures depending on the data type of
54 the instance. An alternative is a Condorcet winner if it strictly beats every other alternative in a pairwise
55 majority contest.
57 :param instance: The instance.
58 :type instance: preflibtools.instance.preflibinstance.PreflibInstance
60 :return: A boolean indicating whether the instance has a Condorcet winner or not.
61 :rtype: bool
62 """
63 if instance.data_type in ["soc", "toc", "soi", "toi"]:
64 scores = copeland_scores(instance)
65 for alt, scoreDict in scores.items():
66 if all(score > 0 for score in scoreDict.values()):
67 return True
68 return False
71def borda_scores(instance):
72 """ Computes the total Borda scores of all the alternatives of the instance. Within an indifference class, all
73 alternatives are assigned the smallest score one alternative from the class would have gotten, had the order
74 been strict. For instance, for the order ({a1}, {a2, a3}, {a4}), a1 gets score 3, a2 and a3 score 1 and a4
75 score 0.
77 :param instance: The instance.
78 :type instance: preflibtools.instance.preflibinstance.PreflibInstance
80 :return: A dictionary mapping every instance to their Borda score.
81 :rtype: dict
82 """
83 if instance.data_type not in ("toc", "soc", "toi", "soi"):
84 raise TypeError("You are trying to compute the Borda scores of an instance of type " +
85 str(instance.data_type) + ", this is not possible.")
86 res = dict([])
87 for order in instance.orders:
88 i = instance.num_alternatives
89 for indif_class in order:
90 i -= len(indif_class)
91 for alt in indif_class:
92 if alt not in res:
93 res[alt] = i
94 else:
95 res[alt] += i
96 return res
99def num_alternatives(instance):
100 """ Returns the number of alternatives of the instance.
102 :param instance: The instance.
103 :type instance: preflibtools.instance.preflibinstance.PreflibInstance
105 :return: The number of alternatives of the instance.
106 :rtype: int
107 """
108 return instance.num_alternatives
111def num_voters(instance):
112 """ Returns the number of voters .
114 :param instance: The instance.
115 :type instance: preflibtools.instance.preflibinstance.PreflibInstance
117 :return: The number of voters of the instance.
118 :rtype: int
119 """
120 return instance.num_voters
123def num_different_preferences(instance):
124 """ Returns the number of different orders of the instance.
126 :param instance: The instance.
127 :type instance: preflibtools.instance.preflibinstance.PreflibInstance
129 :return: The number of different orders of the instance.
130 :rtype: int
131 """
132 if instance.data_type in ("toc", "soc", "toi", "soi"):
133 return instance.num_unique_orders
134 elif instance.data_type == "cat":
135 return instance.num_unique_preferences
138def largest_ballot(instance):
139 """ Returns the size of the largest ballot of the instance, i.e., the maximum number of alternatives
140 appearing in an order.
142 :param instance: The instance.
143 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
145 :return: The size of the largest ballot of the instance.
146 :rtype: int
147 """
148 return max([sum([len(indif_class) for indif_class in order]) for order in instance.orders])
151def smallest_ballot(instance):
152 """ Returns the size of the smallest ballot of the instance, i.e., the smallest number of alternatives
153 appearing in an order.
155 :param instance: The instance.
156 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
158 :return: The size of the smallest ballot of the instance.
159 :rtype: int
160 """
161 return min([sum([len(indif_class) for indif_class in order]) for order in instance.orders])
164def max_num_indif(instance):
165 """ Returns the maximum number of indifference classes over the orders of the instance.
167 :param instance: The instance.
168 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
170 :return: The maximum number of indifference classes of the instance.
171 :rtype: int
172 """
173 return max([len([p for p in o if len(p) > 1]) for o in instance.orders] + [0])
176def min_num_indif(instance):
177 """ Returns the minimum number of indifference classes over the orders of the instance.
179 :param instance: The instance.
180 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
182 :return: The minimum number of indifference classes of the instance.
183 :rtype: int
184 """
185 return min([len([p for p in o if len(p) > 1]) for o in instance.orders] + [instance.num_alternatives])
188def largest_indif(instance):
189 """ Returns the size of the largest indifference class of any voter of the instance.
191 :param instance: The instance.
192 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
194 :return: The size of the largest indifference class of the instance.
195 :rtype: int
196 """
197 return max([len(p) for o in instance.orders for p in o if len(p) > 0] + [0])
200def smallest_indif(instance):
201 """ Returns the size of the smallest indifference class of any voter of the instance.
203 :param instance: The instance.
204 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
206 :return: The size of the smallest indifference class of the instance.
207 :rtype: int
208 """
209 return min([len(p) for o in instance.orders for p in o if len(p) > 0] + [instance.num_alternatives])
212def is_approval(instance):
213 """ Checks whether the instance describes an approval profile. A profile is considered to represent approval
214 ballots in two cases: All the orders are complete and consist of only two indifference classes; The orders
215 are incomplete and consists of a single indifference class.
217 :param instance: The instance.
218 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
220 :return: A boolean indicating whether the instance describes an approval profile.
221 :rtype: bool
222 """
223 m = max([len(order) for order in instance.orders])
224 if m == 1:
225 return True
226 elif m == 2:
227 return is_complete(instance)
228 else:
229 return False
232def is_strict(instance):
233 """ Checks whether the instance describes a profile of strict preferences.
235 :param instance: The instance.
236 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
238 :return: A boolean indicating whether the instance describes a profile of strict preferences.
239 :rtype: bool
240 """
241 return largest_indif(instance) == 1
244def is_complete(instance):
245 """ Checks whether the instance describes a profile of complete preferences.
247 :param instance: The instance.
248 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
250 :return: A boolean indicating whether the instance describes a profile of complete preferences.
251 :rtype: bool
252 """
253 return smallest_ballot(instance) == instance.num_alternatives