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) |
void SCIPdisjointsetClear | ( | SCIP_DISJOINTSET * | djset | ) |
clears the disjoint set (union find) structure uf
djset | disjoint set (union find) data structure |
Definition at line 10359 of file misc.c.
References SCIP_DisjointSet::componentcount, SCIP_DisjointSet::parents, SCIP_DisjointSet::size, and SCIP_DisjointSet::sizes.
Referenced by SCIPdisjointsetCreate(), and SCIPrealHashCode().
int SCIPdisjointsetFind | ( | SCIP_DISJOINTSET * | djset, |
int | element | ||
) |
finds and returns the component identifier of this element
djset | disjoint set (union find) data structure |
element | element to be found |
Definition at line 10376 of file misc.c.
References SCIP_DisjointSet::parents.
Referenced by computeComponents(), SCIPcliquetableGetVarComponentIdx(), SCIPdisjointsetUnion(), and SCIPrealHashCode().
void SCIPdisjointsetUnion | ( | SCIP_DISJOINTSET * | djset, |
int | p, | ||
int | q, | ||
SCIP_Bool | forcerepofp | ||
) |
merges the components containing the elements p
and q
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 10403 of file misc.c.
References SCIP_DisjointSet::componentcount, SCIP_DisjointSet::parents, SCIPdisjointsetFind(), SCIP_DisjointSet::size, and SCIP_DisjointSet::sizes.
Referenced by cliquetableUpdateConnectednessClique(), computeComponents(), and SCIPrealHashCode().
int SCIPdisjointsetGetComponentCount | ( | SCIP_DISJOINTSET * | djset | ) |
returns the number of independent components in this disjoint set (union find) data structure
djset | disjoint set (union find) data structure |
Definition at line 10474 of file misc.c.
References SCIP_DisjointSet::componentcount.
Referenced by SCIPcliquetableComputeCliqueComponents(), and SCIPrealHashCode().
int SCIPdisjointsetGetSize | ( | SCIP_DISJOINTSET * | djset | ) |
returns the size (number of nodes) of this disjoint set (union find) data structure
djset | disjoint set (union find) data structure |
Definition at line 10484 of file misc.c.
References SCIP_DisjointSet::size.
Referenced by SCIPcliquetableGetVarComponentIdx(), and SCIPrealHashCode().
SCIP_RETCODE SCIPcreateDisjointset | ( | SCIP * | scip, |
SCIP_DISJOINTSET ** | djset, | ||
int | ncomponents | ||
) |
creates a disjoint set (union find) structure uf
for ncomponents
many components (of size one)
scip | SCIP data structure |
djset | disjoint set (union find) data structure |
ncomponents | number of components |
Definition at line 48651 of file scip.c.
References Scip::mem, SCIP_Mem::probmem, SCIP_CALL, SCIP_OKAY, and SCIPdisjointsetCreate().
void SCIPfreeDisjointset | ( | SCIP * | scip, |
SCIP_DISJOINTSET ** | djset | ||
) |
frees the disjoint set (union find) data structure
scip | SCIP data structure |
djset | disjoint set (union find) data structure |
Definition at line 48666 of file scip.c.
References Scip::mem, SCIP_Mem::probmem, and SCIPdisjointsetFree().