From 3aee2fd43e3059a699af2b63c6f2395e5a55e515 Mon Sep 17 00:00:00 2001 From: KatolaZ Date: Wed, 27 Sep 2017 15:06:31 +0100 Subject: First commit on github -- NetBunch 1.0 --- doc/strong_conn.1.html | 199 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 199 insertions(+) create mode 100644 doc/strong_conn.1.html (limited to 'doc/strong_conn.1.html') diff --git a/doc/strong_conn.1.html b/doc/strong_conn.1.html new file mode 100644 index 0000000..4b4e0af --- /dev/null +++ b/doc/strong_conn.1.html @@ -0,0 +1,199 @@ + + + + + + strong_conn(1) - Find the strongly connected components of a directed graph + + + + + +
+ + + +
    +
  1. strong_conn(1)
  2. +
  3. www.complex-networks.net
  4. +
  5. strong_conn(1)
  6. +
+ +

NAME

+

+ strong_conn - Find the strongly connected components of a directed graph +

+ +

SYNOPSIS

+ +

strong_conn graph_in [SHOW]

+ +

DESCRIPTION

+ +

strong_conn finds the strongly connected components of the directed +graph given as input using the Kosaraju-Sharir algorithm, and prints +the size of each of them. If the optional second parameter SHOW is +provided, the program dumps on output also the list of nodes belonging +to each component.

+ +

PARAMETERS

+ +
+
graph_in

input graph (edge list) if equal to - (dash), read the edge list + from STDIN.

+
SHOW

If the (optional) second parameter is equal to SHOW, the program + will dump on output the list of all the nodes belonging to each + strongly connected component.

+
+ + +

OUTPUT

+ +

strong_conn prints on the standard output the size of all the +strongly connected components of the directed graph given as input, +one per line:

+ +
    size_1
+    size_2
+    size_3
+    .....
+
+ +

where size_1 is the size of the first component, size_2 is the +size of the second component, and so on. Notice that the sizes are not +sorted. If SHOW is given, the program shows the list of nodes +belonging to each strongly connected component, in the format:

+ +
size_1: node_1 node_2 node_3 ...
+size_2: node_1 node_2 node_3 ...
+
+ +

EXAMPLES

+ +

The following command:

+ +
      $ strong_conn web-NotreDame.net 
+      53968
+      1
+      1
+      1
+      1
+      1
+      1
+      ....
+      $
+
+ +

shows on output the size of the strongly connected component of the +graph web-NotreDame.net (the NotreDame WWW data set), in no particular +order. In this case the graph has 203609 strongly connected +components, most of them containing only 1 isolated node. If we want +to know who are the nodes belonging to each connected component, we +run:

+ +
      $ strong_conn web-NotreDame.net SHOW
+      53968: 0 1 3 4 5 6 7 8.....
+      ..... 325727 325728
+      1: 351
+      1: 350
+      1: 2209
+      1: 2208
+      1: 2206
+      1: 10609
+      ....
+      $
+
+ +

It is better to save the output of strong_conn into a file, e.g. by +using:

+ +
      $ strong_conn web-NotreDame.net SHOW > web-NotreDame.net_scc
+
+ +

SEE ALSO

+ +

components(1), node_components(1), largest_component(1)

+ +

REFERENCES

+ + + + +

AUTHORS

+ +

(c) Vincenzo 'KatolaZ' Nicosia 2009-2017 <v.nicosia@qmul.ac.uk>.

+ + +
    +
  1. www.complex-networks.net
  2. +
  3. September 2017
  4. +
  5. strong_conn(1)
  6. +
+ +
+ + -- cgit v1.2.3