Documentation/core-api/union_find.rst

   1 .. SPDX-License-Identifier: GPL-2.0
   2
   3 ====================
   4 Union-Find in Linux
   5 ====================
   6
   7
   8 :Date: June 21, 2024
   9 :Author: Xavier <xavier_qy@163.com>
  10
  11 What is union-find, and what is it used for?
  12 ------------------------------------------------
  13
  14 Union-find is a data structure used to handle the merging and querying
  15 of disjoint sets. The primary operations supported by union-find are:
  16
  17         Initialization: Resetting each element as an individual set, with
  18                 each set's initial parent node pointing to itself.
  19
  20         Find: Determine which set a particular element belongs to, usually by
  21                 returning a “representative element” of that set. This operation
  22                 is used to check if two elements are in the same set.
  23
  24         Union: Merge two sets into one.
  25
  26 As a data structure used to maintain sets (groups), union-find is commonly
  27 utilized to solve problems related to offline queries, dynamic connectivity,
  28 and graph theory. It is also a key component in Kruskal's algorithm for
  29 computing the minimum spanning tree, which is crucial in scenarios like
  30 network routing. Consequently, union-find is widely referenced. Additionally,
  31 union-find has applications in symbolic computation, register allocation,
  32 and more.
  33
  34 Space Complexity: O(n), where n is the number of nodes.
  35
  36 Time Complexity: Using path compression can reduce the time complexity of
  37 the find operation, and using union by rank can reduce the time complexity
  38 of the union operation. These optimizations reduce the average time
  39 complexity of each find and union operation to O(α(n)), where α(n) is the
  40 inverse Ackermann function. This can be roughly considered a constant time
  41 complexity for practical purposes.
  42
  43 This document covers use of the Linux union-find implementation.  For more
  44 information on the nature and implementation of union-find,  see:
  45
  46   Wikipedia entry on union-find
  47     https://en.wikipedia.org/wiki/Disjoint-set_data_structure
  48
  49 Linux implementation of union-find
  50 -----------------------------------
  51
  52 Linux's union-find implementation resides in the file "lib/union_find.c".
  53 To use it, "#include <linux/union_find.h>".
  54
  55 The union-find data structure is defined as follows::
  56
  57         struct uf_node {
  58                 struct uf_node *parent;
  59                 unsigned int rank;
  60         };
  61
  62 In this structure, parent points to the parent node of the current node.
  63 The rank field represents the height of the current tree. During a union
  64 operation, the tree with the smaller rank is attached under the tree with the
  65 larger rank to maintain balance.
  66
  67 Initializing union-find
  68 -----------------------
  69
  70 You can complete the initialization using either static or initialization
  71 interface. Initialize the parent pointer to point to itself and set the rank
  72 to 0.
  73 Example::
  74
  75         struct uf_node my_node = UF_INIT_NODE(my_node);
  76
  77 or
  78
  79         uf_node_init(&my_node);
  80
  81 Find the Root Node of union-find
  82 --------------------------------
  83
  84 This operation is mainly used to determine whether two nodes belong to the same
  85 set in the union-find. If they have the same root, they are in the same set.
  86 During the find operation, path compression is performed to improve the
  87 efficiency of subsequent find operations.
  88 Example::
  89
  90         int connected;
  91         struct uf_node *root1 = uf_find(&node_1);
  92         struct uf_node *root2 = uf_find(&node_2);
  93         if (root1 == root2)
  94                 connected = 1;
  95         else
  96                 connected = 0;
  97
  98 Union Two Sets in union-find
  99 ----------------------------
 100
 101 To union two sets in the union-find, you first find their respective root nodes
 102 and then link the smaller node to the larger node based on the rank of the root
 103 nodes.
 104 Example::
 105
 106         uf_union(&node_1, &node_2);