cfind.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.
 */

#define _POSIX_C_SOURCE 2

#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include <assert.h>

#include "gcfnd.h"

void	usage();

int
main(int argc, char *argv[])
{
	int opt, nv, ne, *cid, cnb, i;
	edge *e_lst;
	double Q;

	while((opt = getopt(argc, argv, "h")) != -1){
		switch(opt){
		default: /* '?' */
			usage();
			exit(EXIT_FAILURE);
		}
	}

	scanf("%d %d", &nv, &ne);
	e_lst = (edge *) malloc(sizeof(edge)*ne);
	for (i = 0; i < ne; i++)
		scanf("%d %d", &(e_lst[i].u), &(e_lst[i].v));
	cid = (int *) malloc(sizeof(int)*nv);

	gcfnd(nv, e_lst, ne, cid, &cnb, &Q);

	printf("|C| = %d, max Q = %g\n", cnb, Q);

	free(e_lst);
	free(cid);

	return EXIT_SUCCESS;
}

void
usage()
{
	fprintf(stderr, "Usage: cfind < input\n");
}