Scippy

SCIP

Solving Constraint Integer Programs

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

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

Function Documentation

◆ SCIPdisjointsetClear()

SCIP_EXPORT void SCIPdisjointsetClear ( SCIP_DISJOINTSET djset)

clears the disjoint set (union find) structure djset

Parameters
djsetdisjoint set (union find) data structure

Definition at line 10639 of file misc.c.

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

Referenced by SCIPdisjointsetCreate(), and SCIPrealHashCode().

◆ SCIPdisjointsetFind()

SCIP_EXPORT int SCIPdisjointsetFind ( SCIP_DISJOINTSET djset,
int  element 
)

finds and returns the component identifier of this element

Parameters
djsetdisjoint set (union find) data structure
elementelement to be found

Definition at line 10656 of file misc.c.

References SCIP_DisjointSet::parents.

Referenced by computeComponents(), SCIPcliquetableGetVarComponentIdx(), SCIPdisjointsetUnion(), and SCIPrealHashCode().

◆ SCIPdisjointsetUnion()

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

merges the components containing the elements p and q

Parameters
djsetdisjoint set (union find) data structure
pfirst element
qsecond element
forcerepofpforce representative of p to be new representative

Definition at line 10683 of file misc.c.

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

Referenced by cliquetableUpdateConnectednessClique(), computeComponents(), and SCIPrealHashCode().

◆ SCIPdisjointsetGetComponentCount()

SCIP_EXPORT int SCIPdisjointsetGetComponentCount ( SCIP_DISJOINTSET djset)

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

Parameters
djsetdisjoint set (union find) data structure

Definition at line 10753 of file misc.c.

References SCIP_DisjointSet::componentcount, and NULL.

Referenced by SCIPcliquetableComputeCliqueComponents(), and SCIPrealHashCode().

◆ SCIPdisjointsetGetSize()

SCIP_EXPORT int SCIPdisjointsetGetSize ( SCIP_DISJOINTSET djset)

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

Parameters
djsetdisjoint set (union find) data structure

Definition at line 10763 of file misc.c.

References NULL, and SCIP_DisjointSet::size.

Referenced by SCIPcliquetableGetVarComponentIdx(), and SCIPrealHashCode().

◆ SCIPcreateDisjointset()

SCIP_EXPORT 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
scipSCIP data structure
djsetdisjoint set (union find) data structure
ncomponentsnumber of components

Definition at line 644 of file scip_datastructures.c.

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

Referenced by computeComponents().

◆ SCIPfreeDisjointset()

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

frees the disjoint set (union find) data structure

Parameters
scipSCIP data structure
djsetdisjoint set (union find) data structure

Definition at line 659 of file scip_datastructures.c.

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

Referenced by computeComponents().