| | | 1 | | namespace MoreStructures.DisjointSets; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// A <see cref="WeightedQuickUnionDisjointSet"/> refinement which improves the performance of the data structure by |
| | | 5 | | /// performing a technique known as <b>path compression</b>. |
| | | 6 | | /// </summary> |
| | | 7 | | /// <remarks> |
| | | 8 | | /// This variant of <see cref="WeightedQuickUnionDisjointSet"/> introduces a refinement of the |
| | | 9 | | /// <see cref="IDisjointSet.Find(int)"/> method, inherited by its upper classes. |
| | | 10 | | /// <br/> |
| | | 11 | | /// The <see cref="Find(int)"/> algorithm remains unchanged in its core. |
| | | 12 | | /// <br/> |
| | | 13 | | /// However, it produces a flatter forest as side-effect, every time is executed on a value. |
| | | 14 | | /// <br/> |
| | | 15 | | /// Check the documentation of <see cref="Find(int)"/> for further details. |
| | | 16 | | /// </remarks> |
| | | 17 | | public class PathCompressionWeightedQuickUnionDisjointSet : WeightedQuickUnionDisjointSet |
| | | 18 | | { |
| | | 19 | | /// <inheritdoc/> |
| | 37 | 20 | | public PathCompressionWeightedQuickUnionDisjointSet(int valuesCount) : base(valuesCount) |
| | 35 | 21 | | { |
| | 35 | 22 | | } |
| | | 23 | | |
| | | 24 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 25 | | /// <remarks> |
| | | 26 | | /// <para id="algorithm"> |
| | | 27 | | /// ALGORITHM |
| | | 28 | | /// <br/> |
| | | 29 | | /// - The algorithm is pretty much like <see cref="QuickUnionDisjointSet.Find(int)"/>, with one main |
| | | 30 | | /// difference. |
| | | 31 | | /// <br/> |
| | | 32 | | /// - The difference lies in <b>path compression</b>: once the root of the tree is found, a second traversal, |
| | | 33 | | /// from the <paramref name="value"/> up to its root, is performed. |
| | | 34 | | /// <br/> |
| | | 35 | | /// - During the second traversal, each node in path is directly attached to the root. |
| | | 36 | | /// <br/> |
| | | 37 | | /// - That keeps the disjoint set equivalent to its previous state, by transitivity of the equivalence |
| | | 38 | | /// relationship. |
| | | 39 | | /// <br/> |
| | | 40 | | /// - However, it makes the tree much more flat, and the average height of all the nodes in the forest smaller. |
| | | 41 | | /// <br/> |
| | | 42 | | /// - That means that future <see cref="Find(int)"/>, but also <see cref="IDisjointSet.Union(int, int)"/> and |
| | | 43 | | /// <see cref="IDisjointSet.AreConnected(int, int)"/>, will be much faster, since it's faster to reach the |
| | | 44 | | /// root of each tree. |
| | | 45 | | /// </para> |
| | | 46 | | /// <para id="complexity"> |
| | | 47 | | /// COMPLEXITY |
| | | 48 | | /// <br/> |
| | | 49 | | /// - Find the root takes a time proportional to the height of the tree, the item is in. |
| | | 50 | | /// <br/> |
| | | 51 | | /// - Because path compression keeps trees very flat, incrementing the fan out, while the complexity is not |
| | | 52 | | /// constant and there is definitely a dependence over n, it is a sub-logarithmic dependency. |
| | | 53 | | /// <br/> |
| | | 54 | | /// - More precisely, Time Complexity is O(log*(n)), which can be considered "pseudo-constant" for any |
| | | 55 | | /// "real world" value of n. |
| | | 56 | | /// <br/> |
| | | 57 | | /// - Space Complexity remains O(1), since only a constant amount of additional space is required to run the |
| | | 58 | | /// algorithm. |
| | | 59 | | /// </para> |
| | | 60 | | /// </remarks> |
| | | 61 | | public override int Find(int value) |
| | 255 | 62 | | { |
| | 255 | 63 | | if (ValuesCount == 0) |
| | 1 | 64 | | throw new InvalidOperationException( |
| | 1 | 65 | | $"{nameof(AreConnected)} cannot be invoked on an empty set."); |
| | 254 | 66 | | if (value < 0 || value >= ValuesCount) |
| | 3 | 67 | | throw new ArgumentException( |
| | 3 | 68 | | $"Must be non-negative and smaller than {nameof(ValuesCount)}.", nameof(value)); |
| | | 69 | | |
| | 251 | 70 | | var root = value; |
| | 323 | 71 | | while (Parents[root] != root) |
| | 72 | 72 | | { |
| | 72 | 73 | | root = Parents[root]; |
| | 72 | 74 | | } |
| | | 75 | | |
| | 323 | 76 | | while (Parents[value] != value) |
| | 72 | 77 | | { |
| | 72 | 78 | | var parent = Parents[value]; |
| | 72 | 79 | | Parents[value] = root; |
| | 72 | 80 | | value = parent; |
| | 72 | 81 | | } |
| | | 82 | | |
| | 251 | 83 | | return root; |
| | 251 | 84 | | } |
| | | 85 | | } |