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().