diff options
Diffstat (limited to 'src/cnm')
| -rw-r--r-- | src/cnm/Makefile.am | 7 | ||||
| -rw-r--r-- | src/cnm/Makefile.in | 591 | ||||
| -rw-r--r-- | src/cnm/bst_pq.c | 808 | ||||
| -rw-r--r-- | src/cnm/bst_pq.h | 159 | ||||
| -rw-r--r-- | src/cnm/cnm.c | 480 | ||||
| -rw-r--r-- | src/cnm/cnm_bst_pq.c | 155 | ||||
| -rw-r--r-- | src/cnm/cnm_bst_pq.h | 105 |
7 files changed, 2305 insertions, 0 deletions
diff --git a/src/cnm/Makefile.am b/src/cnm/Makefile.am new file mode 100644 index 0000000..b036fac --- /dev/null +++ b/src/cnm/Makefile.am @@ -0,0 +1,7 @@ +include ../common.mk +bin_PROGRAMS = cnm +cnm_SOURCES = cnm.c bst_pq.c cnm_bst_pq.c bst_pq.h cnm_bst_pq.h \ +../utils/utils.c ../utils/gen_stack.c ../utils/dset.c \ +../include/utils.h ../include/gen_stack.h ../include/dset.h +cnm_LDADD = -lm + diff --git a/src/cnm/Makefile.in b/src/cnm/Makefile.in new file mode 100644 index 0000000..74cd719 --- /dev/null +++ b/src/cnm/Makefile.in @@ -0,0 +1,591 @@ +# Makefile.in generated by automake 1.15 from Makefile.am. +# @configure_input@ + +# Copyright (C) 1994-2014 Free Software Foundation, Inc. + +# This Makefile.in is free software; the Free Software Foundation +# gives unlimited permission to copy and/or distribute it, +# with or without modifications, as long as this notice is preserved. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY, to the extent permitted by law; without +# even the implied warranty of MERCHANTABILITY or FITNESS FOR A +# PARTICULAR PURPOSE. + +@SET_MAKE@ + +VPATH = @srcdir@ +am__is_gnu_make = { \ + if test -z '$(MAKELEVEL)'; then \ + false; \ + elif test -n '$(MAKE_HOST)'; then \ + true; \ + elif test -n '$(MAKE_VERSION)' && test -n '$(CURDIR)'; then \ + true; \ + else \ + false; \ + fi; \ +} +am__make_running_with_option = \ + case $${target_option-} in \ + ?) ;; \ + *) echo "am__make_running_with_option: internal error: invalid" \ + "target option '$${target_option-}' specified" >&2; \ + exit 1;; \ + esac; \ + has_opt=no; \ + sane_makeflags=$$MAKEFLAGS; \ + if $(am__is_gnu_make); then \ + sane_makeflags=$$MFLAGS; \ + else \ + case $$MAKEFLAGS in \ + *\\[\ \ ]*) \ + bs=\\; \ + sane_makeflags=`printf '%s\n' "$$MAKEFLAGS" \ + | sed "s/$$bs$$bs[$$bs $$bs ]*//g"`;; \ + esac; \ + fi; \ + skip_next=no; \ + strip_trailopt () \ + { \ + flg=`printf '%s\n' "$$flg" | sed "s/$$1.*$$//"`; \ + }; \ + for flg in $$sane_makeflags; do \ + test $$skip_next = yes && { skip_next=no; continue; }; \ + case $$flg in \ + *=*|--*) continue;; \ + -*I) strip_trailopt 'I'; skip_next=yes;; \ + -*I?*) strip_trailopt 'I';; \ + -*O) strip_trailopt 'O'; skip_next=yes;; \ + -*O?*) strip_trailopt 'O';; \ + -*l) strip_trailopt 'l'; skip_next=yes;; \ + -*l?*) strip_trailopt 'l';; \ + -[dEDm]) skip_next=yes;; \ + -[JT]) skip_next=yes;; \ + esac; \ + case $$flg in \ + *$$target_option*) has_opt=yes; break;; \ + esac; \ + done; \ + test $$has_opt = yes +am__make_dryrun = (target_option=n; $(am__make_running_with_option)) +am__make_keepgoing = (target_option=k; $(am__make_running_with_option)) +pkgdatadir = $(datadir)/@PACKAGE@ +pkgincludedir = $(includedir)/@PACKAGE@ +pkglibdir = $(libdir)/@PACKAGE@ +pkglibexecdir = $(libexecdir)/@PACKAGE@ +am__cd = CDPATH="$${ZSH_VERSION+.}$(PATH_SEPARATOR)" && cd +install_sh_DATA = $(install_sh) -c -m 644 +install_sh_PROGRAM = $(install_sh) -c +install_sh_SCRIPT = $(install_sh) -c +INSTALL_HEADER = $(INSTALL_DATA) +transform = $(program_transform_name) +NORMAL_INSTALL = : +PRE_INSTALL = : +POST_INSTALL = : +NORMAL_UNINSTALL = : +PRE_UNINSTALL = : +POST_UNINSTALL = : +bin_PROGRAMS = cnm$(EXEEXT) +subdir = src/cnm +ACLOCAL_M4 = $(top_srcdir)/aclocal.m4 +am__aclocal_m4_deps = $(top_srcdir)/configure.ac +am__configure_deps = $(am__aclocal_m4_deps) $(CONFIGURE_DEPENDENCIES) \ + $(ACLOCAL_M4) +DIST_COMMON = $(srcdir)/Makefile.am $(am__DIST_COMMON) +mkinstalldirs = $(install_sh) -d +CONFIG_HEADER = $(top_builddir)/config.h +CONFIG_CLEAN_FILES = +CONFIG_CLEAN_VPATH_FILES = +am__installdirs = "$(DESTDIR)$(bindir)" +PROGRAMS = $(bin_PROGRAMS) +am__dirstamp = $(am__leading_dot)dirstamp +am_cnm_OBJECTS = cnm.$(OBJEXT) bst_pq.$(OBJEXT) cnm_bst_pq.$(OBJEXT) \ + ../utils/utils.$(OBJEXT) ../utils/gen_stack.$(OBJEXT) \ + ../utils/dset.$(OBJEXT) +cnm_OBJECTS = $(am_cnm_OBJECTS) +cnm_DEPENDENCIES = +AM_V_P = $(am__v_P_@AM_V@) +am__v_P_ = $(am__v_P_@AM_DEFAULT_V@) +am__v_P_0 = false +am__v_P_1 = : +AM_V_GEN = $(am__v_GEN_@AM_V@) +am__v_GEN_ = $(am__v_GEN_@AM_DEFAULT_V@) +am__v_GEN_0 = @echo " GEN " $@; +am__v_GEN_1 = +AM_V_at = $(am__v_at_@AM_V@) +am__v_at_ = $(am__v_at_@AM_DEFAULT_V@) +am__v_at_0 = @ +am__v_at_1 = +DEFAULT_INCLUDES = -I.@am__isrc@ -I$(top_builddir) +depcomp = $(SHELL) $(top_srcdir)/depcomp +am__depfiles_maybe = depfiles +am__mv = mv -f +COMPILE = $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) \ + $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) +AM_V_CC = $(am__v_CC_@AM_V@) +am__v_CC_ = $(am__v_CC_@AM_DEFAULT_V@) +am__v_CC_0 = @echo " CC " $@; +am__v_CC_1 = +CCLD = $(CC) +LINK = $(CCLD) $(AM_CFLAGS) $(CFLAGS) $(AM_LDFLAGS) $(LDFLAGS) -o $@ +AM_V_CCLD = $(am__v_CCLD_@AM_V@) +am__v_CCLD_ = $(am__v_CCLD_@AM_DEFAULT_V@) +am__v_CCLD_0 = @echo " CCLD " $@; +am__v_CCLD_1 = +SOURCES = $(cnm_SOURCES) +DIST_SOURCES = $(cnm_SOURCES) +am__can_run_installinfo = \ + case $$AM_UPDATE_INFO_DIR in \ + n|no|NO) false;; \ + *) (install-info --version) >/dev/null 2>&1;; \ + esac +am__tagged_files = $(HEADERS) $(SOURCES) $(TAGS_FILES) $(LISP) +# Read a list of newline-separated strings from the standard input, +# and print each of them once, without duplicates. Input order is +# *not* preserved. +am__uniquify_input = $(AWK) '\ + BEGIN { nonempty = 0; } \ + { items[$$0] = 1; nonempty = 1; } \ + END { if (nonempty) { for (i in items) print i; }; } \ +' +# Make sure the list of sources is unique. This is necessary because, +# e.g., the same source file might be shared among _SOURCES variables +# for different programs/libraries. +am__define_uniq_tagged_files = \ + list='$(am__tagged_files)'; \ + unique=`for i in $$list; do \ + if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \ + done | $(am__uniquify_input)` +ETAGS = etags +CTAGS = ctags +am__DIST_COMMON = $(srcdir)/../common.mk $(srcdir)/Makefile.in \ + $(top_srcdir)/depcomp +DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST) +ACLOCAL = @ACLOCAL@ +AMTAR = @AMTAR@ +AM_DEFAULT_VERBOSITY = @AM_DEFAULT_VERBOSITY@ +AUTOCONF = @AUTOCONF@ +AUTOHEADER = @AUTOHEADER@ +AUTOMAKE = @AUTOMAKE@ +AWK = @AWK@ +CC = @CC@ +CCDEPMODE = @CCDEPMODE@ +CFLAGS = @CFLAGS@ +CPPFLAGS = @CPPFLAGS@ +CYGPATH_W = @CYGPATH_W@ +DEFS = @DEFS@ +DEPDIR = @DEPDIR@ +ECHO_C = @ECHO_C@ +ECHO_N = @ECHO_N@ +ECHO_T = @ECHO_T@ +EXEEXT = @EXEEXT@ +INSTALL = @INSTALL@ +INSTALL_DATA = @INSTALL_DATA@ +INSTALL_PROGRAM = @INSTALL_PROGRAM@ +INSTALL_SCRIPT = @INSTALL_SCRIPT@ +INSTALL_STRIP_PROGRAM = @INSTALL_STRIP_PROGRAM@ +LDFLAGS = @LDFLAGS@ +LIBOBJS = @LIBOBJS@ +LIBS = @LIBS@ +LTLIBOBJS = @LTLIBOBJS@ +MAKEINFO = @MAKEINFO@ +MKDIR_P = @MKDIR_P@ +OBJEXT = @OBJEXT@ +PACKAGE = @PACKAGE@ +PACKAGE_BUGREPORT = @PACKAGE_BUGREPORT@ +PACKAGE_NAME = @PACKAGE_NAME@ +PACKAGE_STRING = @PACKAGE_STRING@ +PACKAGE_TARNAME = @PACKAGE_TARNAME@ +PACKAGE_URL = @PACKAGE_URL@ +PACKAGE_VERSION = @PACKAGE_VERSION@ +PATH_SEPARATOR = @PATH_SEPARATOR@ +RONN = @RONN@ +SET_MAKE = @SET_MAKE@ +SHELL = @SHELL@ +STRIP = @STRIP@ +VERSION = @VERSION@ +abs_builddir = @abs_builddir@ +abs_srcdir = @abs_srcdir@ +abs_top_builddir = @abs_top_builddir@ +abs_top_srcdir = @abs_top_srcdir@ +ac_ct_CC = @ac_ct_CC@ +am__include = @am__include@ +am__leading_dot = @am__leading_dot@ +am__quote = @am__quote@ +am__tar = @am__tar@ +am__untar = @am__untar@ +bindir = @bindir@ +build_alias = @build_alias@ +builddir = @builddir@ +datadir = @datadir@ +datarootdir = @datarootdir@ +docdir = @docdir@ +dvidir = @dvidir@ +exec_prefix = @exec_prefix@ +host_alias = @host_alias@ +htmldir = @htmldir@ +includedir = @includedir@ +infodir = @infodir@ +install_sh = @install_sh@ +libdir = @libdir@ +libexecdir = @libexecdir@ +localedir = @localedir@ +localstatedir = @localstatedir@ +mandir = @mandir@ +mkdir_p = @mkdir_p@ +oldincludedir = @oldincludedir@ +pdfdir = @pdfdir@ +prefix = @prefix@ +program_transform_name = @program_transform_name@ +psdir = @psdir@ +runstatedir = @runstatedir@ +sbindir = @sbindir@ +sharedstatedir = @sharedstatedir@ +srcdir = @srcdir@ +sysconfdir = @sysconfdir@ +target_alias = @target_alias@ +top_build_prefix = @top_build_prefix@ +top_builddir = @top_builddir@ +top_srcdir = @top_srcdir@ +AM_CFLAGS = -I../include -O2 -std=c99 -Wall +cnm_SOURCES = cnm.c bst_pq.c cnm_bst_pq.c bst_pq.h cnm_bst_pq.h \ +../utils/utils.c ../utils/gen_stack.c ../utils/dset.c \ +../include/utils.h ../include/gen_stack.h ../include/dset.h + +cnm_LDADD = -lm +all: all-am + +.SUFFIXES: +.SUFFIXES: .c .o .obj +$(srcdir)/Makefile.in: $(srcdir)/Makefile.am $(srcdir)/../common.mk $(am__configure_deps) + @for dep in $?; do \ + case '$(am__configure_deps)' in \ + *$$dep*) \ + ( cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh ) \ + && { if test -f $@; then exit 0; else break; fi; }; \ + exit 1;; \ + esac; \ + done; \ + echo ' cd $(top_srcdir) && $(AUTOMAKE) --foreign src/cnm/Makefile'; \ + $(am__cd) $(top_srcdir) && \ + $(AUTOMAKE) --foreign src/cnm/Makefile +Makefile: $(srcdir)/Makefile.in $(top_builddir)/config.status + @case '$?' in \ + *config.status*) \ + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh;; \ + *) \ + echo ' cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe)'; \ + cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe);; \ + esac; +$(srcdir)/../common.mk $(am__empty): + +$(top_builddir)/config.status: $(top_srcdir)/configure $(CONFIG_STATUS_DEPENDENCIES) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh + +$(top_srcdir)/configure: $(am__configure_deps) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh +$(ACLOCAL_M4): $(am__aclocal_m4_deps) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh +$(am__aclocal_m4_deps): +install-binPROGRAMS: $(bin_PROGRAMS) + @$(NORMAL_INSTALL) + @list='$(bin_PROGRAMS)'; test -n "$(bindir)" || list=; \ + if test -n "$$list"; then \ + echo " $(MKDIR_P) '$(DESTDIR)$(bindir)'"; \ + $(MKDIR_P) "$(DESTDIR)$(bindir)" || exit 1; \ + fi; \ + for p in $$list; do echo "$$p $$p"; done | \ + sed 's/$(EXEEXT)$$//' | \ + while read p p1; do if test -f $$p \ + ; then echo "$$p"; echo "$$p"; else :; fi; \ + done | \ + sed -e 'p;s,.*/,,;n;h' \ + -e 's|.*|.|' \ + -e 'p;x;s,.*/,,;s/$(EXEEXT)$$//;$(transform);s/$$/$(EXEEXT)/' | \ + sed 'N;N;N;s,\n, ,g' | \ + $(AWK) 'BEGIN { files["."] = ""; dirs["."] = 1 } \ + { d=$$3; if (dirs[d] != 1) { print "d", d; dirs[d] = 1 } \ + if ($$2 == $$4) files[d] = files[d] " " $$1; \ + else { print "f", $$3 "/" $$4, $$1; } } \ + END { for (d in files) print "f", d, files[d] }' | \ + while read type dir files; do \ + if test "$$dir" = .; then dir=; else dir=/$$dir; fi; \ + test -z "$$files" || { \ + echo " $(INSTALL_PROGRAM_ENV) $(INSTALL_PROGRAM) $$files '$(DESTDIR)$(bindir)$$dir'"; \ + $(INSTALL_PROGRAM_ENV) $(INSTALL_PROGRAM) $$files "$(DESTDIR)$(bindir)$$dir" || exit $$?; \ + } \ + ; done + +uninstall-binPROGRAMS: + @$(NORMAL_UNINSTALL) + @list='$(bin_PROGRAMS)'; test -n "$(bindir)" || list=; \ + files=`for p in $$list; do echo "$$p"; done | \ + sed -e 'h;s,^.*/,,;s/$(EXEEXT)$$//;$(transform)' \ + -e 's/$$/$(EXEEXT)/' \ + `; \ + test -n "$$list" || exit 0; \ + echo " ( cd '$(DESTDIR)$(bindir)' && rm -f" $$files ")"; \ + cd "$(DESTDIR)$(bindir)" && rm -f $$files + +clean-binPROGRAMS: + -test -z "$(bin_PROGRAMS)" || rm -f $(bin_PROGRAMS) +../utils/$(am__dirstamp): + @$(MKDIR_P) ../utils + @: > ../utils/$(am__dirstamp) +../utils/$(DEPDIR)/$(am__dirstamp): + @$(MKDIR_P) ../utils/$(DEPDIR) + @: > ../utils/$(DEPDIR)/$(am__dirstamp) +../utils/utils.$(OBJEXT): ../utils/$(am__dirstamp) \ + ../utils/$(DEPDIR)/$(am__dirstamp) +../utils/gen_stack.$(OBJEXT): ../utils/$(am__dirstamp) \ + ../utils/$(DEPDIR)/$(am__dirstamp) +../utils/dset.$(OBJEXT): ../utils/$(am__dirstamp) \ + ../utils/$(DEPDIR)/$(am__dirstamp) + +cnm$(EXEEXT): $(cnm_OBJECTS) $(cnm_DEPENDENCIES) $(EXTRA_cnm_DEPENDENCIES) + @rm -f cnm$(EXEEXT) + $(AM_V_CCLD)$(LINK) $(cnm_OBJECTS) $(cnm_LDADD) $(LIBS) + +mostlyclean-compile: + -rm -f *.$(OBJEXT) + -rm -f ../utils/*.$(OBJEXT) + +distclean-compile: + -rm -f *.tab.c + +@AMDEP_TRUE@@am__include@ @am__quote@../utils/$(DEPDIR)/dset.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@../utils/$(DEPDIR)/gen_stack.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@../utils/$(DEPDIR)/utils.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/bst_pq.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/cnm.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/cnm_bst_pq.Po@am__quote@ + +.c.o: +@am__fastdepCC_TRUE@ $(AM_V_CC)depbase=`echo $@ | sed 's|[^/]*$$|$(DEPDIR)/&|;s|\.o$$||'`;\ +@am__fastdepCC_TRUE@ $(COMPILE) -MT $@ -MD -MP -MF $$depbase.Tpo -c -o $@ $< &&\ +@am__fastdepCC_TRUE@ $(am__mv) $$depbase.Tpo $$depbase.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ $(AM_V_CC)source='$<' object='$@' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(AM_V_CC@am__nodep@)$(COMPILE) -c -o $@ $< + +.c.obj: +@am__fastdepCC_TRUE@ $(AM_V_CC)depbase=`echo $@ | sed 's|[^/]*$$|$(DEPDIR)/&|;s|\.obj$$||'`;\ +@am__fastdepCC_TRUE@ $(COMPILE) -MT $@ -MD -MP -MF $$depbase.Tpo -c -o $@ `$(CYGPATH_W) '$<'` &&\ +@am__fastdepCC_TRUE@ $(am__mv) $$depbase.Tpo $$depbase.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ $(AM_V_CC)source='$<' object='$@' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(AM_V_CC@am__nodep@)$(COMPILE) -c -o $@ `$(CYGPATH_W) '$<'` + +ID: $(am__tagged_files) + $(am__define_uniq_tagged_files); mkid -fID $$unique +tags: tags-am +TAGS: tags + +tags-am: $(TAGS_DEPENDENCIES) $(am__tagged_files) + set x; \ + here=`pwd`; \ + $(am__define_uniq_tagged_files); \ + shift; \ + if test -z "$(ETAGS_ARGS)$$*$$unique"; then :; else \ + test -n "$$unique" || unique=$$empty_fix; \ + if test $$# -gt 0; then \ + $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \ + "$$@" $$unique; \ + else \ + $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \ + $$unique; \ + fi; \ + fi +ctags: ctags-am + +CTAGS: ctags +ctags-am: $(TAGS_DEPENDENCIES) $(am__tagged_files) + $(am__define_uniq_tagged_files); \ + test -z "$(CTAGS_ARGS)$$unique" \ + || $(CTAGS) $(CTAGSFLAGS) $(AM_CTAGSFLAGS) $(CTAGS_ARGS) \ + $$unique + +GTAGS: + here=`$(am__cd) $(top_builddir) && pwd` \ + && $(am__cd) $(top_srcdir) \ + && gtags -i $(GTAGS_ARGS) "$$here" +cscopelist: cscopelist-am + +cscopelist-am: $(am__tagged_files) + list='$(am__tagged_files)'; \ + case "$(srcdir)" in \ + [\\/]* | ?:[\\/]*) sdir="$(srcdir)" ;; \ + *) sdir=$(subdir)/$(srcdir) ;; \ + esac; \ + for i in $$list; do \ + if test -f "$$i"; then \ + echo "$(subdir)/$$i"; \ + else \ + echo "$$sdir/$$i"; \ + fi; \ + done >> $(top_builddir)/cscope.files + +distclean-tags: + -rm -f TAGS ID GTAGS GRTAGS GSYMS GPATH tags + +distdir: $(DISTFILES) + @srcdirstrip=`echo "$(srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \ + topsrcdirstrip=`echo "$(top_srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \ + list='$(DISTFILES)'; \ + dist_files=`for file in $$list; do echo $$file; done | \ + sed -e "s|^$$srcdirstrip/||;t" \ + -e "s|^$$topsrcdirstrip/|$(top_builddir)/|;t"`; \ + case $$dist_files in \ + */*) $(MKDIR_P) `echo "$$dist_files" | \ + sed '/\//!d;s|^|$(distdir)/|;s,/[^/]*$$,,' | \ + sort -u` ;; \ + esac; \ + for file in $$dist_files; do \ + if test -f $$file || test -d $$file; then d=.; else d=$(srcdir); fi; \ + if test -d $$d/$$file; then \ + dir=`echo "/$$file" | sed -e 's,/[^/]*$$,,'`; \ + if test -d "$(distdir)/$$file"; then \ + find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \ + fi; \ + if test -d $(srcdir)/$$file && test $$d != $(srcdir); then \ + cp -fpR $(srcdir)/$$file "$(distdir)$$dir" || exit 1; \ + find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \ + fi; \ + cp -fpR $$d/$$file "$(distdir)$$dir" || exit 1; \ + else \ + test -f "$(distdir)/$$file" \ + || cp -p $$d/$$file "$(distdir)/$$file" \ + || exit 1; \ + fi; \ + done +check-am: all-am +check: check-am +all-am: Makefile $(PROGRAMS) +installdirs: + for dir in "$(DESTDIR)$(bindir)"; do \ + test -z "$$dir" || $(MKDIR_P) "$$dir"; \ + done +install: install-am +install-exec: install-exec-am +install-data: install-data-am +uninstall: uninstall-am + +install-am: all-am + @$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am + +installcheck: installcheck-am +install-strip: + if test -z '$(STRIP)'; then \ + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \ + install; \ + else \ + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \ + "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'" install; \ + fi +mostlyclean-generic: + +clean-generic: + +distclean-generic: + -test -z "$(CONFIG_CLEAN_FILES)" || rm -f $(CONFIG_CLEAN_FILES) + -test . = "$(srcdir)" || test -z "$(CONFIG_CLEAN_VPATH_FILES)" || rm -f $(CONFIG_CLEAN_VPATH_FILES) + -rm -f ../utils/$(DEPDIR)/$(am__dirstamp) + -rm -f ../utils/$(am__dirstamp) + +maintainer-clean-generic: + @echo "This command is intended for maintainers to use" + @echo "it deletes files that may require special tools to rebuild." +clean: clean-am + +clean-am: clean-binPROGRAMS clean-generic mostlyclean-am + +distclean: distclean-am + -rm -rf ../utils/$(DEPDIR) ./$(DEPDIR) + -rm -f Makefile +distclean-am: clean-am distclean-compile distclean-generic \ + distclean-tags + +dvi: dvi-am + +dvi-am: + +html: html-am + +html-am: + +info: info-am + +info-am: + +install-data-am: + +install-dvi: install-dvi-am + +install-dvi-am: + +install-exec-am: install-binPROGRAMS + +install-html: install-html-am + +install-html-am: + +install-info: install-info-am + +install-info-am: + +install-man: + +install-pdf: install-pdf-am + +install-pdf-am: + +install-ps: install-ps-am + +install-ps-am: + +installcheck-am: + +maintainer-clean: maintainer-clean-am + -rm -rf ../utils/$(DEPDIR) ./$(DEPDIR) + -rm -f Makefile +maintainer-clean-am: distclean-am maintainer-clean-generic + +mostlyclean: mostlyclean-am + +mostlyclean-am: mostlyclean-compile mostlyclean-generic + +pdf: pdf-am + +pdf-am: + +ps: ps-am + +ps-am: + +uninstall-am: uninstall-binPROGRAMS + +.MAKE: install-am install-strip + +.PHONY: CTAGS GTAGS TAGS all all-am check check-am clean \ + clean-binPROGRAMS clean-generic cscopelist-am ctags ctags-am \ + distclean distclean-compile distclean-generic distclean-tags \ + distdir dvi dvi-am html html-am info info-am install \ + install-am install-binPROGRAMS install-data install-data-am \ + install-dvi install-dvi-am install-exec install-exec-am \ + install-html install-html-am install-info install-info-am \ + install-man install-pdf install-pdf-am install-ps \ + install-ps-am install-strip installcheck installcheck-am \ + installdirs maintainer-clean maintainer-clean-generic \ + mostlyclean mostlyclean-compile mostlyclean-generic pdf pdf-am \ + ps ps-am tags tags-am uninstall uninstall-am \ + uninstall-binPROGRAMS + +.PRECIOUS: Makefile + + +# Tell versions [3.59,3.63) of GNU make to not export all variables. +# Otherwise a system limit (for SysV at least) may be exceeded. +.NOEXPORT: diff --git a/src/cnm/bst_pq.c b/src/cnm/bst_pq.c new file mode 100644 index 0000000..9502f4e --- /dev/null +++ b/src/cnm/bst_pq.c @@ -0,0 +1,808 @@ +/** + * 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 3 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, see + * <http://www.gnu.org/licenses/>. + * + * (c) Vincenzo Nicosia 2009-2017 -- <v.nicosia@qmul.ac.uk> + * + * This file is part of NetBunch, a package for complex network + * analysis and modelling. For more information please visit: + * + * http://www.complex-networks.net/ + * + * If you use this software, please add a reference to + * + * V. Latora, V. Nicosia, G. Russo + * "Complex Networks: Principles, Methods and Applications" + * Cambridge University Press (2017) + * ISBN: 9781107103184 + * + *********************************************************************** + * + * This is an implementation of a Binary Search Tree augmented by a + * Priority Queue. This data structure is central to the + * implementation of the Clauset-Newman-Moore greedy modularity + * optimisation algorithm + * + */ + +#include <stdlib.h> +#include <stdio.h> +#include <math.h> +#include <assert.h> + +#include "utils.h" +#include "bst_pq.h" + + + +/* BST-related functions */ + + +void __recursive_preorder(node_t *cur, ilfunc_t *funs){ + + if(cur->left){ + __recursive_preorder(cur->left, funs); + } + if(cur -> active) + funs->print(cur->info, funs->fileout); + if(cur->right){ + __recursive_preorder(cur->right, funs); + } +} + +/* + * + * Recursive push of nodes in the nodecache :-) + * + */ + +void __recursive_destroy(node_t *cur, ilfunc_t *funs){ + if(cur->left){ + __recursive_destroy(cur->left, funs); + cur->left = NULL; + } + if(cur->right){ + __recursive_destroy(cur->right, funs); + cur->right = NULL; + } +} + + +int __recursive_insert(node_t *cur, node_t *elem, ilfunc_t *f){ + + int res ; + res = f->compare(cur->info, elem->info); + /* printf("res: %d\n", res); */ + assert(res != 0); + if ( res > 0){ + if (cur->left){ + return __recursive_insert(cur->left, elem, f); + } + else{ + cur->left = elem; + elem->parent = cur; + return 0; + } + } + else if (res < 0){ + if (cur->right){ + return __recursive_insert(cur->right, elem, f); + } + else{ + cur->right = elem; + elem->parent = cur; + return 0; + } + } + if (cur -> active){ + printf("warning!!!!! duplicate entry!!!!!!\n\n"); + exit(1); + } + else + cur->active = 1; + return -1; +} + + + +void* __recursive_lookup(node_t *cur, int v, ilfunc_t *f){ + + int res; + + res = f->compare(cur->info, v); + + if (res > 0){ + if(cur->left) + return __recursive_lookup(cur->left, v, f); + else + return NULL; + + } + else if (res < 0){ + if(cur->right) + return __recursive_lookup(cur->right, v, f); + else + return NULL; + } + else{ /* res == 0, we found the element we were looking for */ + return cur; + } +} + + + +node_t* __recursive_getmin(node_t *cur){ + + if(cur->left){ + return __recursive_getmin(cur->left); + } + else{ + return cur; + } + +} + + +node_t* __tree_getmin(node_t *n){ + + if (!n){ + return NULL; + } + else{ + return __recursive_getmin(n); + } + +} + + +/* This is used by __tree__delete to put another tree v in place of + the current node u */ + + +void __tree_transplant(bst_pq_t t, node_t *u, node_t * v){ + + if (u->parent == NULL){ + t->root = v; + } + else if(u == u->parent->left){ + u->parent->left = v; + } + else{ + u->parent->right = v; + } + if (v != NULL){ + v->parent = u->parent; + } + +} + + +void __tree_delete(bst_pq_t t, node_t *z){ + + node_t *y; + + if (z == NULL) + return; + + if (z->left == NULL){ + __tree_transplant(t, z, z->right); + } + else if(z->right == NULL){ + __tree_transplant(t, z, z->left); + } + else{ + y = __tree_getmin(z->right); + if (y->parent != z){ + __tree_transplant(t, y, y->right); + y->right = z->right; + y->right->parent = y; + } + __tree_transplant(t, z, y); + y->left = z->left; + y->left->parent = y; + } +} + + + + +void bst_pq_tree_destroy(bst_pq_t t){ + + if(t->root) + __recursive_destroy(t->root, & (t->bst_funs)); + free(t); +} + + + + +void __bst_pq_tree_view_pre(bst_pq_t t){ + + if (t->root){ + printf("----\n"); + __recursive_preorder(t->root, & (t->bst_funs)); + printf("\n----\n"); + } + else + printf("----- Empty tree!!!! -----\n"); + +} + + + +void* __bst_pq_tree_lookup(bst_pq_t t , int elem){ + + if(t->root) + return __recursive_lookup(t->root, elem, & (t->bst_funs) ); + else + return NULL; +} + + + + + +/* void bst_pq_tree_map(bst_pq_t t, void (*func)(void*)){ */ + +/* __recursive_map(t->root, func); */ + +/* } */ + + +/* void bst_pq_tree_map_args(bst_pq_t t, void (*func)(void*, void*), void *args){ */ + +/* __recursive_map_args(t->root, func, args); */ + +/* } */ + +void* bst_pq_tree_get_fileout(bst_pq_t t){ + + return t->bst_funs.fileout; +} + +void bst_pq_tree_set_fileout(bst_pq_t t, void *f){ + + t->bst_funs.fileout = f; +} + + + +node_t* __recursive_getmax(node_t *cur){ + + if(cur->right){ + return __recursive_getmax(cur->right); + } + else{ + return cur; + } + +} + + +void* bst_pq_tree_getmax(bst_pq_t t){ + + if (!t){ + return NULL; + } + else{ + return __recursive_getmax(t->root); + } + +} + + +/************************ + * PQ-related functions * + ************************/ + +void __update_handle(bst_pq_t q, int idx){ + + node_t *n; + n = (node_t*) q->v[idx]; + n->index = idx; + //q->handles[q->pq_funs.get_id(q->v[idx])] = idx; +} + + + +void __bst_pq_queue_sift_up(bst_pq_t q, int i){ + + int idx, parent; + void *tmp; + + if ( q->last < 0) + return; /* no sifting if the PQ is empty!!! */ + + idx = i; + parent = PARENT(idx); + + switch(q->qtype){ + case MAX_QUEUE: + while ( idx >0 && q->pq_funs.compare(q->v[idx]->key, q->v[parent]->key) > 0){ + tmp = q->v[idx]; + q->v[idx] = q->v[parent]; + q->v[parent] = tmp; + __update_handle(q, idx); + __update_handle(q, parent); + idx = parent; + parent = PARENT(idx); + } + break; + case MIN_QUEUE: + while ( idx >0 && q-> pq_funs.compare(q->v[idx]->key, q->v[parent]->key) < 0){ + tmp = q->v[idx]; + q->v[idx] = q->v[parent]; + q->v[parent] = tmp; + __update_handle(q, idx); + __update_handle(q, parent); + idx = parent; + parent = PARENT(idx); + } + break; + } +} + + +void __bst_pq_queue_sift_down(bst_pq_t q, int i){ + + int left, right, largest, smallest; + void *tmp; + + if ( q->last < 0) + return; /* no sifting if the PQ is empty!!! */ + if( i > q->last) + return; /* no sifting if the index i is beyond the end of the PQ */ + + switch(q->qtype){ + case MAX_QUEUE: + largest = i; + left = 2 * i + 1; + right = 2 * i + 2; + + if (left <= q->last && q->pq_funs.compare(q->v[left]->key, q->v[largest]->key) > 0){ + largest = left; + } + if (right <= q->last && q->pq_funs.compare(q->v[right]->key, q->v[largest]->key) > 0){ + largest = right; + } + if (largest != i){ + tmp = q->v[i]; + q->v[i] = q->v[largest]; + q->v[largest] = tmp; + __update_handle(q, i); + __update_handle(q, largest); + __bst_pq_queue_sift_down(q, largest); + } + else{ + __update_handle(q, i); + } + break; + + case MIN_QUEUE: + smallest = i; + left = 2 * i + 1; + right = 2 * i + 2; + + if (left <= q->last && q->pq_funs.compare(q->v[left]->key, q->v[smallest]->key) < 0){ + smallest = left; + } + if (right <= q->last && q->pq_funs.compare(q->v[right]->key, q->v[smallest]->key) < 0){ + smallest = right; + } + if (smallest != i){ + tmp = q->v[i]; + q->v[i] = q->v[smallest]; + q->v[smallest] = tmp; + __update_handle(q, i); + __update_handle(q, smallest); + __bst_pq_queue_sift_down(q, smallest); + } + else{ + __update_handle(q, i); + } + break; + } +} + + +void __bst_pq_queue_insert(bst_pq_t q, void *elem){ + + //void *tmp; + + if (q->last == q->N-1){ + /* reallocate the array to arrange a few new elements */ + q->N += 10; + q->v = realloc(q->v, (q->N) * sizeof(void*)); + VALID_PTR_OR_EXIT(q->v, 17); + //q->v = tmp; + } + + q->last += 1; + q->v[q->last] = elem; + __update_handle(q, q->last); + __bst_pq_queue_sift_up(q, q->last); + +} + + + +int __bst_pq_queue_delete_index(bst_pq_t q, int index){ + + if (q->last >=0 && index <= q->last){ + //*val = q->v[0]; + q->v[index] = q->v[q->last]; + q->last -= 1; + __bst_pq_queue_sift_down(q, index); + return 0; + } + else{ + return 1; + } +} + + + +void* __bst_pq_queue_peek(bst_pq_t q){ + + if (q->last >= 0) + return q->v[0]; + else + return NULL; +} + + + +int __bst_pq_queue_force_key(bst_pq_t q, unsigned int idx, double key){ + + switch(q->qtype){ + case MAX_QUEUE: + if (q->pq_funs.compare_to_key(q->v[idx], key) > 0){ + //q->pq_funs.set_key(q->v[idx], key); + q->v[idx]->key = key; + __bst_pq_queue_sift_down(q, idx); + } + else{ + //q->pq_funs.set_key(q->v[idx], key); + q->v[idx]->key = key; + __bst_pq_queue_sift_up(q, idx); + } + break; + case MIN_QUEUE: + if (q->pq_funs.compare_to_key(q->v[idx], key) < 0){ + //q->pq_funs.set_key(q->v[idx], key); + q->v[idx]->key = key; + __bst_pq_queue_sift_down(q, idx); + } + else{ + //q->pq_funs.set_key(q->v[idx], key); + q->v[idx]->key = key; + __bst_pq_queue_sift_up(q, idx); + } + break; + } + return 0; +} + + + +void __bst_pq_queue_dump(bst_pq_t q){ + + int i; + + unsigned int N; + + N = q->last+1; + + printf("N: %d last:%d root:", q->N, q->last); + if (q->last >=0) + q->pq_funs.print_elem(q->v[0]); + else + printf("NULL"); + printf("\n"); + + for(i=0; i<N; i++){ + if (i < (N+1)/2){ + if (2*i+1 < N) + if (2*i + 2 < N){ + printf("%d: ", i); + q->pq_funs.print_elem(q->v[i]); + printf(" ("); + q->pq_funs.print_elem(q->v[2*i+1]); + printf(", "); + q->pq_funs.print_elem(q->v[2*i+2]); + printf(")\n"); + } + else{ + printf("%d: ", i); + q->pq_funs.print_elem(q->v[i]); + printf(" ("); + q->pq_funs.print_elem(q->v[2*i+1]); + printf(", NULL)\n"); + } + else{ + printf("%d: ", i); + q->pq_funs.print_elem(q->v[i]); + printf(" (NULL, NULL)\n"); + } + } + else{ + printf("%d: ", i); + q->pq_funs.print_elem(q->v[i]); + printf(" (NULL, NULL)\n"); + } + } + printf("\n"); +} + + + + +/* bst_pq interface */ + +/* init the BST_PQ -- TESTED --*/ + +bst_pq_t bst_pq_create(ilfunc_t *bst_funs, gen_pqueue_func_t *pq_funs, char qtype, + unsigned int N, gen_stack_t *node_cache){ + + bst_pq_t b; + + b = (bst_pq_t)malloc(sizeof(bst_pq_struct_t)); + b->root = NULL; + b->bst_funs = *bst_funs; + + b->bst_funs.fileout = stdout; + b->qtype = qtype; + b->N = N; + b->last = -1; + b->pq_funs = *pq_funs; + b->v = b->pq_funs.alloc_vector(N); + if (node_cache == NULL){ + b->node_cache = malloc(sizeof(gen_stack_t)); + gen_stack_create(b->node_cache); + } + else{ + b->node_cache = node_cache; + } + return b; +} + + + + + + + +/* insert a new element in the BST_PQ -- TESTED */ +void bst_pq_insert(bst_pq_t b, unsigned int elem_info, double elem_key){ + + /* insert the element in the tree first */ + node_t *n; + int err; + + n = __bst_pq_tree_lookup(b, elem_info); + + /* The following assert should fail ONLY if there is an auto-loop */ + assert(n == NULL); + + if (gen_stack_empty(b->node_cache)){ + n = (node_t*)malloc(sizeof(node_t)); + //n->info = b->bst_funs.alloc(); + //n->key = b->pq_funs.alloc_key(); + } + else{ + err = gen_stack_pop(b->node_cache, (void**) &n); + if (err){ + n = malloc(sizeof(node_t)); + //n->info = b->bst_funs.alloc(); + //n->key = b->pq_funs.alloc_key(); + } + } + //b->bst_funs.copy(elem_info, n->info); + n->info = elem_info; + n->left = n->right = NULL; + if (b->root == NULL){ + b->root = n; + n->parent = NULL; + } + else{ + err = __recursive_insert(b->root, n, & (b->bst_funs)); + if(err){ + fprintf(stderr, "Error during insert into BST!!! (%s: %d)\n", + __FILE__, __LINE__); + exit(23); + } + } + n->active = 1; + n->index = -1; + /* set the key as needed */ + //b->pq_funs.copy_key(elem_key, n->key); + n->key = elem_key; + + /* then, insert the pointer to the element in the PQ */ + __bst_pq_queue_insert(b, n); + +} + +/* delete (or deactivate) the element associated to a given info -- TESTED --*/ +int bst_pq_delete(bst_pq_t b, unsigned int info){ + + node_t *n; + + n = __bst_pq_tree_lookup(b, info); + + if (n != NULL){ + __tree_delete(b, n); + n->active = 0; /* deactivate the node */ + /* After the node has been deleted from the tree, we add it to + the node cache */ + gen_stack_push(b->node_cache, n); + __bst_pq_queue_delete_index(b, n->index); /* remove the reference form the PQ */ + return 0; /* No problem */ + } + return 1; /* the element does not exist */ +} + +/* change the key of an element in the BST_PQ -- TESTED --*/ +int bst_pq_change_key(bst_pq_t b, unsigned int info, double key){ + + node_t *n; + int idx; + + n = __bst_pq_tree_lookup(b, info); + if (n != NULL){ + /* the element exists. We should just force its key and sift as required */ + idx = n->index; + __bst_pq_queue_force_key(b, idx, key); + return 0; /* No problem */ + } + else{ + return 1; /* The element does not exist */ + } + +} + +/* return the head of the PQ -- TESTED --*/ +void* bst_pq_peek(bst_pq_t q){ + + return __bst_pq_queue_peek(q); +} + + +/* Read the key of a given node of the BST */ +double bst_pq_get_key(bst_pq_t b, unsigned int info){ + + node_t *n; + + n = __bst_pq_tree_lookup(b, info); + if (n != NULL){ + return n->key; + } + else{ + return -100000; + } +} + + +/* Read the key of the element of index "index" in the PQ */ +double bst_pq_get_key_from_index(bst_pq_t b, int index){ + + node_t *n; + + n = (node_t *)b->v[index]; + + return n->key; +} + + +/* Dump the BST -- TESTED -- */ +void bst_pq_dump_bst(bst_pq_t b){ + + __bst_pq_tree_view_pre(b); + +} + +/* Show the PQ -- TESTED -- */ +void bst_pq_dump_pq(bst_pq_t b){ + + __bst_pq_queue_dump(b); + +} + +/* Perform a lookup of an element in the BST_PQ -- TESTED-- */ +node_t* bst_pq_lookup(bst_pq_t b, unsigned int info){ + + return __bst_pq_tree_lookup(b, info); +} + + +node_t* bst_pq_lookup_active(bst_pq_t b, unsigned int info){ + + node_t *ptr; + + ptr = __bst_pq_tree_lookup(b, info); + + if(ptr) + assert(ptr->active != 0); + + if (ptr != NULL && ptr->active){ + return ptr; + } + + return NULL; +} + + +/* void bst_pq_insert_existing(bst_pq_t b, node_t *n){ */ + +/* /\* insert the element in the tree first *\/ */ +/* if (n == NULL){ */ +/* fprintf(stderr, "Error!!!! Attempt to insert a NULL existing element (%s: %d)\n", */ +/* __FILE__, __LINE__); */ +/* exit(37); */ +/* } */ +/* /\* n->info = b->bst_funs.alloc(); *\/ */ +/* /\* n->key = b->pq_funs.alloc_key(); *\/ */ +/* /\* b->bst_funs.copy(elem_info, n->info); *\/ */ +/* n->left = n->right = NULL; */ +/* if (b->root == NULL){ */ +/* b->root = n; */ +/* n->parent = NULL; */ +/* } */ +/* else{ */ +/* __recursive_insert(b->root, n, & (b->bst_funs)); */ +/* } */ + +/* n->active = 1; */ +/* /\* set the key as needed *\/ */ +/* //b->pq_funs.copy_key(elem_key, n->key); */ + +/* /\* then, insert the pointer to the element in the PQ *\/ */ +/* __bst_pq_queue_insert(b, n); */ + +/* } */ + + + + + + +void bst_pq_destroy(bst_pq_t b, char destroy_cache){ + + int i; + node_t *n; + + if (b == NULL) + return; + + if(destroy_cache && b->node_cache != NULL ){ + while(!gen_stack_pop(b->node_cache, (void**) &n)){ + //b->bst_funs.dealloc(n->info); + //free(n->key); + free(n); + } + free(b->node_cache->v); + free(b->node_cache); + } + + for(i=b->last; i>=0; i--){ + __tree_delete(b, b->v[i]); + __bst_pq_queue_delete_index(b, i); /* remove the reference form the PQ */ + //bst_pq_delete(b, b->v[i]->info); + //b->bst_funs.dealloc(b->v[i]->info); + //free(b->v[i]->key); + free(b->v[i]); + } + free(b->v); + free(b); +} diff --git a/src/cnm/bst_pq.h b/src/cnm/bst_pq.h new file mode 100644 index 0000000..892eef0 --- /dev/null +++ b/src/cnm/bst_pq.h @@ -0,0 +1,159 @@ +/** + * 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 3 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, see + * <http://www.gnu.org/licenses/>. + * + * (c) Vincenzo Nicosia 2009-2017 -- <v.nicosia@qmul.ac.uk> + * + * This file is part of NetBunch, a package for complex network + * analysis and modelling. For more information please visit: + * + * http://www.complex-networks.net/ + * + * If you use this software, please add a reference to + * + * V. Latora, V. Nicosia, G. Russo + * "Complex Networks: Principles, Methods and Applications" + * Cambridge University Press (2017) + * ISBN: 9781107103184 + * + *********************************************************************** + * + * This is an implementation of a Binary Search Tree augmented by a + * Priority Queue. This data structure is central to the + * implementation of the Clauset-Newman-Moore greedy modularity + * optimisation algorithm + * + */ + +#ifndef __BST_PQ_H__ +#define __BST_PQ_H__ + +#include "gen_stack.h" + + +/** + * + * This is an implementation of a Binary Search Tree augmented by a + * Priority Queue. + * + */ + +#define PARENT(i) (int)(floor((i-1)/2)) + +#define MIN_QUEUE 0x01 +#define MAX_QUEUE 0x02 + +typedef struct node{ + unsigned int info; /* This is the ID of the neighbour used in the BST */ + double key; /* This is the \DeltaQ values used as a key in the + PQ */ + struct node* left; /* left child of the current element in the BST */ + struct node* right; /* right child of the current element in the BST */ + int index; /* Index of the current node in the PQ */ + struct node *parent; /* Parent of the current node in the BST */ + char active; /* indicates whether the node is active or not */ +} node_t; + + +typedef struct{ + void* (*alloc)(); + void (*dealloc)(void*); + //void (*copy)(void *src, void *dst); + int (*compare)(unsigned int e1, unsigned int e2); + void (*print)(unsigned int, void*); + void *fileout; +} ilfunc_t; + + +typedef struct{ + int (*compare)(double e1, double e2); /* compare two elements (standard comparator) */ + void* (*alloc_vector)(unsigned int N); /* */ + void (*dealloc_vector)(void *v); /* */ + void* (*alloc_key)(void); /* Allocate an element for the key */ + void (*copy_key)(void *src, void *dst); /* copy into key */ + void (*print_elem)(void *e); /* print an element */ + void (*set_key)(void *e, double k); /* set a new key to element e */ + int (*compare_to_key)(void *e, double key); /* compare a key with the one of element e */ +} gen_pqueue_func_t; + + +typedef struct { + node_t* root; /* root of the BST */ + int N; /* Maximum size of the PQ */ + int last; /* last element in the PQ */ + node_t **v; /* vector of pointers to the nodes of the BST */ + char qtype; /* type of PQ, either MIN_QUEUE or MAX_QUEUE */ + ilfunc_t bst_funs; + gen_pqueue_func_t pq_funs; + gen_stack_t *node_cache; /* this is a pointer to a cache of + allocated nodes, implemented as a stack */ +} bst_pq_struct_t; + + +typedef bst_pq_struct_t* bst_pq_t; + + + + + +/* bst_pq interface */ + +/* init the BST_PQ */ + +bst_pq_t bst_pq_create(ilfunc_t* bst_funs, gen_pqueue_func_t* pq_funs, char qtype, + unsigned int N, gen_stack_t *node_cache); + +/* Destroy an existing BST_PQ */ +void bst_pq_destroy(bst_pq_t b, char clear_cache); + +/* lookup an element in the BST */ +node_t* bst_pq_lookup(bst_pq_t b, unsigned int info); + +/* insert a new element in the BST_PQ */ +void bst_pq_insert(bst_pq_t b, unsigned int info, double key); + +/* delete (or deactivate) an element in the BST_PQ */ +int bst_pq_delete(bst_pq_t b, unsigned int info); + +/* change the key of an element in the BST_PQ */ +int bst_pq_change_key(bst_pq_t b, unsigned int info, double key); + +/* return the head of the PQ */ +void* bst_pq_peek(bst_pq_t); + +/* Read the key of a given node of the BST */ +double bst_pq_get_key(bst_pq_t b, unsigned int info); + +/* Read the key of the element of index "index" in the PQ */ +double bst_pq_get_key_from_index(bst_pq_t b, int index); + +/* Dump the BST */ +void bst_pq_dump_bst(bst_pq_t b); + +/* Show the PQ */ +void bst_pq_dump_pq(bst_pq_t b); + +/* See if a node is in the BST, either active or inactive */ +node_t* bst_pq_lookup(bst_pq_t b, unsigned int info); + +/* See if a node is in the BST and is ACTIVE */ +node_t* bst_pq_lookup_active(bst_pq_t b, unsigned int info); + + +/* Insert a pre-allocated node_t in the BST_PQ */ +//void bst_pq_insert_existing(bst_pq_t b, node_t *n); + + + +#endif /*__BST_PQ_H__*/ diff --git a/src/cnm/cnm.c b/src/cnm/cnm.c new file mode 100644 index 0000000..d1afb3f --- /dev/null +++ b/src/cnm/cnm.c @@ -0,0 +1,480 @@ +/** + * 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 3 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, see + * <http://www.gnu.org/licenses/>. + * + * (c) Vincenzo Nicosia 2009-2017 -- <v.nicosia@qmul.ac.uk> + * + * This file is part of NetBunch, a package for complex network + * analysis and modelling. For more information please visit: + * + * http://www.complex-networks.net/ + * + * If you use this software, please add a reference to + * + * V. Latora, V. Nicosia, G. Russo + * "Complex Networks: Principles, Methods and Applications" + * Cambridge University Press (2017) + * ISBN: 9781107103184 + * + *********************************************************************** + * + * This program finds the communities in a graph using the greedy + * modularity optimisation algorithm proposed by Clauset, Newman, and + * Moore. + * + * References: + * + * [1] A. Clauset, M. E. J. Newman, and C. Moore. "Finding community + * structure in very large networks". Phys. Rev. E 70 (2004), + * 066111. + * + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include <math.h> + +#include "utils.h" +#include "cnm_bst_pq.h" +#include "dset.h" + + +void usage(char *argv[]){ + + printf("********************************************************************\n" + "** **\n" + "** -*- cnm -*- **\n" + "** **\n" + "** Find the communities of the input graph 'graph_in' using **\n" + "** the greedy modularity optimisation algorithm proposed by **\n" + "** Clauset, Newman, and Moore. **\n" + "** **\n" + "** The input file 'graph_in' is an edge-list. **\n" + "** If 'graph_in' is equal to '-' (dash), read the file from **\n" + "** the standard input (STDIN). **\n" + "** **\n" + "** The program prints on STDOUT the partition corresponding **\n" + "** to the largest value of modularity, in the format: **\n" + "** **\n" + "** node_1 comm_1 **\n" + "** node_2 comm_2 **\n" + "** node_3 comm_3 **\n" + "** ..... **\n" + "** **\n" + "** where 'comm_1' is the community to which 'node_1' belongs. **\n" + "** **\n" + "** The program prints on STDERR the number of communities and **\n" + "** the value of modularity obtained at each step, in the **\n" + "** format: **\n" + "** **\n" + "** ## nc: NUM_COMM Q_max: Q_MAX **\n" + "** nc_1 Q_1 **\n" + "** nc_2 Q_2 **\n" + "** nc_3 Q_3 **\n" + "** ... **\n" + "** **\n" + "** where 'nc_1', 'nc_2', 'nc_3', etc. is the number of **\n" + "** communities at the 1st, 2nd, 3rd step etc., and 'Q_1', **\n" + "** 'Q_2', 'Q_3', etc. are the value of the modularity **\n" + "** function of the corresponding node partition. The first **\n" + "** output line reports the number of communities NUM_COMM **\n" + "** and corresponding value of modularity Q_MAX of the best **\n" + "** partition found. **\n" + "** **\n" + "********************************************************************\n" + " This is Free Software - You can use and distribute it under \n" + " the terms of the GNU General Public License, version 3 or later\n\n" + " Please visit http://www.complex-networks.net for more information\n\n" + " (c) Vincenzo Nicosia 2009-2017 (v.nicosia@qmul.ac.uk)\n" + "********************************************************************\n\n" + ); + printf("Usage: %s <graph_in>\n", argv[0]); + exit(1); +} + + +/* shuffle a vector in-place */ +void shuffle_vector_ptr(unsigned int **v, unsigned int N){ + + int i, pos; + void *tmp; + + for(i=N-1; i>=0; i--){ + pos = rand() % N; + if (pos != i){ + tmp = v[i]; + v[i] = v[pos]; + v[pos] = tmp; + } + } +} + + + + +/* initialise BST-related functions */ +void set_bst_funs(ilfunc_t *f){ + + f->alloc = cnm_bst_alloc; + f->dealloc = cnm_bst_dealloc; + f->compare = cnm_bst_compare; + f->print = cnm_bst_print; + +} + +/* Initialise priority-queue-related functions */ +void set_pq_funs(gen_pqueue_func_t *f){ + + f->compare = cnm_pq_compare; + f->alloc_vector = cnm_pq_alloc_vector; + f->dealloc_vector = cnm_pq_dealloc_vector; + f->alloc_key = cnm_pq_alloc_key; + f->copy_key = cnm_pq_copy_key; + f->print_elem = cnm_pq_print_elem; + f->set_key = cnm_pq_set_key; + f->compare_to_key = cnm_pq_compare_to_key; +} + + + +void init_bsts(unsigned int *J_slap, unsigned int *r_slap, unsigned int N, + bst_pq_t *b, bst_pq_t *H, gen_stack_t *node_cache){ + + unsigned int i, j, n, m, deg_i, deg_j; + //struct_key_t dQ; + double dQ; + //struct_neigh_t ith, jth; + unsigned int K; + node_t *node_ptr; + + ilfunc_t bst_funs; + gen_pqueue_func_t pq_funs; + unsigned int *nodes; + + set_bst_funs(&bst_funs); + set_pq_funs(&pq_funs); + + K = r_slap[N]/2; + *H = bst_pq_create(&bst_funs, &pq_funs, MAX_QUEUE, N, node_cache); + nodes = malloc(N * sizeof(unsigned int)); + for (i=0; i<N; i++){ + nodes[i] = i; + } + shuffle_vector(nodes, N); + + for(n=0; n<N; n++){ + i = nodes[n]; + //ith.neigh = i; + deg_i = r_slap[i+1] - r_slap[i]; + if (deg_i == 0){ + b[i] = NULL; + continue; + } + /* create the BST_PQ for the current node i */ + b[i] = bst_pq_create(&bst_funs, &pq_funs, MAX_QUEUE, deg_i, node_cache); + /* Let's shuffle the ids of the neighbours of i, to have a somehow + balanced BST on average */ + shuffle_vector(J_slap + r_slap[i], deg_i); + /* Now we insert all the neighbours of i into b[i] */ + for(m = r_slap[i]; m<r_slap[i+1]; m++){ + j = J_slap[m]; + if(i == j) + continue; + deg_j = r_slap[j + 1] - r_slap[j]; + dQ = 2.0 * (1.0 / (2.0*K) - 1.0 * (deg_i * deg_j)/ (4.0 * K * K)); + bst_pq_insert(b[i], j, dQ); + } + /* then we get the maximum value of modularity in the neighbourhood of i */ + node_ptr = bst_pq_peek(b[i]); + if (node_ptr){ + dQ = cnm_get_Q(node_ptr); + /* and insert it into H */ + bst_pq_insert(*H, i, dQ); + } + } + free(nodes); +} + + +dset_t* cnm(unsigned int *J_slap, unsigned int *r_slap, unsigned int N, + bst_pq_t *b, bst_pq_t H){ + + double *a; + double Q; + double dQ_ik, dQ_jk, corr; + double dQ; + //struct_neigh_t ith, jth, kth; + int i, j, k; + node_t *best, *merge, *tmp; + unsigned int K; + node_t **neighs; /* pointers to the neighbours of a node */ + int num_neighs; + double Q_max; + int l, m, N_max; + double Q_step; + char found_max; + + dset_t *comms; + + Q = 0; + K = r_slap[N]/2; + + + a = malloc(N * sizeof(double)); + neighs = malloc(N * sizeof(node_t*)); + + comms = malloc(N * sizeof(dset_t)); + + for (l=0; l<N; l++){ + a[l] = 1.0 * (r_slap[l+1] - r_slap[l]) / (2.0 * K); + Q -= a[l] * a[l]; + comms[l] = NULL; + dset_makeset_id(comms + l, l); + } + + Q_max = Q; + N_max = N; + found_max = 0; + + for(l=0; l<N; l++){ + fprintf(stderr, "%d %g\n", N-l, Q); + /* Get the maximum from H and remove the element */ + best = bst_pq_peek(H); + if (!best) + break; + j = cnm_get_id(best); + + //Q_step = cnm_get_Q(best); + merge = bst_pq_peek(b[j]); + if (!merge){ + /* the node j does not have any neighbour, indeed... discard it + and continue */ + bst_pq_delete(H, j); + continue; + } + + i = cnm_get_id(merge); + /* So, we will merge community i into community j */ + if (i == j){ + /* This should never happen */ + fprintf(stderr, "Error!!!! i and j are the same node!!!!\n"); + exit(1); + } + + Q_step = cnm_get_Q(best); + if (Q_step < 0){ + found_max = 1; + } + Q += Q_step; + + + /* Let's go to the neighbours of i */ + memcpy(neighs, b[i]->v, (b[i]->last + 1) * sizeof(node_t *)); + num_neighs = b[i]->last + 1; + shuffle_vector_ptr((void*)neighs, num_neighs); + + for(m=0; m<num_neighs; m++){ + /* let's call this neighbour k */ + k = cnm_get_id(neighs[m]); + + if (k == j) + continue; + /* let's check whether k is also a neighbour of j already */ + tmp = bst_pq_lookup_active(b[j], k); + if (tmp){ /* this is a closed triangle k-i-j */ + dQ_ik = cnm_get_Q(neighs[m]); /* this is i-k*/ + dQ_jk = cnm_get_Q(tmp); /* this is j-k */ + + dQ = dQ_ik + dQ_jk; + + /* now we update Q_jk and Q_kj */ + if (bst_pq_change_key(b[j], k, dQ)){ + fprintf(stderr, "error changing key %d into %d-th tree!!! (%s: %d)\n", + k, j, __FILE__, __LINE__); + exit(1); + } + if (bst_pq_change_key(b[k], j, dQ)){ + fprintf(stderr, "error changing key %d into %d-th tree!!! (%s: %d)\n", + j, k, __FILE__, __LINE__); + exit(1); + } + bst_pq_delete(b[k], i); + } + else{ /* this is a chain k-i-j */ + dQ_ik = cnm_get_Q(neighs[m]); + corr = -2.0 * a[j] * a[k]; + dQ = dQ_ik + corr; + + /* we add Q_{jk} which did not exist before */ + bst_pq_insert(b[j], k, dQ); + /* we add Q_{kj} which did not exist before */ + bst_pq_insert(b[k], j, dQ); + bst_pq_delete(b[k], i); + } + + /* now we update the maximum value associated to k in H */ + tmp = bst_pq_peek(b[k]); + if (tmp){ + dQ = cnm_get_Q(tmp); + bst_pq_change_key(H, k, dQ); + } + } + + /* We delete the value associated to i in j */ + bst_pq_delete(b[j], i); + + + /* Let's start with the neighbours of j */ + memcpy(neighs, b[j]->v, (b[j]->last + 1) * sizeof(node_t *)); + num_neighs = b[j]->last + 1; + shuffle_vector_ptr((void*)neighs, num_neighs); + + for(m=0; m<num_neighs; m++){ + k = cnm_get_id(neighs[m]); + if (k == i) + continue; + /* let's check whether k is also a neighbour of i */ + tmp = bst_pq_lookup_active(b[i], k); + if(! tmp){ /* this is a chain i-j-k */ + dQ_jk = cnm_get_Q(neighs[m]); + corr = -2.0 * a[i] * a[k]; + dQ = dQ_jk + corr; + + /* update Q_jk and Q_kj */ + if (bst_pq_change_key(b[j], k, dQ)){ + fprintf(stderr, "error changing key %d into %d-th tree!!! (%s: %d)\n", + k, j, __FILE__, __LINE__); + exit(1); + + } + if (bst_pq_change_key(b[k], j, dQ)){ + fprintf(stderr, "error changing key %d into %d-th tree!!! (%s: %d)\n", + j, k, __FILE__, __LINE__); + exit(1); + } + } + + /* now we update the value associated to k in H */ + tmp = bst_pq_peek(b[k]); + if (tmp){ + dQ = cnm_get_Q(tmp); + bst_pq_change_key(H, k, dQ); + } + } + + /* We can now free the BST_PQ associated to node i, since it will + not be used ever again...*/ + bst_pq_destroy(b[i], 0); + b[i] = NULL; + + /* We can now remove the value associated to i in H */ + bst_pq_delete(H, i); + + /* OK, now we should update the value associated to j in H */ + tmp = bst_pq_peek(b[j]); + if (tmp){ + dQ = cnm_get_Q(tmp); + bst_pq_change_key(H, j, dQ); + } + a[j]+= a[i]; + a[i] = 0; + if (! found_max) + dset_union_opt(comms[j], comms[i]); + + if (Q>Q_max){ + Q_max = Q; + N_max = N-l-1; + } + } + fprintf(stdout, "### nc: %d Q_max: %g\n", N_max, Q_max); + free(a); + free(neighs); + + return comms; +} + + +void dump_communities(dset_t *comms, unsigned int N){ + + int i; + + for(i=0; i<N; i++){ + fprintf(stdout, "%d %d\n", i, dset_find_id_opt(comms[i])); + } +} + + +int main(int argc, char *argv[]){ + + unsigned int *J_slap = NULL, *r_slap = NULL; + unsigned int N, K; + bst_pq_t *b = NULL; + bst_pq_t H = NULL; + dset_t *comms; + int i; + + gen_stack_t *node_cache = NULL; + + FILE *filein; + + if(argc < 2){ + usage(argv); + exit(1); + } + + srand(time(NULL)); + + if (!strcmp(argv[1], "-")){ + /* take the input from STDIN */ + filein = stdin; + } + else { + filein = openfile_or_exit(argv[1], "r", 2); + } + + + read_slap(filein, &K, &N, &J_slap, &r_slap); + + b = malloc(N * sizeof(bst_pq_t)); + + node_cache = malloc(sizeof(gen_stack_t)); + gen_stack_create(node_cache); + + + init_bsts(J_slap, r_slap, N, b, &H, node_cache); + + + comms = cnm(J_slap, r_slap, N, b, H); + dump_communities(comms, N); + + free(J_slap); + free(r_slap); + for(i=0; i<N; i++){ + if(b[i]){ + bst_pq_destroy(b[i], 0); + } + if (comms[i]) + free(comms[i]); + } + free(b); + bst_pq_destroy(H, 1); + free(comms); + fclose(filein); + return 0; +} + + + diff --git a/src/cnm/cnm_bst_pq.c b/src/cnm/cnm_bst_pq.c new file mode 100644 index 0000000..acbdfad --- /dev/null +++ b/src/cnm/cnm_bst_pq.c @@ -0,0 +1,155 @@ +/** + * 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 3 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, see + * <http://www.gnu.org/licenses/>. + * + * (c) Vincenzo Nicosia 2009-2017 -- <v.nicosia@qmul.ac.uk> + * + * This file is part of NetBunch, a package for complex network + * analysis and modelling. For more information please visit: + * + * http://www.complex-networks.net/ + * + * If you use this software, please add a reference to + * + * V. Latora, V. Nicosia, G. Russo + * "Complex Networks: Principles, Methods and Applications" + * Cambridge University Press (2017) + * ISBN: 9781107103184 + * + *********************************************************************** + * + * Functions used to manage the special BST-augmented priority queue + * used in the Clauset-Newman-Moore greedy modularity optimisation + * algorithm. + * + */ + + +#include <stdio.h> +#include <stdlib.h> + +#include "cnm_bst_pq.h" + + +/* Prototypes for BST-related functions */ + +void* cnm_bst_alloc(){ + + /* nothing to be done, actually*/ + return NULL; // malloc(sizeof(struct_neigh_t)); +} + +void cnm_bst_dealloc(void *info){ + + /* Nothing to be done, actually */ + return; +} + + +int cnm_bst_compare(unsigned int e1, unsigned int e2){ + + //struct_neigh_t *i1, *i2; + + /* i1 = (struct_neigh_t*)e1; */ + /* i2 = (struct_neigh_t*)e2; */ + + //return (((struct_neigh_t*)e1)->neigh - ((struct_neigh_t*)e2)->neigh); + return e1 - e2; +} + +void cnm_bst_print(unsigned int elem, void *fout){ + fprintf(fout, " %d ", elem); +} + + +/* Prototypes for PQ-related functions */ + +int cnm_pq_compare(double e1, double e2){ + + return (e1 - e2) > 0 ? 1 : (e1 - e2) < 0 ? -1 : 0; +} + +void* cnm_pq_alloc_vector(unsigned int N){ + + return malloc(N * sizeof(node_t*)); +} + +void cnm_pq_dealloc_vector(void *v){ + + free (v); +} + +void* cnm_pq_alloc_key(void){ + + + //return malloc(sizeof(struct_key_t)); + return NULL; +} + +void cnm_pq_copy_key(void *src, void *dst){ + + struct_key_t *k1 = (struct_key_t *)src; + struct_key_t *k2 = (struct_key_t *)dst; + + k2->deltaQ = k1->deltaQ; + +} + +void cnm_pq_print_elem(void *e){ + + node_t *n = (node_t*)e; + printf("%g{%d [%d]}", n->key, n->info, n->index); + +} + + +double cnm_pq_get_key(void *e){ + + node_t *n; + + n = (node_t *)e; + return n->key; +} + +void cnm_pq_set_key(void *e, double k){ + + node_t *n; + + n = (node_t *)e; + n->key = k; +} + +int cnm_pq_compare_to_key(void *e, double key){ + + double d1; + d1 = ((node_t*)e)->key; + + return (d1 - key) > 0 ? 1 : (d1 - key) < 0 ? -1 : 0; +} + + + +unsigned int cnm_get_id(node_t *n){ + + return n->info; +} + + +double cnm_get_Q(node_t *n){ + + if (n) + return n->key; + else + return 0; +} diff --git a/src/cnm/cnm_bst_pq.h b/src/cnm/cnm_bst_pq.h new file mode 100644 index 0000000..f49687a --- /dev/null +++ b/src/cnm/cnm_bst_pq.h @@ -0,0 +1,105 @@ +/** + * 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 3 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, see + * <http://www.gnu.org/licenses/>. + * + * (c) Vincenzo Nicosia 2009-2017 -- <v.nicosia@qmul.ac.uk> + * + * This file is part of NetBunch, a package for complex network + * analysis and modelling. For more information please visit: + * + * http://www.complex-networks.net/ + * + * If you use this software, please add a reference to + * + * V. Latora, V. Nicosia, G. Russo + * "Complex Networks: Principles, Methods and Applications" + * Cambridge University Press (2017) + * ISBN: 9781107103184 + * + *********************************************************************** + * + * Functions used to manage the special BST-augmented priority queue + * used in the Clauset-Newman-Moore greedy modularity optimisation + * algorithm. + * + */ + +#ifndef __CNM_BST_PQ_H__ +#define __CNM_BST_PQ_H__ + +#include "bst_pq.h" + +/** + * + * Specific functions needed for the management of the BST_PQ used in + * the implementation of CNM + * + * (c) Vincenzo Nicosia (KatolaZ) -- 2016 + */ + +/* data structure for the id, to be used by the BST */ +typedef struct{ + int neigh; /* This is the label of a neighbour */ +} struct_neigh_t; + + +/* data structure for the key, to be used by the PQ */ +typedef struct{ + double deltaQ; /* This is the variation in modularity associated to + the join with neighbour contained in info */ +} struct_key_t; + + +/* Prototypes for BST-related functions */ + +void* cnm_bst_alloc(); + +void cnm_bst_dealloc(void*); + +//void cnm_bst_copy(unsigned int src, unsigned int dst); + +int cnm_bst_compare(unsigned int, unsigned int ); + +void cnm_bst_print(unsigned int, void*); + + +/* Prototypes for PQ-related functions */ + +int cnm_pq_compare(double e1, double e2); + +void* cnm_pq_alloc_vector(unsigned int N); + +void cnm_pq_dealloc_vector(void *v); + +void* cnm_pq_alloc_key(void); + +void cnm_pq_copy_key(void *src, void *dst); + +void cnm_pq_print_elem(void *e); + +double cnm_pq_get_key(void *e); + +void cnm_pq_set_key(void *e, double k); + +int cnm_pq_compare_to_key(void *e, double key); + +unsigned int cnm_get_id(node_t *); + +double cnm_get_Q(node_t *); + + + + +#endif /*__CNM_BST_PQ_H__*/ + |