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
-
djset disjoint set (union find) data structure
Definition at line 10980 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
-
djset disjoint set (union find) data structure element element to be found
Definition at line 10997 of file misc.c.
References SCIP_DisjointSet::parents.
Referenced by SCIPcliquetableGetVarComponentIdx(), SCIPcomputeComponentsSym(), 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
-
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 11024 of file misc.c.
References SCIP_DisjointSet::componentcount, NULL, SCIP_DisjointSet::parents, SCIPdisjointsetFind(), SCIP_DisjointSet::size, and SCIP_DisjointSet::sizes.
Referenced by cliquetableUpdateConnectednessClique(), SCIPcomputeComponentsSym(), 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
-
djset disjoint set (union find) data structure
Definition at line 11094 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
-
djset disjoint set (union find) data structure
Definition at line 11104 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
-
scip SCIP data structure djset disjoint set (union find) data structure ncomponents number of components
Definition at line 645 of file scip_datastructures.c.
References Scip::mem, NULL, SCIP_Mem::probmem, SCIP_CALL, SCIP_OKAY, and SCIPdisjointsetCreate().
◆ SCIPfreeDisjointset()
SCIP_EXPORT 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 660 of file scip_datastructures.c.
References Scip::mem, NULL, SCIP_Mem::probmem, and SCIPdisjointsetFree().