data_structures
union_find.h
Go to the documentation of this file.
1 /* ************************************************************************** */
3 /* */
4 /* ::: :::::::: */
5 /* union_find.h :+: :+: :+: */
6 /* +:+ +:+ +:+ */
7 /* By: unite <marvin@42.fr> +#+ +:+ +#+ */
8 /* +#+#+#+#+#+ +#+ */
9 /* Created: 2020/07/21 21:49:30 by unite #+# #+# */
10 /* Updated: 2020/09/07 22:20:25 by unite ### ########.fr */
11 /* */
12 /* ************************************************************************** */
13 
14 #ifndef UNION_FIND
15 
16 # define UNION_FIND
17 
18 # include <errno.h>
19 # include <sys/types.h>
20 # include "types.h"
21 # include "utils.h"
22 
36 typedef struct s_union_find
37 {
38  size_t *parent;
39  size_t *nchild;
40  size_t size;
41  size_t count;
42 } t_union_find;
43 
49 t_union_find *union_find_new(size_t size);
50 
58 void union_find_union(t_union_find *uf, size_t p, size_t q);
59 
65 size_t union_find_count(const t_union_find *uf);
66 
72 size_t union_find_size(const t_union_find *uf);
73 
80 
87 size_t union_find_find(const t_union_find *uf, size_t p);
88 
89 #endif
s_union_find::count
size_t count
The number of disconnected sets.
Definition: union_find.h:41
s_union_find::parent
size_t * parent
An array with each element's parent.
Definition: union_find.h:38
s_union_find
Weighted quick-union by rank with path compression by halving.
Definition: union_find.h:36
types.h
utils.h
union_find_delete
void union_find_delete(t_union_find *uf)
Deletes the union-find and frees all memory taken by its contents, or does nothing if the argument is...
Definition: union_find_delete.c:16
union_find_size
size_t union_find_size(const t_union_find *uf)
Returns the number of elements in this union-find.
Definition: union_find_size.c:16
union_find_find
size_t union_find_find(const t_union_find *uf, size_t p)
Returns the canonical element of the set containing the specified element.
Definition: union_find_find.c:16
union_find_count
size_t union_find_count(const t_union_find *uf)
Returns the number of disconnected sets.
Definition: union_find_count.c:16
union_find_union
void union_find_union(t_union_find *uf, size_t p, size_t q)
Merges the set containing element p with the set containing element q.
Definition: union_find_union.c:16
union_find_new
t_union_find * union_find_new(size_t size)
Initializes a new union-find data structure of the specified size.
Definition: union_find_new.c:16
s_union_find::nchild
size_t * nchild
An array with the number of each element's children.
Definition: union_find.h:39
s_union_find::size
size_t size
The number of elements.
Definition: union_find.h:40