Disjoint-set

Disjoint-set implementation. More...

Files
file	set.h
	Header file for disjoint-set data structure.

Data Structures
struct	sys_set_node
	Disjoint-set node structure. More...

Functions
static void	sys_set_makeset (struct sys_set_node *node, uint16_t rank)
	Initialize a disjoint-set.
struct sys_set_node *	sys_set_find (struct sys_set_node *node)
	Find the root of the disjoint-set.
void	sys_set_union (struct sys_set_node *node1, struct sys_set_node *node2)
	Merge two nodes into the same disjoint-set.

Detailed Description

Disjoint-set implementation.

This implements a disjoint-set (union-find) that guarantees O(alpha(n)) runtime for all operations. The algorithms and naming are conventional per existing academic and didactic implementations, c.f.:

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Function Documentation

sys_set_find()

struct sys_set_node * sys_set_find

(

struct sys_set_node *

node

)

#include <zephyr/sys/set.h>

Find the root of the disjoint-set.

Parameters

node	Pointer to a sys_set_node structure.

Returns

Pointer to the root sys_set_node of the set containing the node.

sys_set_makeset()

void sys_set_makeset ( struct sys_set_node * node, uint16_t rank )

inlinestatic

#include <zephyr/sys/set.h>

Initialize a disjoint-set.

Parameters

node	Pointer to a sys_set_node structure.
rank	Initial rank (usually set to 0).

sys_set_union()

void sys_set_union	(	struct sys_set_node *	node1,
		struct sys_set_node *	node2 )

#include <zephyr/sys/set.h>

Merge two nodes into the same disjoint-set.

This function attaches the node with the smaller rank to the one with the larger rank. That say, if node1 has a smaller rank than node2, it will be linked to node2.

Parameters

node1	Pointer to a sys_set_node structure.
node2	Pointer to a sys_set_node structure.