| | | 1 | | namespace MoreStructures.DisjointSets; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// An <see cref="IDisjointSet"/> implementation based on a simple <see cref="List{T}"/> conceptually storing a forest |
| | | 5 | | /// of trees, by defining the index of the parent node, for each value stored in the data structure. |
| | | 6 | | /// </summary> |
| | | 7 | | /// <remarks> |
| | | 8 | | /// - This implementation optimizes the runtime of <see cref="Union(int, int)"/>, which only requires navigating to the |
| | | 9 | | /// each root instead of a full linear scan of the list, at the cost of <see cref="Find(int)"/> and |
| | | 10 | | /// <see cref="AreConnected(int, int)"/>, which also require to navigate to the root. |
| | | 11 | | /// <br/> |
| | | 12 | | /// - Check <see cref="QuickFindDisjointSet"/> for an alternative implementation of <see cref="IDisjointSet"/> which |
| | | 13 | | /// does the opposite, in terms of optimization. |
| | | 14 | | /// </remarks> |
| | | 15 | | public class QuickUnionDisjointSet : IDisjointSet |
| | | 16 | | { |
| | | 17 | | /// <summary> |
| | | 18 | | /// Maps the i-th item of the Disjoint Set to the parent in the tree structure, they belong to. |
| | | 19 | | /// <br/> |
| | | 20 | | /// I-th items which are roots have parent equal to themselves (i.e. <c>i</c>). |
| | | 21 | | /// </summary> |
| | 2453 | 22 | | protected int[] Parents { get; } |
| | | 23 | | |
| | | 24 | | /// <summary> |
| | | 25 | | /// Builds a Disjoint Set structure containing <paramref name="valuesCount"/> disjoint values, each one into its |
| | | 26 | | /// own singleton tree. |
| | | 27 | | /// </summary> |
| | | 28 | | /// <param name="valuesCount"><inheritdoc cref="ValuesCount" path="/summary"/></param> |
| | | 29 | | /// <remarks> |
| | | 30 | | /// Requires initializing all the <paramref name="valuesCount"/> items of the underlying list, so that each item |
| | | 31 | | /// is conceptually in its own singleton tree. |
| | | 32 | | /// <br/> |
| | | 33 | | /// Time and Space Complexity are O(n). |
| | | 34 | | /// </remarks> |
| | 97 | 35 | | public QuickUnionDisjointSet(int valuesCount) |
| | 97 | 36 | | { |
| | 97 | 37 | | ValuesCount = valuesCount >= 0 |
| | 97 | 38 | | ? valuesCount |
| | 97 | 39 | | : throw new ArgumentException("Must be non-negative.", nameof(valuesCount)); |
| | 91 | 40 | | Parents = new int[valuesCount]; |
| | | 41 | | |
| | 1486 | 42 | | for (var i = 0; i < ValuesCount; i++) |
| | 652 | 43 | | Parents[i] = i; |
| | 91 | 44 | | } |
| | | 45 | | |
| | | 46 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 47 | | /// <remarks> |
| | | 48 | | /// Set at construction time, based on the constructor parameter. |
| | | 49 | | /// <br/> |
| | | 50 | | /// Time and Space Complexity are O(1). |
| | | 51 | | /// </remarks> |
| | 2804 | 52 | | public virtual int ValuesCount { get; } |
| | | 53 | | |
| | | 54 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 55 | | /// <remarks> |
| | | 56 | | /// <para id="algorithm"> |
| | | 57 | | /// ALGORITHM |
| | | 58 | | /// <br/> |
| | | 59 | | /// - Obtained as the number of distinct roots in the forest of trees. |
| | | 60 | | /// <br/> |
| | | 61 | | /// - All items i from 0 to <see cref="ValuesCount"/> - 1 are iterated over. |
| | | 62 | | /// <br/> |
| | | 63 | | /// - An item i is a root if it's parent of itself: <c>Parents[i] == i</c>. |
| | | 64 | | /// </para> |
| | | 65 | | /// <para id="complexity"> |
| | | 66 | | /// COMPLEXITY |
| | | 67 | | /// <br/> |
| | | 68 | | /// - Checking whether an item is parent of itself is a constant-time operation. |
| | | 69 | | /// <br/> |
| | | 70 | | /// - Therefore, Time and Space Complexity are O(n), where n is <see cref="ValuesCount"/>. |
| | | 71 | | /// </para> |
| | | 72 | | /// </remarks> |
| | 306 | 73 | | public virtual int SetsCount => Enumerable.Range(0, ValuesCount).Count(i => Parents[i] == i); |
| | | 74 | | |
| | | 75 | | /// <summary> |
| | | 76 | | /// Returns a copy of the parents of all the values of the forest representing the Disjoint Set. |
| | | 77 | | /// </summary> |
| | 2 | 78 | | public IList<int> GetParents() => Parents.ToArray(); |
| | | 79 | | |
| | | 80 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 81 | | /// <remarks> |
| | | 82 | | /// <para id="algorithm"> |
| | | 83 | | /// ALGORITHM |
| | | 84 | | /// <br/> |
| | | 85 | | /// - Finds the root of <paramref name="first"/> and the root of <paramref name="second"/> and compares them. |
| | | 86 | | /// <br/> |
| | | 87 | | /// - Because the root of a tree is unique, if the two roots coincide, <paramref name="first"/> and |
| | | 88 | | /// <paramref name="second"/> belong to the same tree, and are connected. |
| | | 89 | | /// <br/> |
| | | 90 | | /// - Otherwise they belong to two separate trees of the forest, and are not connected. |
| | | 91 | | /// </para> |
| | | 92 | | /// <para id="complexity"> |
| | | 93 | | /// COMPLEXITY |
| | | 94 | | /// <br/> |
| | | 95 | | /// - Find the two roots takes a time proportional to the height of the two trees. |
| | | 96 | | /// <br/> |
| | | 97 | | /// - If no mechanism to keep trees flat is put in place by this data structure, the height of each is O(n) in |
| | | 98 | | /// the worst case. |
| | | 99 | | /// <br/> |
| | | 100 | | /// - Therefore, Time Complexity is O(n). Space Complexity is O(1). |
| | | 101 | | /// <br/> |
| | | 102 | | /// - If a sub-class of <see cref="QuickUnionDisjointSet"/> introduces mechanisms to keep trees flat, the |
| | | 103 | | /// complexity may become sub-linear. An example is <see cref="WeightedQuickUnionDisjointSet"/>. |
| | | 104 | | /// </para> |
| | | 105 | | /// </remarks> |
| | | 106 | | public virtual bool AreConnected(int first, int second) |
| | 117 | 107 | | { |
| | 117 | 108 | | if (ValuesCount == 0) |
| | 3 | 109 | | throw new InvalidOperationException( |
| | 3 | 110 | | $"{nameof(AreConnected)} cannot be invoked on an empty set."); |
| | 114 | 111 | | if (first < 0 || first >= ValuesCount) |
| | 6 | 112 | | throw new ArgumentException( |
| | 6 | 113 | | $"Must be non-negative and smaller than {nameof(ValuesCount)}.", nameof(first)); |
| | 108 | 114 | | if (second < 0 || second >= ValuesCount) |
| | 6 | 115 | | throw new ArgumentException( |
| | 6 | 116 | | $"Must be non-negative and smaller than {nameof(ValuesCount)}.", nameof(second)); |
| | | 117 | | |
| | 102 | 118 | | if (first == second) |
| | 10 | 119 | | return true; |
| | | 120 | | |
| | 92 | 121 | | return Find(first) == Find(second); |
| | 102 | 122 | | } |
| | | 123 | | |
| | | 124 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 125 | | /// <remarks> |
| | | 126 | | /// <para id="algorithm"> |
| | | 127 | | /// ALGORITHM |
| | | 128 | | /// <br/> |
| | | 129 | | /// - Finds the root of <paramref name="value"/>, by iteratively traversing the tree upwards, until the root |
| | | 130 | | /// of the tree is reached. |
| | | 131 | | /// <br/> |
| | | 132 | | /// - Because the root of a tree is unique and can be reached by every node of the tree navigating upwards, it |
| | | 133 | | /// represents a good identifier of the set of all items in the same tree of the forest. |
| | | 134 | | /// </para> |
| | | 135 | | /// <para id="complexity"> |
| | | 136 | | /// COMPLEXITY |
| | | 137 | | /// <br/> |
| | | 138 | | /// - Find the root takes a time proportional to the height of the tree, the item is in. |
| | | 139 | | /// <br/> |
| | | 140 | | /// - If no mechanism to keep trees flat is put in place by this data structure, the height of the tree |
| | | 141 | | /// is O(n) in the worst case. |
| | | 142 | | /// <br/> |
| | | 143 | | /// - Therefore, Time Complexity is O(n). Space Complexity is O(1). |
| | | 144 | | /// <br/> |
| | | 145 | | /// - If a sub-class of <see cref="QuickUnionDisjointSet"/> introduces mechanisms to keep trees flat, the |
| | | 146 | | /// complexity may become sub-linear. An example is <see cref="WeightedQuickUnionDisjointSet"/>. |
| | | 147 | | /// </para> |
| | | 148 | | /// </remarks> |
| | | 149 | | public virtual int Find(int value) |
| | 332 | 150 | | { |
| | 332 | 151 | | if (ValuesCount == 0) |
| | 2 | 152 | | throw new InvalidOperationException( |
| | 2 | 153 | | $"{nameof(AreConnected)} cannot be invoked on an empty set."); |
| | 330 | 154 | | if (value < 0 || value >= ValuesCount) |
| | 6 | 155 | | throw new ArgumentException( |
| | 6 | 156 | | $"Must be non-negative and smaller than {nameof(ValuesCount)}.", nameof(value)); |
| | | 157 | | |
| | 420 | 158 | | while (Parents[value] != value) |
| | 96 | 159 | | value = Parents[value]; |
| | 324 | 160 | | return value; |
| | 324 | 161 | | } |
| | | 162 | | |
| | | 163 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 164 | | /// <remarks> |
| | | 165 | | /// <para id="algorithm"> |
| | | 166 | | /// ALGORITHM |
| | | 167 | | /// <br/> |
| | | 168 | | /// - It first finds the root R1 of <paramref name="first"/> and the root R2 of <paramref name="second"/>, by |
| | | 169 | | /// running <see cref="Find(int)"/> on each item. |
| | | 170 | | /// <br/> |
| | | 171 | | /// - Then, it attaches R2 as immediate child of R1, by setting the parent of R2 to R1. |
| | | 172 | | /// <br/> |
| | | 173 | | /// - This way the two three now are merged into a single one, which means that all items of the two trees, |
| | | 174 | | /// including <paramref name="first"/> and <paramref name="second"/> are now in the same set. |
| | | 175 | | /// </para> |
| | | 176 | | /// <para id="complexity"> |
| | | 177 | | /// COMPLEXITY |
| | | 178 | | /// <br/> |
| | | 179 | | /// - Find the two roots takes a time proportional to the height of the two trees. |
| | | 180 | | /// <br/> |
| | | 181 | | /// - If no mechanism to keep trees flat is put in place by this data structure, the height of each tree |
| | | 182 | | /// is O(n) in the worst case. |
| | | 183 | | /// <br/> |
| | | 184 | | /// - Attaching one root as child of the other is a constant-time operation, since it only requires setting the |
| | | 185 | | /// parent in the list of parents, which is O(1) work. |
| | | 186 | | /// <br/> |
| | | 187 | | /// - Therefore, Time Complexity is O(n). Space Complexity is O(1). |
| | | 188 | | /// <br/> |
| | | 189 | | /// - If a sub-class of <see cref="QuickUnionDisjointSet"/> introduces mechanisms to keep trees flat, the |
| | | 190 | | /// complexity may become sub-linear. An example is <see cref="WeightedQuickUnionDisjointSet"/>. |
| | | 191 | | /// </para> |
| | | 192 | | /// </remarks> |
| | | 193 | | public virtual void Union(int first, int second) |
| | 28 | 194 | | { |
| | 28 | 195 | | if (ValuesCount == 0) |
| | 1 | 196 | | throw new InvalidOperationException( |
| | 1 | 197 | | $"{nameof(AreConnected)} cannot be invoked on an empty set."); |
| | 27 | 198 | | if (first < 0 || first >= ValuesCount) |
| | 2 | 199 | | throw new ArgumentException( |
| | 2 | 200 | | $"Must be non-negative and smaller than {nameof(ValuesCount)}.", nameof(first)); |
| | 25 | 201 | | if (second < 0 || second >= ValuesCount) |
| | 2 | 202 | | throw new ArgumentException( |
| | 2 | 203 | | $"Must be non-negative and smaller than {nameof(ValuesCount)}.", nameof(second)); |
| | | 204 | | |
| | 23 | 205 | | Parents[Find(second)] = Find(first); |
| | 23 | 206 | | } |
| | | 207 | | } |