EGeSet

---

Detailed Description

This is an implementation of the set's defined at 'Data Structures and Network Algorithms' of Robert Endre Tarjan. This structures allow to work with disjoint setswith a representant (thus an equivalence class) and ask the basic question of, given an elment, who is the representant if his class, make a set, link two sets (i.e. union if them) and given a representant link an element to that class.

Version:

0.0.1

History:

• 2005-06-20
  • First Implementation.

Files
file	eg_eset.h
Data Structures
struct	EGes_t
	this structure holds an element of a set More...
Defines
#define	EG_ESET_DLEVEL   0
#define	EGesFind(elem)
	this function find the representant of this element in his equivalence set.
#define	EGesInit(elem)
	Initialize a set element as a set containing only itsself.
#define	EGesLink(u, v)
	Given two representing elements for two clases, joint them into a single class.
Typedefs
typedef EGes_t	EGes_t
	this structure holds an element of a set

---

Define Documentation

#define EG_ESET_DLEVEL   0

Definition at line 47 of file eg_eset.h.

#define EGesFind (  elem   )

Value: ({\ EGes_t *_EGesFc = elem, *_EGesFn;\ while(_EGesFc != _EGesFc->father)\ {\ _EGesFn = _EGesFc->father;\ _EGesFc->father = _EGesFn->father;\ _EGesFc = _EGesFn;\ }\ _EGesFc;}) this function find the representant of this element in his equivalence set. Parameters: elem  pointer to the element to wich we want to find the representant. Returns: the representant for this set (EGes_t*). Definition at line 73 of file eg_eset.h.

#define EGesInit (  elem   )

Value: ({\ EGes_t*const __EGesElm = (elem);\ *__EGesElm = (EGes_t){__EGesElm,0};}) Initialize a set element as a set containing only itsself. Definition at line 63 of file eg_eset.h.

#define EGesLink (  u, v   )

Value: ({\ EGes_t *_EGes_lu = (u), *_EGes_lv = (v);\ EXITL(EG_ESET_DLEVEL, _EGes_lu != _EGes_lu->father, #u\ " is not a representant for its class");\ EXITL(EG_ESET_DLEVEL, _EGes_lv != _EGes_lv->father, #v\ " is not a representant for its class");\ EXITL(EG_ESET_DLEVEL, _EGes_lu == _EGes_lv, "same representant v == u");\ if(_EGes_lu->rank <= _EGes_lv->rank) _EGes_lu->rank = _EGes_lv->rank+1;\ _EGes_lv->father = _EGes_lu;\ _EGes_lu;}) Given two representing elements for two clases, joint them into a single class. Parameters: u  first representative. v  second representative. Returns: the representing element of the new class. Note: This implementation always let the first element to be the representative for the new class. Definition at line 91 of file eg_eset.h.

---

Typedef Documentation

typedef struct EGes_t EGes_t

this structure holds an element of a set

---