Woolz Image Processing  Version 1.8.3
AlcUFTree.c File Reference

A general purpose union tree based on Sedgewick's Weighted Quick Union Find, see Robert Sedgewick, Kevin Wayne "Algorithms (4th Edition)". There is very little parameter checking in these functions and all given parameters must be valid. More...

Functions

void AlcUFTreeFree (AlcUFTree *uft)
 Free a union find tree data structure. More...
 
void AlcUFTreeInit (AlcUFTree *uft, int n)
 Initialises a union find tree data structure to allow reuse. More...
 
AlcUFTreeAlcUFTreeNew (int maxNod, int nNod)
 Creates a union find tree data structure which is required by all the other AlcUFTree functions. More...
 
int AlcUFTreeFind (AlcUFTree *uft, int p)
 Finds the component containing the given node. More...
 
int AlcUFTreeConnected (AlcUFTree *uft, int p, int q)
 Returns non-zero if the two given nodes are connected, ie if they are in the same component. More...
 
void AlcUFTreeUnion (AlcUFTree *uft, int p, int q)
 If the two given nodes have different components then their components are merged to form one. More...
 

Detailed Description

A general purpose union tree based on Sedgewick's Weighted Quick Union Find, see Robert Sedgewick, Kevin Wayne "Algorithms (4th Edition)". There is very little parameter checking in these functions and all given parameters must be valid.

Author
Bill Hill
Date
September 2014
Version
Id
70eb29108826f880f97f2637d03e9a2bb5287ea6
Address: MRC Human Genetics Unit, MRC Institute of Genetics and Molecular Medicine, University of Edinburgh, Western General Hospital, Edinburgh, EH4 2XU, UK.
Copyright (C), [2014], The University Court of the University of Edinburgh, Old College, Edinburgh, UK.

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

Function Documentation

◆ AlcUFTreeFree()

void AlcUFTreeFree ( AlcUFTree uft)

Free a union find tree data structure.

Parameters
uftGiven union find tree.

References AlcFree(), and _AlcUFTree::pr.

Referenced by WlzLabel3D().

◆ AlcUFTreeInit()

void AlcUFTreeInit ( AlcUFTree uft,
int  n 
)

Initialises a union find tree data structure to allow reuse.

Parameters
uftThe union find tree.
nNumber of nodes, which must be \(leq\) the value of maxNod in the data structure..

References _AlcUFTree::nCmp, _AlcUFTree::nNod, _AlcUFTree::pr, and _AlcUFTree::sz.

Referenced by AlcUFTreeNew().

◆ AlcUFTreeNew()

AlcUFTree* AlcUFTreeNew ( int  maxNod,
int  nNod 
)

Creates a union find tree data structure which is required by all the other AlcUFTree functions.

Returns
Union find tree, or NULL on error.
Parameters
maxNodMaximum number of nodes space allocated for.
nNodNumber of nodes.

References AlcCalloc(), AlcFree(), AlcMalloc(), AlcUFTreeInit(), _AlcUFTree::maxNod, _AlcUFTree::pr, and _AlcUFTree::sz.

Referenced by WlzLabel3D().

◆ AlcUFTreeFind()

int AlcUFTreeFind ( AlcUFTree uft,
int  p 
)

Finds the component containing the given node.

Returns
The component containing the given node.
Parameters
uftThe union find tree.
pGiven node.

References _AlcUFTree::pr.

Referenced by AlcUFTreeConnected(), AlcUFTreeUnion(), and WlzLabel3D().

◆ AlcUFTreeConnected()

int AlcUFTreeConnected ( AlcUFTree uft,
int  p,
int  q 
)

Returns non-zero if the two given nodes are connected, ie if they are in the same component.

Returns
Non-zero if the nodes are connected.
Parameters
uftThe union find tree.
pNode in first component.
qNode in second component.

References AlcUFTreeFind().

◆ AlcUFTreeUnion()

void AlcUFTreeUnion ( AlcUFTree uft,
int  p,
int  q 
)

If the two given nodes have different components then their components are merged to form one.

Parameters
uftThe union find tree.
pNode in first component.
qNode in second component.

References AlcUFTreeFind(), _AlcUFTree::nCmp, _AlcUFTree::pr, and _AlcUFTree::sz.

Referenced by WlzLabel3D().