| | | 1 | | namespace MoreStructures.DisjointSets; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// A <see cref="QuickUnionDisjointSet"/> refinement which improves the performance of Find by minimizing the height of |
| | | 5 | | /// trees in the forest when merging them in <see cref="Union"/>. |
| | | 6 | | /// </summary> |
| | | 7 | | /// <remarks> |
| | | 8 | | /// By merging by rank, the increment of rank of the trees in the forest when merging is minimized, and the forest |
| | | 9 | | /// is kept as flat as possible after the <see cref="Union(int, int)"/> operation. |
| | | 10 | | /// <br/> |
| | | 11 | | /// Keeping trees flat is the way to ensure sub-linear, Time Complexity in |
| | | 12 | | /// <see cref="QuickUnionDisjointSet.AreConnected(int, int)"/> and <see cref="QuickUnionDisjointSet.Find(int)"/>, which |
| | | 13 | | /// in the specific case become logarithmic in time. |
| | | 14 | | /// </remarks> |
| | | 15 | | public class WeightedQuickUnionDisjointSet : QuickUnionDisjointSet |
| | | 16 | | { |
| | | 17 | | /// <summary> |
| | | 18 | | /// Maps the i-th item of the Disjoint Set to its rank in the tree structure, they belong to. |
| | | 19 | | /// <br/> |
| | | 20 | | /// I-th items which are leaves have rank equal to 0. |
| | | 21 | | /// </summary> |
| | | 22 | | /// <remarks> |
| | | 23 | | /// The rank of a node in the tree is an upper bound for its height. |
| | | 24 | | /// <br/> |
| | | 25 | | /// Ranks are used, instead of heights, because keeping ranks correct is easier than keeping heights correct. |
| | | 26 | | /// </remarks> |
| | 668 | 27 | | protected int[] Ranks { get; } |
| | | 28 | | |
| | | 29 | | /// <inheritdoc path="//*[not(self::summary)]"/> |
| | | 30 | | /// <summary> |
| | | 31 | | /// <inheritdoc/> |
| | | 32 | | /// <br/> |
| | | 33 | | /// Initializes the ranks of all singleton trees to 0. |
| | | 34 | | /// </summary> |
| | 75 | 35 | | public WeightedQuickUnionDisjointSet(int valuesCount) : base(valuesCount) |
| | 71 | 36 | | { |
| | 71 | 37 | | Ranks = new int[valuesCount]; |
| | 71 | 38 | | } |
| | | 39 | | |
| | | 40 | | /// <summary> |
| | | 41 | | /// Returns a copy of the ranks of the trees of the forest representing the Disjoint Set. |
| | | 42 | | /// </summary> |
| | 18 | 43 | | public IList<int> GetRanks() => Ranks.ToArray(); |
| | | 44 | | |
| | | 45 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 46 | | /// <remarks> |
| | | 47 | | /// <para id="algorithm"> |
| | | 48 | | /// ALGORITHM |
| | | 49 | | /// <br/> |
| | | 50 | | /// - It first finds the root R1 of <paramref name="first"/> and the root R2 of <paramref name="second"/>, by |
| | | 51 | | /// running <see cref="QuickUnionDisjointSet.Find(int)"/> on each item. |
| | | 52 | | /// <br/> |
| | | 53 | | /// - Then, it checks the rank of R1, H1 and R2, H2 and uses them to decide whether to attach R1 to R2 or |
| | | 54 | | /// viceversa. |
| | | 55 | | /// <br/> |
| | | 56 | | /// - If <c>H1 >= H2</c>, it attaches R2 as immediate child of R1, by setting the parent of R2 to R1. |
| | | 57 | | /// <br/> |
| | | 58 | | /// - Otherwise, it attaches R1 as immediate child of R2, by setting the parent of R1 to R2. |
| | | 59 | | /// <br/> |
| | | 60 | | /// - This way the two three now are merged into a single one, which means that all items of the two trees, |
| | | 61 | | /// including <paramref name="first"/> and <paramref name="second"/> are now in the same set. |
| | | 62 | | /// <br/> |
| | | 63 | | /// - Moreover, by merging based on ranks H1 and H2, the rank of the resulting tree is minimized. |
| | | 64 | | /// <br/> |
| | | 65 | | /// - Finally the rank of the new root (R1 or R2), is updated, to reflect the merge. |
| | | 66 | | /// </para> |
| | | 67 | | /// <para id="complexity"> |
| | | 68 | | /// COMPLEXITY |
| | | 69 | | /// <br/> |
| | | 70 | | /// - Find the two roots takes a time proportional to the rank of the two trees. |
| | | 71 | | /// <br/> |
| | | 72 | | /// - Thanks to the "merging by rank", unlike in <see cref="QuickUnionDisjointSet"/>, the rank of each tree |
| | | 73 | | /// in the forest is not O(n) in the worst case, but O(log(n)). |
| | | 74 | | /// <br/> |
| | | 75 | | /// - Attaching one root as child of the other is a constant-time operation, since it only requires setting the |
| | | 76 | | /// parent in the list of parents, which is O(1) work. |
| | | 77 | | /// <br/> |
| | | 78 | | /// - Updating the rank of the root of the merged tree is also a constant-time operation. |
| | | 79 | | /// <br/> |
| | | 80 | | /// - Therefore, Time Complexity is O(log(n)). Space Complexity is O(1). |
| | | 81 | | /// </para> |
| | | 82 | | /// </remarks> |
| | | 83 | | public override void Union(int first, int second) |
| | 140 | 84 | | { |
| | 140 | 85 | | if (ValuesCount == 0) |
| | 2 | 86 | | throw new InvalidOperationException( |
| | 2 | 87 | | $"{nameof(AreConnected)} cannot be invoked on an empty set."); |
| | 138 | 88 | | if (first < 0 || first >= ValuesCount) |
| | 4 | 89 | | throw new ArgumentException( |
| | 4 | 90 | | $"Must be non-negative and smaller than {nameof(ValuesCount)}.", nameof(first)); |
| | 134 | 91 | | if (second < 0 || second >= ValuesCount) |
| | 4 | 92 | | throw new ArgumentException( |
| | 4 | 93 | | $"Must be non-negative and smaller than {nameof(ValuesCount)}.", nameof(second)); |
| | | 94 | | |
| | 130 | 95 | | var firstRoot = Find(first); |
| | 130 | 96 | | var secondRoot = Find(second); |
| | 130 | 97 | | if (Ranks[firstRoot] >= Ranks[secondRoot]) |
| | 115 | 98 | | { |
| | 115 | 99 | | Parents[secondRoot] = firstRoot; |
| | 115 | 100 | | Ranks[firstRoot] = Math.Max(Ranks[firstRoot], Ranks[secondRoot] + 1); |
| | 115 | 101 | | } |
| | | 102 | | else |
| | 15 | 103 | | { |
| | 15 | 104 | | Parents[firstRoot] = secondRoot; |
| | 15 | 105 | | Ranks[secondRoot] = Math.Max(Ranks[secondRoot], Ranks[firstRoot] + 1); |
| | 15 | 106 | | } |
| | 130 | 107 | | } |
| | | 108 | | } |