unfnd.c

用改进的数据结构快速计算复杂网络的社区划分

/*-
 * Copyright (c) 2008, Alexandre P. Francisco <[e-mail]>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/*
 * This is an implementation of the well known disjoint-set data structure
 * and associated union-find operations.
 */

#include <assert.h>
#include <limits.h>
#include <stdlib.h>

#include "unfnd.h"

struct _disjoint_set {
	int	sz;
	struct { int pi, rank; }	my[1];
};

/*
 * Initialize the data structure with capacity to 'sz' elements.
 */
disjoint_set
make_set(int sz)
{
	disjoint_set set;
	int i;

	if (sz == 0)
		return NULL;
	set = (disjoint_set) malloc(sizeof(int) + 2 * sizeof(int) * sz);
	if (set == NULL)
		return NULL;
	set->sz = sz;
	for (i = 0; i < sz; i++) {
		set->my[i].pi = i;
		set->my[i].rank = 0;
	}
	return set;
}

/*
 * Finds the root of the set to which 'i' belongs applying path compression
 * by halving.
 */
int
find_set(disjoint_set set, int i)
{
	if (set == NULL || i < 0 || i >= set->sz)
		return UINT_MAX;
	for (; i != set->my[i].pi; i = set->my[i].pi)
		set->my[i].pi = set->my[set->my[i].pi].pi;
	return i;
}

/*
 * Link the sets to which 'i' and 'j' belong with union by rank.
 */
int
same_set(disjoint_set set, int i, int j)
{
	int i_root, j_root;

	if (set == NULL || i < 0 || j < 0 || i >= set->sz || j >= set->sz)
		return 0;
	i_root = find_set(set, i);
	j_root = find_set(set, j);
	if (i_root == j_root)
		return 1;
	return 0;
}

/*
 * Link the sets to which 'i' and 'j' belong with union by rank.
 */
void
union_set(disjoint_set set, int i, int j)
{
	int i_root, j_root;

	if (set == NULL || i < 0 || j < 0 || i >= set->sz || j >= set->sz)
		return;
	i_root = find_set(set, i);
	j_root = find_set(set, j);
	if (i_root == j_root)
		return;
	if (set->my[i_root].rank > set->my[j_root].rank)
		set->my[j_root].pi = i_root;
	else if (set->my[i_root].rank < set->my[j_root].rank)
		set->my[i_root].pi = j_root;
	else { /* set->my[i_root].rank == set->my[j_root].rank */ 
		set->my[i_root].pi = j_root;
		set->my[j_root].rank ++;
	}
}