SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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
djsetdisjoint set (union find) data structure

Definition at line 11164 of file misc.c.

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

Referenced by SCIPdisjointsetCreate().

◆ SCIPdisjointsetFind()

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 11181 of file misc.c.

References i, and SCIP_DisjointSet::parents.

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

◆ SCIPdisjointsetUnion()

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 11208 of file misc.c.

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

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

◆ SCIPdisjointsetGetComponentCount()

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 11278 of file misc.c.

References assert(), SCIP_DisjointSet::componentcount, and NULL.

Referenced by buildSubgroupGraph(), and SCIPcliquetableComputeCliqueComponents().

◆ SCIPdisjointsetGetSize()

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 11288 of file misc.c.

References assert(), NULL, and SCIP_DisjointSet::size.

Referenced by SCIPcliquetableGetVarComponentIdx().

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

Definition at line 654 of file scip_datastructures.c.

References assert(), NULL, 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
scipSCIP data structure
djsetdisjoint set (union find) data structure

Definition at line 669 of file scip_datastructures.c.

References assert(), NULL, and SCIPdisjointsetFree().

Referenced by buildSubgroupGraph().