Coverage for /usr/lib/python3/dist-packages/sympy/multipledispatch/utils.py: 79%

1from collections import OrderedDict 

2 

3 

4def expand_tuples(L): 

5 """ 

6 >>> from sympy.multipledispatch.utils import expand_tuples 

7 >>> expand_tuples([1, (2, 3)]) 

8 [(1, 2), (1, 3)] 

9 

10 >>> expand_tuples([1, 2]) 

11 [(1, 2)] 

12 """ 

13 if not L: 

14 return [()] 

15 elif not isinstance(L[0], tuple): 

16 rest = expand_tuples(L[1:]) 

17 return [(L[0],) + t for t in rest] 

18 else: 

19 rest = expand_tuples(L[1:]) 

20 return [(item,) + t for t in rest for item in L[0]] 

21 

22 

23# Taken from theano/theano/gof/sched.py 

24# Avoids licensing issues because this was written by Matthew Rocklin 

25def _toposort(edges): 

26 """ Topological sort algorithm by Kahn [1] - O(nodes + vertices) 

27 

28 inputs: 

29 edges - a dict of the form {a: {b, c}} where b and c depend on a 

30 outputs: 

31 L - an ordered list of nodes that satisfy the dependencies of edges 

32 

33 >>> from sympy.multipledispatch.utils import _toposort 

34 >>> _toposort({1: (2, 3), 2: (3, )}) 

35 [1, 2, 3] 

36 

37 Closely follows the wikipedia page [2] 

38 

39 [1] Kahn, Arthur B. (1962), "Topological sorting of large networks", 

40 Communications of the ACM 

41 [2] https://en.wikipedia.org/wiki/Toposort#Algorithms 

42 """ 

43 incoming_edges = reverse_dict(edges) 

44 incoming_edges = {k: set(val) for k, val in incoming_edges.items()} 

45 S = OrderedDict.fromkeys(v for v in edges if v not in incoming_edges) 

46 L = [] 

47 

48 while S: 

49 n, _ = S.popitem() 

50 L.append(n) 

51 for m in edges.get(n, ()): 

52 assert n in incoming_edges[m] 

53 incoming_edges[m].remove(n) 

54 if not incoming_edges[m]: 

55 S[m] = None 

56 if any(incoming_edges.get(v, None) for v in edges): 

57 raise ValueError("Input has cycles") 

58 return L 

59 

60 

61def reverse_dict(d): 

62 """Reverses direction of dependence dict 

63 

64 >>> d = {'a': (1, 2), 'b': (2, 3), 'c':()} 

65 >>> reverse_dict(d) # doctest: +SKIP 

66 {1: ('a',), 2: ('a', 'b'), 3: ('b',)} 

67 

68 :note: dict order are not deterministic. As we iterate on the 

69 input dict, it make the output of this function depend on the 

70 dict order. So this function output order should be considered 

71 as undeterministic. 

72 

73 """ 

74 result = {} 

75 for key in d: 

76 for val in d[key]: 

77 result[val] = result.get(val, ()) + (key, ) 

78 return result 

79 

80 

81# Taken from toolz 

82# Avoids licensing issues because this version was authored by Matthew Rocklin 

83def groupby(func, seq): 

84 """ Group a collection by a key function 

85 

86 >>> from sympy.multipledispatch.utils import groupby 

87 >>> names = ['Alice', 'Bob', 'Charlie', 'Dan', 'Edith', 'Frank'] 

88 >>> groupby(len, names) # doctest: +SKIP 

89 {3: ['Bob', 'Dan'], 5: ['Alice', 'Edith', 'Frank'], 7: ['Charlie']} 

90 

91 >>> iseven = lambda x: x % 2 == 0 

92 >>> groupby(iseven, [1, 2, 3, 4, 5, 6, 7, 8]) # doctest: +SKIP 

93 {False: [1, 3, 5, 7], True: [2, 4, 6, 8]} 

94 

95 See Also: 

96 ``countby`` 

97 """ 

98 

99 d = {} 

100 for item in seq: 

101 key = func(item) 

102 if key not in d: 

103 d[key] = [] 

104 d[key].append(item) 

105 return d