summaryrefslogtreecommitdiff
path: root/src/components
diff options
context:
space:
mode:
Diffstat (limited to 'src/components')
-rw-r--r--src/components/Makefile.am10
-rw-r--r--src/components/Makefile.in614
-rw-r--r--src/components/components.c207
-rw-r--r--src/components/largest_component.c191
-rw-r--r--src/components/node_components.c442
-rw-r--r--src/components/strong_conn.c277
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);
+}