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

1""" This module provides procedures to check if an instance describes preferences that are single-crossing. 

2""" 

3 

4 

5def is_single_crossing(instance): 

6 """ Tests whether the instance describe a profile of single-crossed preferences. 

7 

8 :param instance: The instance to take the orders from. 

9 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance 

10 

11 :return: A boolean indicating whether the instance is single-crossed or no. 

12 :rtype: bool 

13 """ 

14 

15 def prefers(a, b, o): 

16 return o.index(a) < o.index(b) 

17 

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 

26 

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 

35 

36 for i in range(len(instance.orders)): 

37 if is_SC_with_first(i, instance.orders): 

38 return True 

39 return False