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

1""" This module provides functions to compute distances between orders. 

2""" 

3 

4import numpy as np 

5 

6 

7def distance_matrix(instance, distance_function): 

8 """ Returns a matrix of the pairwise distance between all orders of the instance. 

9 

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 

14 

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 

27 

28 

29def kendall_tau_distance(order1, order2): 

30 """ Returns the Kendall's tau distance between two orders. 

31 

32 :param order1: The first order. 

33 :type order1: tuple 

34 :param order2: The second order. 

35 :type order2: tuple 

36 

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 

50 

51 

52def spearman_footrule_distance(order1, order2): 

53 """ Returns the Spearman's footrule distance between two orders. 

54 

55 :param order1: The first order. 

56 :type order1: tuple 

57 :param order2: The second order. 

58 :type order2: tuple 

59 

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) 

69 

70 

71def sertel_distance(order1, order2): 

72 """ Returns the Sertel's distance between two orders. 

73 

74 :param order1: The first order. 

75 :type order1: tuple 

76 :param order2: The second order. 

77 :type order2: tuple 

78 

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)