Disjoint Set (Union Find)

Detailed Description

weighted disjoint set (union find) data structure with path compression

Weighted Disjoint Set is a data structure to quickly update and query connectedness information between nodes of a graph. Disjoint Set is also known as Union Find.

Functions
void	SCIPdisjointsetClear (SCIP_DISJOINTSET *djset)
int	SCIPdisjointsetFind (SCIP_DISJOINTSET *djset, int element)
void	SCIPdisjointsetUnion (SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
int	SCIPdisjointsetGetComponentCount (SCIP_DISJOINTSET *djset)
int	SCIPdisjointsetGetSize (SCIP_DISJOINTSET *djset)
SCIP_RETCODE	SCIPcreateDisjointset (SCIP *scip, SCIP_DISJOINTSET **djset, int ncomponents)
void	SCIPfreeDisjointset (SCIP *scip, SCIP_DISJOINTSET **djset)

Function Documentation

SCIPdisjointsetClear()

void SCIPdisjointsetClear

(

SCIP_DISJOINTSET *

djset

)

clears the disjoint set (union find) structure djset

Parameters

djset

disjoint set (union find) data structure

Definition at line 11164 of file misc.c.

References SCIP_DisjointSet::componentcount, SCIP_DisjointSet::parents, SCIP_DisjointSet::size, and SCIP_DisjointSet::sizes.

Referenced by SCIPdisjointsetCreate(), and SCIPrealHashCode().

SCIPdisjointsetFind()

int SCIPdisjointsetFind	(	SCIP_DISJOINTSET *	djset,
		int	element
	)

finds and returns the component identifier of this element

Parameters

djset	disjoint set (union find) data structure
element	element to be found

Definition at line 11181 of file misc.c.

References SCIP_DisjointSet::parents.

Referenced by buildSubgroupGraph(), SCIPcliquetableGetVarComponentIdx(), SCIPcomputeComponentsSym(), SCIPdisjointsetUnion(), and SCIPrealHashCode().

SCIPdisjointsetUnion()

void SCIPdisjointsetUnion	(	SCIP_DISJOINTSET *	djset,
		int	p,
		int	q,
		SCIP_Bool	forcerepofp
	)

merges the components containing the elements p and q

Parameters

djset	disjoint set (union find) data structure
p	first element
q	second element
forcerepofp	force representative of p to be new representative

Definition at line 11208 of file misc.c.

References SCIP_DisjointSet::componentcount, NULL, SCIP_DisjointSet::parents, SCIPdisjointsetFind(), SCIP_DisjointSet::size, and SCIP_DisjointSet::sizes.

Referenced by buildSubgroupGraph(), cliquetableUpdateConnectednessClique(), SCIPcomputeComponentsSym(), and SCIPrealHashCode().

SCIPdisjointsetGetComponentCount()

int SCIPdisjointsetGetComponentCount

(

SCIP_DISJOINTSET *

djset

)

returns the number of independent components in this disjoint set (union find) data structure

Parameters

djset

disjoint set (union find) data structure

Definition at line 11278 of file misc.c.

References SCIP_DisjointSet::componentcount, and NULL.

Referenced by buildSubgroupGraph(), SCIPcliquetableComputeCliqueComponents(), and SCIPrealHashCode().

SCIPdisjointsetGetSize()

int SCIPdisjointsetGetSize

(

SCIP_DISJOINTSET *

djset

)

returns the size (number of nodes) of this disjoint set (union find) data structure

Parameters

djset

disjoint set (union find) data structure

Definition at line 11288 of file misc.c.

References NULL, and SCIP_DisjointSet::size.

Referenced by SCIPcliquetableGetVarComponentIdx(), and SCIPrealHashCode().

SCIPcreateDisjointset()

SCIP_RETCODE SCIPcreateDisjointset	(	SCIP *	scip,
		SCIP_DISJOINTSET **	djset,
		int	ncomponents
	)

creates a disjoint set (union find) structure djset for ncomponents many components (of size one)

creates a disjoint set (union find) structure uf for ncomponents many components (of size one)

Parameters

scip	SCIP data structure
djset	disjoint set (union find) data structure
ncomponents	number of components

Definition at line 654 of file scip_datastructures.c.

References Scip::mem, NULL, SCIP_Mem::probmem, SCIP_CALL, SCIP_OKAY, and SCIPdisjointsetCreate().

Referenced by buildSubgroupGraph().

SCIPfreeDisjointset()

void SCIPfreeDisjointset	(	SCIP *	scip,
		SCIP_DISJOINTSET **	djset
	)

frees the disjoint set (union find) data structure

Parameters

scip	SCIP data structure
djset	disjoint set (union find) data structure

Definition at line 669 of file scip_datastructures.c.

References Scip::mem, NULL, SCIP_Mem::probmem, and SCIPdisjointsetFree().

Referenced by buildSubgroupGraph().