/* Tobin Fricke's implementation of the
Hoshen-Kopelman algorithm for
cluster labeling.
Copyright (c) September 9, 2000, by Tobin Fricke
Distributed under the terms of the GNU Public License.
Modified 2002-03-09 Tobin Fricke
Modified substantially 2004-04-21 by Tobin Fricke
This program is written in the 1999 standard of the C language (C99). Older C
compilers will refuse to compile it. You can use a C++ compiler, a C99 compiler,
or you can modify this code to comply with a previous version of the C standard.
The GCC compiler supports C99 as of version 3.0. Compile this program with:
gcc-3.0 -Wall -std=c99 hk.c -o hk
http://www.ocf.berkeley.edu/~fricke/projects/hoshenkopelman/hoshenkopelman.html
*/
#include
#include
#include
/* #include "hk.h" */
/* Implementation of Union-Find Algorithm */
/* The 'labels' array has the meaning that labels[x] is an alias for the label x; by
following this chain until x == labels[x], you can find the canonical name of an
equivalence class. The labels start at one; labels[0] is a special value indicating
the highest label already used. */
int *labels;
int n_labels = 0; /* length of the labels array */
/* uf_find returns the canonical label for the equivalence class containing x */
int uf_find(int x) {
int y = x;
while (labels[y] != y)
y = labels[y];
while (labels[x] != x) {
int z = labels[x];
labels[x] = y;
x = z;
}
return y;
}
/* uf_union joins two equivalence classes and returns the canonical label of the resulting class. */
int uf_union(int x, int y) {
return labels[uf_find(x)] = uf_find(y);
}
/* uf_make_set creates a new equivalence class and returns its label */
int uf_make_set(void) {
labels[0] ++;
assert(labels[0] < n_labels);
labels[labels[0]] = labels[0];
return labels[0];
}
/* uf_intitialize sets up the data structures needed by the union-find implementation. */
void uf_initialize(int max_labels) {
n_labels = max_labels;
labels = calloc(sizeof(int), n_labels);
labels[0] = 0;
}
/* uf_done frees the memory used by the union-find data structures */
void uf_done(void) {
n_labels = 0;
free(labels);
labels = 0;
}
/* End Union-Find implementation */
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?b:a)
/* print_matrix prints out a matrix that is set up in the "pointer to pointers" scheme
(aka, an array of arrays); this is incompatible with C's usual representation of 2D
arrays, but allows for 2D arrays with dimensions determined at run-time */
void print_matrix(int **matrix, int m, int n) {
for (int i=0; i