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...
AlcUFTree *	AlcUFTreeNew (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

uft	Given 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

uft	The union find tree.
n	Number 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

maxNod	Maximum number of nodes space allocated for.
nNod	Number 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

uft	The union find tree.
p	Given 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

uft	The union find tree.
p	Node in first component.
q	Node 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

uft	The union find tree.
p	Node in first component.
q	Node in second component.

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

Referenced by WlzLabel3D().