Coverage for /home/simon/Git/preflibtools/preflibtools/properties/distances.py: 92%
36 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 functions to compute distances between orders.
2"""
4import numpy as np
7def distance_matrix(instance, distance_function):
8 """ Returns a matrix of the pairwise distance between all orders of the instance.
10 :param instance: The instance to take the orders from.
11 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
12 :param distance_function: The distance function to use. It should take two orders as input.
13 :type distance_function: function
15 :return: A Numpy array of the pairwise distances, coordinates being the index of the orders in the order
16 list of the instance.
17 :rtype: numpy array
18 """
19 profile = instance.full_profile()
20 num_voters = len(profile)
21 res = np.zeros((num_voters, num_voters))
22 for i in range(num_voters):
23 for j in range(i + 1, num_voters):
24 res[(i, j)] = distance_function(profile[i], profile[j])
25 res[(j, i)] = distance_function(profile[j], profile[i])
26 return res
29def kendall_tau_distance(order1, order2):
30 """ Returns the Kendall's tau distance between two orders.
32 :param order1: The first order.
33 :type order1: tuple
34 :param order2: The second order.
35 :type order2: tuple
37 :return: The Kendall's tau distance between the two orders.
38 :rtype: int
39 """
40 if len(order1) != len(order2):
41 raise ValueError("Rankings must have the same length to compute their Kendall's tau distance")
42 res = 0
43 norm = 0
44 for j1 in range(len(order1)):
45 for j2 in range(j1 + 1, len(order1)):
46 if order2.index(order1[j1]) > order2.index(order1[j2]):
47 res += 1
48 norm += 1
49 return res / norm
52def spearman_footrule_distance(order1, order2):
53 """ Returns the Spearman's footrule distance between two orders.
55 :param order1: The first order.
56 :type order1: tuple
57 :param order2: The second order.
58 :type order2: tuple
60 :return: The Spearman's footrule distance between the two orders.
61 :rtype: float
62 """
63 if len(order1) != len(order2):
64 raise ValueError("Rankings must have the same length to compute their Spearman's footrule distance")
65 res = 0
66 for j in range(len(order1)):
67 res += abs(j - order2.index(order1[j]))
68 return res / np.floor(len(order1) ** 2 / 2)
71def sertel_distance(order1, order2):
72 """ Returns the Sertel's distance between two orders.
74 :param order1: The first order.
75 :type order1: tuple
76 :param order2: The second order.
77 :type order2: tuple
79 :return: The Sertel's distance between the two orders.
80 :rtype: float
81 """
82 if len(order1) != len(order2):
83 raise ValueError("Rankings must have the same length to compute their Sertel's distance")
84 j = 0
85 for j in range(len(order1)):
86 if order1[j] != order2[j]:
87 break
88 return (len(order1) - 1 - j) / (len(order1) - 1)