libFirm

Union-Find data structure. More...

Functions

static void uf_init (int *const data, size_t const n_elems)
 Call this to initialize an array of count elements to be used by the union find functions. More...
 
static int uf_union (int *const data, int const set1, int const set2)
 Merge 2 sets (union operation). More...
 
static int uf_find (int *const data, int const e)
 Finds the representative for the set with member e. More...
 

Detailed Description

Union-Find data structure.

This implementation uses weighted sets and path compression which results in (nearly) O(n) complexity for n find and union operations

Function Documentation

static int uf_find ( int *const  data,
int const  e 
)
inlinestatic

Finds the representative for the set with member e.

The representative of a set is unique, so if the find operations finds the same/different representatives, then the elements are in the the same/different sets.

Parameters
dataThe union find data
eThe element
Returns
The representative of the set that contains e

Definition at line 83 of file unionfind.h.

static void uf_init ( int *const  data,
size_t const  n_elems 
)
inlinestatic

Call this to initialize an array of count elements to be used by the union find functions.

Parameters
dataThe array (you have to allocate it yourself)
n_elemsnumber of elements handled by the data structure

Definition at line 35 of file unionfind.h.

static int uf_union ( int *const  data,
int const  set1,
int const  set2 
)
inlinestatic

Merge 2 sets (union operation).

Note that you have to pass the representatives of the sets and not just random elements

Parameters
dataThe union find data
set1Representative of set1
set2Representative of set2
Returns
the new representative of the set (which is set1 or set2)

Definition at line 51 of file unionfind.h.