EGeSet

Data Structures
struct	EGes_t
	this structure holds an element of a set More...
Files
file	eg_eset.h
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 struct EGes_t	EGes_t
	this structure holds an element of a set

---

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.

---

Define Documentation

#define EG_ESET_DLEVEL   0

Definition at line 44 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 70 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 60 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 88 of file eg_eset.h.

---

Typedef Documentation

typedef struct EGes_t EGes_t

this structure holds an element of a set