diff options
Diffstat (limited to 'src/components')
| -rw-r--r-- | src/components/Makefile.am | 10 | ||||
| -rw-r--r-- | src/components/Makefile.in | 614 | ||||
| -rw-r--r-- | src/components/components.c | 207 | ||||
| -rw-r--r-- | src/components/largest_component.c | 191 | ||||
| -rw-r--r-- | src/components/node_components.c | 442 | ||||
| -rw-r--r-- | src/components/strong_conn.c | 277 |
6 files changed, 1741 insertions, 0 deletions
diff --git a/src/components/Makefile.am b/src/components/Makefile.am new file mode 100644 index 0000000..df629ab --- /dev/null +++ b/src/components/Makefile.am @@ -0,0 +1,10 @@ +include ../common.mk +bin_PROGRAMS = components largest_component strong_conn node_components +components_SOURCES = components.c ../utils/utils.c ../include/utils.h +components_LDADD = -lm +largest_component_SOURCES = largest_component.c ../utils/utils.c ../include/utils.h +largest_component_LDADD = -lm +strong_conn_SOURCES = strong_conn.c ../utils/utils.c ../include/utils.h +strong_conn_LDADD = -lm +node_components_SOURCES = node_components.c ../utils/utils.c ../include/utils.h +node_components_LDADD = -lm diff --git a/src/components/Makefile.in b/src/components/Makefile.in new file mode 100644 index 0000000..a36407b --- /dev/null +++ b/src/components/Makefile.in @@ -0,0 +1,614 @@ +# 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 = components$(EXEEXT) largest_component$(EXEEXT) \ + strong_conn$(EXEEXT) node_components$(EXEEXT) +subdir = src/components +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_components_OBJECTS = components.$(OBJEXT) ../utils/utils.$(OBJEXT) +components_OBJECTS = $(am_components_OBJECTS) +components_DEPENDENCIES = +am_largest_component_OBJECTS = largest_component.$(OBJEXT) \ + ../utils/utils.$(OBJEXT) +largest_component_OBJECTS = $(am_largest_component_OBJECTS) +largest_component_DEPENDENCIES = +am_node_components_OBJECTS = node_components.$(OBJEXT) \ + ../utils/utils.$(OBJEXT) +node_components_OBJECTS = $(am_node_components_OBJECTS) +node_components_DEPENDENCIES = +am_strong_conn_OBJECTS = strong_conn.$(OBJEXT) \ + ../utils/utils.$(OBJEXT) +strong_conn_OBJECTS = $(am_strong_conn_OBJECTS) +strong_conn_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 = $(components_SOURCES) $(largest_component_SOURCES) \ + $(node_components_SOURCES) $(strong_conn_SOURCES) +DIST_SOURCES = $(components_SOURCES) $(largest_component_SOURCES) \ + $(node_components_SOURCES) $(strong_conn_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 +components_SOURCES = components.c ../utils/utils.c ../include/utils.h +components_LDADD = -lm +largest_component_SOURCES = largest_component.c ../utils/utils.c ../include/utils.h +largest_component_LDADD = -lm +strong_conn_SOURCES = strong_conn.c ../utils/utils.c ../include/utils.h +strong_conn_LDADD = -lm +node_components_SOURCES = node_components.c ../utils/utils.c ../include/utils.h +node_components_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/components/Makefile'; \ + $(am__cd) $(top_srcdir) && \ + $(AUTOMAKE) --foreign src/components/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) + +components$(EXEEXT): $(components_OBJECTS) $(components_DEPENDENCIES) $(EXTRA_components_DEPENDENCIES) + @rm -f components$(EXEEXT) + $(AM_V_CCLD)$(LINK) $(components_OBJECTS) $(components_LDADD) $(LIBS) + +largest_component$(EXEEXT): $(largest_component_OBJECTS) $(largest_component_DEPENDENCIES) $(EXTRA_largest_component_DEPENDENCIES) + @rm -f largest_component$(EXEEXT) + $(AM_V_CCLD)$(LINK) $(largest_component_OBJECTS) $(largest_component_LDADD) $(LIBS) + +node_components$(EXEEXT): $(node_components_OBJECTS) $(node_components_DEPENDENCIES) $(EXTRA_node_components_DEPENDENCIES) + @rm -f node_components$(EXEEXT) + $(AM_V_CCLD)$(LINK) $(node_components_OBJECTS) $(node_components_LDADD) $(LIBS) + +strong_conn$(EXEEXT): $(strong_conn_OBJECTS) $(strong_conn_DEPENDENCIES) $(EXTRA_strong_conn_DEPENDENCIES) + @rm -f strong_conn$(EXEEXT) + $(AM_V_CCLD)$(LINK) $(strong_conn_OBJECTS) $(strong_conn_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)/utils.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/components.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/largest_component.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/node_components.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/strong_conn.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/components/components.c b/src/components/components.c new file mode 100644 index 0000000..a5dc52d --- /dev/null +++ b/src/components/components.c @@ -0,0 +1,207 @@ +/** + * 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 implements the Depth-First Search algorithm to find + * the connected components of a graph provided as input. + * + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "utils.h" + + + +void usage(char *argv[]){ + printf("********************************************************************\n" + "** **\n" + "** -*- components -*- **\n" + "** **\n" + "** Find the connected components of an undirected graph **\n" + "** and print on output their size and/or the list of nodes **\n" + "** belonging to each component. The first parameter 'graph_in' **\n" + "** is the name of the file containing the edge list of the **\n" + "** graph. **\n" + "** **\n" + "** If 'graph_in' is equal to '-' (dash), read the edge list **\n" + "** from standard input (STDIN). **\n" + "** **\n" + "** The program prints on output the SIZE of each connected **\n" + "** component of the graph, one per line: **\n" + "** **\n" + "** size_1 **\n" + "** size_2 **\n" + "** size_3 **\n" + "** **\n" + "** The sizes are in no particular order. **\n" + "** **\n" + "** If 'SHOW' is given as second argument, the list of nodes **\n" + "** belonging to each component is printed as well, in the **\n" + "** format: **\n" + "** **\n" + "** size_1: node_1 node_2 node_3 .... **\n" + "** size_2: node_1 node_2 node_3 .... **\n" + "** size_3: node_1 node_2 node_3 .... **\n" + "** **\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 2010-2017 (v.nicosia@qmul.ac.uk)\n" + "********************************************************************\n\n" + ); + printf("Usage: %s <graph_in> [SHOW]\n\n" , argv[0]); +} + + + +/** + * + * Depth-First search on node i.... + * + */ +int dfs(unsigned int i, unsigned int *J_slap, unsigned int *r_slap, + unsigned int N, unsigned int nc, + unsigned int *ic, unsigned int *f, + char reset){ + + static unsigned int time; + unsigned int j, s; + + if(reset){ + time = 0; + } + + ic[i] = nc; + s = 1; + time += 1; + + for(j=r_slap[i]; j<r_slap[i+1]; j++){ + if (ic[J_slap[j]] == 0){ + s += dfs(J_slap[j], J_slap, r_slap, N, nc, ic, f, 0); + } + } + time += 1; + f[i] = time; + return s; +} + +/** + * + * Find all the components of the given graph, using the Depth-First + * Search algorithm + * + */ + +int components(unsigned int *J_slap, unsigned int *r_slap, + unsigned int N, unsigned int **ic, + unsigned int **f, unsigned int **sizes){ + + unsigned int nc, s; + unsigned int i; + + *ic = malloc(N * sizeof(unsigned int)); + *f = malloc(N * sizeof(unsigned int)); + *sizes = malloc((N+1) * sizeof(unsigned int)); + + for(i=0; i<N; i++){ + (*ic)[i] = 0; + (*f)[i] = 0; + } + nc = 0; + for(i=0; i<N; i++){ + while( i<N && (*ic) [i] != 0 ) + i += 1; + if (i == N) + break; + nc += 1; + s = dfs(i, J_slap, r_slap, N, nc, *ic, *f, 1); + (*sizes)[nc] = s; + } + return nc; +} + + +int main(int argc, char *argv[]){ + + + FILE *filein; + unsigned int N, K; + unsigned int *J_slap, *r_slap; + unsigned int *ic, *f, *sizes; + unsigned int nc, i, j; + char show = 0; + + + if (argc < 2){ + usage(argv); + exit(1); + } + if (argc >2 && !my_strcasecmp("SHOW", argv[2])){ + show = 1; + } + + 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); + fclose(filein); + + nc = components(J_slap, r_slap, N, &ic, &f, &sizes); + for(i=1; i<=nc; i++){ + printf("%d", sizes[i]); + if (show){ + printf(":"); + for(j=0; j<N; j++){ + if (ic[j] == i){ + printf(" %d", j); + } + } + printf("\n"); + } + else{ + printf("\n"); + } + } + free(f); + free(ic); + free(sizes); + free(J_slap); + free(r_slap); +} diff --git a/src/components/largest_component.c b/src/components/largest_component.c new file mode 100644 index 0000000..06a26eb --- /dev/null +++ b/src/components/largest_component.c @@ -0,0 +1,191 @@ +/** + * 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 + * + *********************************************************************** + * + * Compute the largest connected component of a graph (i.e., the + * connected component that contains the largest number of nodes). + * + * + */ + + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "utils.h" + + +void usage(char *argv[]){ + printf("********************************************************************\n" + "** **\n" + "** -*- largest_component -*- **\n" + "** **\n" + "** Find the largest connected component of 'graph_in'. **\n" + "** **\n" + "** The input file 'graph_in' is an edge-list: **\n" + "** **\n" + "** I_1 J_1 **\n" + "** I_2 J_2 **\n" + "** I_3 J_3 **\n" + "** ... ... **\n" + "** I_K J_K **\n" + "** **\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 edge list of the largest **\n" + "** connected component of 'graph_in'. **\n" + "** **\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]); +} + + + +/** + * + * Depth-First search on the node i.... + * + */ +int dfs(unsigned int i, unsigned int *J_slap, unsigned int *r_slap, + unsigned int N, unsigned int nc, + unsigned int *ic, unsigned int *f, + char reset){ + + static unsigned int time; + unsigned int j, s; + + if(reset){ + time = 0; + } + + ic[i] = nc; + s = 1; + time += 1; + + for(j=r_slap[i]; j<r_slap[i+1]; j++){ + if (ic[J_slap[j]] == 0){ + s += dfs(J_slap[j], J_slap, r_slap, N, nc, ic, f, 0); + } + } + time += 1; + f[i] = time; + return s; +} + +/** + * + * Find all the components of the given graph + * + */ +int components(unsigned int *J_slap, unsigned int *r_slap, + unsigned int N, unsigned int **ic, + unsigned int **f, unsigned int **sizes){ + + unsigned int nc, s; + unsigned int i; + + *ic = malloc(N * sizeof(unsigned int)); + *f = malloc(N * sizeof(unsigned int)); + *sizes = malloc(N * sizeof(unsigned int)); + + for(i=0; i<N; i++){ + (*ic)[i] = 0; + (*f)[i] = 0; + } + nc = 0; + for(i=0; i<N; i++){ + while( (*ic) [i] != 0 && i < N) + i += 1; + if (i == N) + break; + nc += 1; + s = dfs(i, J_slap, r_slap, N, nc, *ic, *f, 1); + (*sizes)[nc] = s; + } + return nc; +} + + +int main(int argc, char *argv[]){ + + + FILE *filein; + unsigned int N, K; + unsigned int *J_slap, *r_slap; + unsigned int *ic, *f, *sizes; + unsigned int nc, i, j, max_c; + + + if (argc < 2){ + usage(argv); + exit(1); + } + + 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); + fclose(filein); + nc = components(J_slap, r_slap, N, &ic, &f, &sizes); + + max_c = 1; + for(i=2; i<=nc; i++){ + if (sizes[i] > sizes[max_c]) + max_c = i; + } + for(i=0; i<N; i++){ + if(ic[i] == max_c){ + for(j=r_slap[i]; j<r_slap[i+1]; j++){ + if (J_slap[j] > i) + fprintf(stdout, "%d %d\n", i, J_slap[j]); + } + } + } + free(J_slap); + free(r_slap); + free(ic); + free(f); + free(sizes); +} diff --git a/src/components/node_components.c b/src/components/node_components.c new file mode 100644 index 0000000..33477f6 --- /dev/null +++ b/src/components/node_components.c @@ -0,0 +1,442 @@ +/** + * 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 computes (the size of) all the components associated + * to a node, namely the OUT-, IN-, SCC (strongly connected + * component), and the WCC (weekly connected component). + * + * + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "utils.h" + +#define COMP_IN 0x01 +#define COMP_OUT 0x02 +#define COMP_WCC 0x04 +#define COMP_SCC 0x08 +#define COMP_ALL (COMP_IN | COMP_OUT | COMP_WCC | COMP_SCC) + + +void usage(char *argv[]){ + printf("********************************************************************\n" + "** **\n" + "** -*- node_components -*- **\n" + "** **\n" + "** Find all the components associated to a node of a directed **\n" + "** graph, namely the IN-, OUT-, SCC, and WCC, and print on **\n" + "** output their size and/or the list of nodes belonging to **\n" + "** each component. The first parameter 'graph_in' is the name **\n" + "** of the file containing the edge list of the graph. **\n" + "** **\n" + "** The second parameter 'node' is the label of the node whose **\n" + "** components we are interested in. The (optional) third **\n" + "** parameter <component> can be one of 'IN', 'OUT', 'INOUT', **\n" + "** 'SCC', 'WCC', respectively corresponding to the IN-, OUT-, **\n" + "** IN- and OUT-, strongly connected and weakly connected **\n" + "** component to which 'node' belongs. If the <component> is **\n" + "** 'ALL', the program computes all the components to which **\n" + "** 'node' belongs. If no third parameter is provided, all **\n" + "** the components are computed by default. **\n" + "** **\n" + "** If SHOW is given as fourth argument, the list nodes in each **\n" + "** component is dumped on output as well. **\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 2010-2017 (v.nicosia@qmul.ac.uk)\n" + "********************************************************************\n\n" + ); + printf("Usage: %s <graph_in> <node> [<component> [SHOW]]\n\n" , argv[0]); +} + +int dfs(unsigned int i, unsigned int *J_slap, unsigned int *r_slap, + unsigned int N, unsigned int nc, + unsigned int *ic, unsigned int *f, + char reset){ + + static unsigned int time = 0; + unsigned int j, s; + + if(reset){ + time = 0; + } + + ic[i] = nc; + s = 1; + + for(j=r_slap[i]; j<r_slap[i+1]; j++){ + if (ic[J_slap[j]] == 0){ + s += dfs(J_slap[j], J_slap, r_slap, N, nc, ic, f, 0); + } + } + f[time] = i; + time += 1; + return s; +} + + + +/** + * + * Find all the components of the given graph + * + */ + +int components(unsigned int *J_slap, unsigned int *r_slap, + unsigned int N, unsigned int **ic, + unsigned int **f, unsigned int **sizes){ + + unsigned int nc, s; + unsigned int i; + + *ic = malloc(N * sizeof(unsigned int)); + *f = malloc(N * sizeof(unsigned int)); + *sizes = malloc((N+1) * sizeof(unsigned int)); + + for(i=0; i<N; i++){ + (*ic)[i] = 0; + (*f)[i] = 0; + } + nc = 0; + for(i=0; i<N; i++){ + while( i < N && (*ic) [i] != 0 ) + i += 1; + if (i == N) + break; + nc += 1; + if (nc ==1){ + s = dfs(i, J_slap, r_slap, N, nc, *ic, *f, 1); + } + else{ + s = dfs(i, J_slap, r_slap, N, nc, *ic, *f, 0); + } + + (*sizes)[nc] = s; + } + return nc; +} + + + +int components_rev(unsigned int *J_slap, unsigned int *r_slap, + unsigned int N, unsigned int **ic, + unsigned int *f, unsigned int **f_T, unsigned int **sizes){ + + unsigned int nc, s; + unsigned int idx; + int i; + + *ic = malloc(N * sizeof(unsigned int)); + *f_T = malloc(N * sizeof(unsigned int)); + *sizes = malloc(N * sizeof(unsigned int)); + + for(i=0; i<N; i++){ + (*ic)[i] = 0; + } + nc = 0; + for(i=N-1; i>=0; i--){ + idx = f[i]; + while( (*ic) [idx] != 0 && i > 0 ){ + i -= 1; + idx = f[i]; + } + if (i == 0) + break; + nc += 1; + if (nc == 1){ + s = dfs(idx, J_slap, r_slap, N, nc, *ic, *f_T, 1); + } + else{ + s = dfs(idx, J_slap, r_slap, N, nc, *ic, *f_T, 1); + } + (*sizes)[nc] = s; + } + return nc; +} + + +void compute_comp_out(FILE *filein, unsigned int node, char show){ + + unsigned int N, K, size, i; + unsigned int *J_slap, *r_slap, *ic, *f, *I, *J; + + I = J = NULL; + K = read_ij(filein, &I, &J); + rewind(filein); + + J_slap = NULL; + r_slap = NULL; + /* obtain the SLAP representation of the graph */ + N = convert_ij2slap(I, J, K, &r_slap, &J_slap); + + ic = malloc(N * sizeof(unsigned int)); + f = malloc(N * sizeof(unsigned int)); + for(i=0; i<N; i++){ + ic[i] = 0; + } + + + size = dfs(node, J_slap, r_slap, N, 1, ic, f, 1); + + printf("OUT: %d", size); + if (show){ + for(i=0; i<N; i++){ + if (ic[i] == 1){ + printf(" %d", i); + } + } + } + printf("\n"); + free(ic); + free(f); + free(I); + free(J); + free(J_slap); + free(r_slap); +} + +void compute_comp_in(FILE *filein, unsigned int node, char show){ + + unsigned int N, K, size, i; + unsigned int *J_slap, *r_slap, *ic, *f, *I, *J; + + I = J = NULL; + + K = read_ij(filein, &I, &J); + rewind(filein); + + J_slap = NULL; + r_slap = NULL; + /* obtain the SLAP representation of the graph */ + N = convert_ij2slap(J, I, K, &r_slap, &J_slap); + + + ic = malloc(N * sizeof(unsigned int)); + f = malloc(N * sizeof(unsigned int)); + for(i=0; i<N; i++){ + ic[i] = 0; + } + + + size = dfs(node, J_slap, r_slap, N, 1, ic, f, 1); + + printf("IN: %d", size); + if (show){ + for(i=0; i<N; i++){ + if (ic[i] == 1){ + printf(" %d", i); + } + } + } + printf("\n"); + free(ic); + free(f); + free(I); + free(J); + free(J_slap); + free(r_slap); +} + + + + +void compute_wcc(FILE *filein, unsigned int node, char show){ + + unsigned int N, K; + unsigned int *J_slap, *r_slap; + unsigned int *ic, *f, *sizes; + unsigned int j, node_comp; + + + read_slap(filein, &K, &N, &J_slap, &r_slap); + + rewind(filein); + + components(J_slap, r_slap, N, &ic, &f, &sizes); + + node_comp = ic[node]; + + printf("WCC: %d", sizes[node_comp]); + if (show){ + //printf(": "); + for(j=0; j<N; j++){ + if (ic[j] == node_comp){ + printf(" %d", j); + } + } + printf("\n"); + } + else{ + printf("\n"); + } + free(sizes); + free(J_slap); + free(r_slap); + free(ic); + free(f); +} + +void compute_scc(FILE *filein, unsigned int node, char show){ + + unsigned int N, K, N1, N2; + unsigned int *I, *J, *J_slap, *r_slap, *J_slap_T, *r_slap_T; + unsigned int *ic, *f, *ic_T, *f_T, *sizes_T, *sizes; + unsigned int j; + unsigned int node_comp; + + + + I = J = NULL; + K = read_ij(filein, &I, &J); + + rewind(filein); + + + J_slap = J_slap_T = NULL; + r_slap = r_slap_T = NULL; + /* obtain the SLAP representation of the graph */ + N1 = convert_ij2slap(I, J, K, &r_slap, &J_slap); + /* obtain the SLAP representation of the transposed graph */ + N2 = convert_ij2slap(J, I, K, &r_slap_T, &J_slap_T); + N = N1 >= N2 ? N1 : N2; + + components(J_slap, r_slap, N, &ic, &f, &sizes); + components_rev(J_slap_T, r_slap_T, N, &ic_T, f, &f_T, &sizes_T); + + node_comp = ic_T[node]; + + + printf("SCC: %d", sizes_T[node_comp]); + if (show){ + for(j=0; j<N; j++){ + if (ic_T[j] == node_comp){ + printf(" %d", j); + } + } + printf("\n"); + } + else{ + printf("\n"); + } + free(sizes); + free(sizes_T); + free(I); + free(J); + free(J_slap); + free(r_slap); + free(J_slap_T); + free(r_slap_T); + free(ic); + free(ic_T); + free(f); + free(f_T); +} + + + +int main(int argc, char *argv[]){ + + unsigned int mode=0, node; + FILE *filein; + char show = 0; + + + if (argc < 3){ + usage(argv); + exit(1); + } + + filein = openfile_or_exit(argv[1], "r", 2); + + node = atoi(argv[2]); + + + if (argc < 4){ + mode = COMP_ALL; + } + else{ + if (!my_strcasecmp("IN", argv[3])){ + mode |= COMP_IN; + } + else if (!my_strcasecmp("OUT", argv[3])){ + mode |= COMP_OUT; + } + else if (!my_strcasecmp("INOUT", argv[3])){ + mode |= COMP_OUT | COMP_IN; + } + else if (!my_strcasecmp("WCC", argv[3])){ + mode |= COMP_WCC; + } + else if (!my_strcasecmp("SCC", argv[3])){ + mode |= COMP_SCC; + } + else if (!my_strcasecmp("ALL", argv[3])){ + mode |= COMP_ALL; + } + } + + if (argc > 4 && !my_strcasecmp("SHOW", argv[4])){ + show = 1; + } + + + switch(mode){ + case COMP_IN: + compute_comp_in(filein, node, show); + break; + case COMP_OUT: + compute_comp_out(filein, node, show); + break; + case COMP_IN | COMP_OUT: + compute_comp_in(filein, node, show); + compute_comp_out(filein, node, show); + break; + case COMP_WCC: + compute_wcc(filein, node, show); + break; + case COMP_SCC: + compute_scc(filein, node, show); + break; + default: + compute_comp_in(filein, node, show); + compute_comp_out(filein, node, show); + compute_wcc(filein, node, show); + compute_scc(filein, node, show); + }; + fclose(filein); + +} diff --git a/src/components/strong_conn.c b/src/components/strong_conn.c new file mode 100644 index 0000000..4c0f80d --- /dev/null +++ b/src/components/strong_conn.c @@ -0,0 +1,277 @@ +/** + * 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 (size of the) strongly connected components + * of a directed graph given as input. We use the Kosaraju-Sharir + * algorithm, which performs two DFS scans of the graph, the first + * time using the original DFS algorithm on the graph, and the second + * time using the transposed graph and a slightly modified version of + * "components", which traverses the nodes of the graph in descending + * order of finishing time. + * + * + * + */ + + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "utils.h" + + +void usage(char *argv[]){ + printf("********************************************************************\n" + "** **\n" + "** -*- strong_conn -*- **\n" + "** **\n" + "** Find the strongly connected components of a directed graph **\n" + "** and print on output their size and/or the list of nodes **\n" + "** belonging to each component. The first parameter 'graph_in' **\n" + "** is the name of the file containing the edge list of the **\n" + "** graph. **\n" + "** **\n" + "** If 'graph_in' is equal to '-' (dash), read the edge list **\n" + "** from standard input (STDIN). **\n" + "** **\n" + "** The program prints on output the SIZE of each strongly **\n" + "** connected component of the graph, one per line: **\n" + "** **\n" + "** size_1 **\n" + "** size_2 **\n" + "** size_3 **\n" + "** **\n" + "** The sizes are in no particular order. **\n" + "** **\n" + "** If 'SHOW' is given as second argument, the list of nodes **\n" + "** belonging to each component is printed as well, in the **\n" + "** format: **\n" + "** **\n" + "** size_1: node_1 node_2 node_3 .... **\n" + "** size_2: node_1 node_2 node_3 .... **\n" + "** size_3: node_1 node_2 node_3 .... **\n" + "** **\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 2010-2017 (v.nicosia@qmul.ac.uk)\n" + "********************************************************************\n\n" + ); + printf("Usage: %s <graph_in> [SHOW]\n\n" , argv[0]); +} + +int dfs(unsigned int i, unsigned int *J_slap, unsigned int *r_slap, + unsigned int N, unsigned int nc, + unsigned int *ic, unsigned int *f, + char reset){ + + static unsigned int time = 0; + unsigned int j, s; + + if(reset){ + time = 0; + } + + ic[i] = nc; + s = 1; + + for(j=r_slap[i]; j<r_slap[i+1]; j++){ + if (ic[J_slap[j]] == 0){ + s += dfs(J_slap[j], J_slap, r_slap, N, nc, ic, f, 0); + } + } + f[time] = i; + time += 1; + return s; +} + + + +/** + * + * Find all the components of the given graph + * + */ + +int components(unsigned int *J_slap, unsigned int *r_slap, + unsigned int N, unsigned int **ic, + unsigned int **f, unsigned int **sizes){ + + unsigned int nc, s; + unsigned int i; + + *ic = malloc(N * sizeof(unsigned int)); + *f = malloc(N * sizeof(unsigned int)); + *sizes = malloc(N * sizeof(unsigned int)); + + for(i=0; i<N; i++){ + (*ic)[i] = 0; + (*f)[i] = 0; + } + nc = 0; + for(i=0; i<N; i++){ + while( (*ic) [i] != 0 && i < N) + i += 1; + if (i == N) + break; + nc += 1; + if (nc ==1){ + s = dfs(i, J_slap, r_slap, N, nc, *ic, *f, 1); + } + else{ + s = dfs(i, J_slap, r_slap, N, nc, *ic, *f, 0); + } + //printf("s: %d\n", s); + (*sizes)[nc] = s; + } + return nc; +} + + +/** + * + * Find the components of the transposed graph, where the nodes are + * visited in descending order of their finishing time + * + */ + +int components_rev(unsigned int *J_slap, unsigned int *r_slap, + unsigned int N, unsigned int **ic, + unsigned int *f, unsigned int **f_T, unsigned int **sizes){ + + unsigned int nc, s; + unsigned int idx; + int i; + + *ic = malloc(N * sizeof(unsigned int)); + *f_T = malloc(N * sizeof(unsigned int)); + *sizes = malloc((N+1) * sizeof(unsigned int)); + + for(i=0; i<N; i++){ + (*ic)[i] = 0; + } + nc = 0; + for(i=N-1; i>=0; i--){ + idx = f[i]; + while( i >0 && (*ic) [idx] != 0 ){ + i -= 1; + idx = f[i]; + } + if (i < 0) + break; + nc += 1; + if (nc == 1){ + s = dfs(idx, J_slap, r_slap, N, nc, *ic, *f_T, 1); + } + else{ + s = dfs(idx, J_slap, r_slap, N, nc, *ic, *f_T, 1); + } + (*sizes)[nc] = s; + } + return nc; +} + + + +int main(int argc, char *argv[]){ + + + FILE *filein; + unsigned int N, K, N1, N2; + unsigned int *I, *J, *J_slap, *r_slap, *J_slap_T, *r_slap_T; + unsigned int *ic, *f, *sizes, *ic_T, *f_T, *sizes_T; + unsigned int i, j, nc_T; + char show = 0; + + if (argc < 2){ + usage(argv); + exit(1); + } + if (argc == 3 && !my_strcasecmp("SHOW", argv[2])){ + show = 1; + } + + if (!strcmp(argv[1], "-")){ + /* take the input from STDIN */ + filein = stdin; + } + else { + filein = openfile_or_exit(argv[1], "r", 2); + } + + + I = J = NULL; + K = read_ij(filein, &I, &J); + J_slap = J_slap_T = NULL; + r_slap = r_slap_T = NULL; + /* obtain the SLAP representation of the graph */ + N1 = convert_ij2slap(I, J, K, &r_slap, &J_slap); + /* obtain the SLAP representation of the transposed graph */ + N2 = convert_ij2slap(J, I, K, &r_slap_T, &J_slap_T); + N = N1 >= N2 ? N1 : N2; + components(J_slap, r_slap, N, &ic, &f, &sizes); + + fclose(filein); + + + nc_T = components_rev(J_slap_T, r_slap_T, N, &ic_T, f, &f_T, &sizes_T); + + for(i=1; i<=nc_T; i++){ + printf("%d", sizes_T[i]); + if (show){ + printf(":"); + for(j=0; j<N; j++){ + if (ic_T[j] == i){ + printf(" %d", j); + } + } + printf("\n"); + } + else{ + printf("\n"); + } + } + free(J_slap); + free(r_slap); + free(J_slap_T); + free(r_slap_T); + free(ic); + free(f); + free(sizes); + free(ic_T); + free(f_T); + free(sizes_T); + free(I); + free(J); +} |