Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/utils/union_find.py: 18%

1""" 

2Union-find data structure. 

3""" 

4 

5from networkx.utils import groups 

6 

7 

8class UnionFind: 

9 """Union-find data structure. 

10 

11 Each unionFind instance X maintains a family of disjoint sets of 

12 hashable objects, supporting the following two methods: 

13 

14 - X[item] returns a name for the set containing the given item. 

15 Each set is named by an arbitrarily-chosen one of its members; as 

16 long as the set remains unchanged it will keep the same name. If 

17 the item is not yet part of a set in X, a new singleton set is 

18 created for it. 

19 

20 - X.union(item1, item2, ...) merges the sets containing each item 

21 into a single larger set. If any item is not yet part of a set 

22 in X, it is added to X as one of the members of the merged set. 

23 

24 Union-find data structure. Based on Josiah Carlson's code, 

25 https://code.activestate.com/recipes/215912/ 

26 with significant additional changes by D. Eppstein. 

27 http://www.ics.uci.edu/~eppstein/PADS/UnionFind.py 

28 

29 """ 

30 

31 def __init__(self, elements=None): 

32 """Create a new empty union-find structure. 

33 

34 If *elements* is an iterable, this structure will be initialized 

35 with the discrete partition on the given set of elements. 

36 

37 """ 

38 if elements is None: 

39 elements = () 

40 self.parents = {} 

41 self.weights = {} 

42 for x in elements: 

43 self.weights[x] = 1 

44 self.parents[x] = x 

45 

46 def __getitem__(self, object): 

47 """Find and return the name of the set containing the object.""" 

48 

49 # check for previously unknown object 

50 if object not in self.parents: 

51 self.parents[object] = object 

52 self.weights[object] = 1 

53 return object 

54 

55 # find path of objects leading to the root 

56 path = [] 

57 root = self.parents[object] 

58 while root != object: 

59 path.append(object) 

60 object = root 

61 root = self.parents[object] 

62 

63 # compress the path and return 

64 for ancestor in path: 

65 self.parents[ancestor] = root 

66 return root 

67 

68 def __iter__(self): 

69 """Iterate through all items ever found or unioned by this structure.""" 

70 return iter(self.parents) 

71 

72 def to_sets(self): 

73 """Iterates over the sets stored in this structure. 

74 

75 For example:: 

76 

77 >>> partition = UnionFind("xyz") 

78 >>> sorted(map(sorted, partition.to_sets())) 

79 [['x'], ['y'], ['z']] 

80 >>> partition.union("x", "y") 

81 >>> sorted(map(sorted, partition.to_sets())) 

82 [['x', 'y'], ['z']] 

83 

84 """ 

85 # Ensure fully pruned paths 

86 for x in self.parents: 

87 _ = self[x] # Evaluated for side-effect only 

88 

89 yield from groups(self.parents).values() 

90 

91 def union(self, *objects): 

92 """Find the sets containing the objects and merge them all.""" 

93 # Find the heaviest root according to its weight. 

94 roots = iter( 

95 sorted( 

96 {self[x] for x in objects}, key=lambda r: self.weights[r], reverse=True 

97 ) 

98 ) 

99 try: 

100 root = next(roots) 

101 except StopIteration: 

102 return 

103 

104 for r in roots: 

105 self.weights[root] += self.weights[r] 

106 self.parents[r] = root