Documentation/core-api/union_find.rst

Source file repositories/reference/linux-study-clean/Documentation/core-api/union_find.rst

File Facts

System
Linux kernel
Corpus path
Documentation/core-api/union_find.rst
Extension
.rst
Size
3557 bytes
Lines
107
Domain
Support Tooling And Documentation
Bucket
Documentation
Inferred role
Support Tooling And Documentation: documentation
Status
atlas-only

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

struct uf_node {
		struct uf_node *parent;
		unsigned int rank;
	};

In this structure, parent points to the parent node of the current node.
The rank field represents the height of the current tree. During a union
operation, the tree with the smaller rank is attached under the tree with the
larger rank to maintain balance.

Initializing union-find
-----------------------

You can complete the initialization using either static or initialization
interface. Initialize the parent pointer to point to itself and set the rank
to 0.
Example::

	struct uf_node my_node = UF_INIT_NODE(my_node);

or

	uf_node_init(&my_node);

Find the Root Node of union-find
--------------------------------

This operation is mainly used to determine whether two nodes belong to the same
set in the union-find. If they have the same root, they are in the same set.
During the find operation, path compression is performed to improve the
efficiency of subsequent find operations.
Example::

	int connected;
	struct uf_node *root1 = uf_find(&node_1);
	struct uf_node *root2 = uf_find(&node_2);
	if (root1 == root2)
		connected = 1;
	else
		connected = 0;

Union Two Sets in union-find
----------------------------

To union two sets in the union-find, you first find their respective root nodes
and then link the smaller node to the larger node based on the rank of the root
nodes.
Example::

	uf_union(&node_1, &node_2);

Annotation

Implementation Notes