- strong_conn(1)
- www.complex-networks.net
- strong_conn(1)

`strong_conn`

- Find the strongly connected components of a directed graph

`strong_conn`

`graph_in` [SHOW]

`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.

`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.

`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 ...
```

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
```

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

V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles, Methods and Applications", Chapter 6, Cambridge University Press (2017)

V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles, Methods and Applications", Appendix 8, Cambridge University Press (2017)

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

.

- www.complex-networks.net
- September 2017
- strong_conn(1)