1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
|
<!DOCTYPE html>
<html>
<head>
<meta http-equiv='content-type' value='text/html;charset=utf8'>
<meta name='generator' value='Ronn/v0.7.3 (http://github.com/rtomayko/ronn/tree/0.7.3)'>
<title>strong_conn(1) - Find the strongly connected components of a directed graph</title>
<style type='text/css' media='all'>
/* style: man */
body#manpage {margin:0}
.mp {max-width:100ex;padding:0 9ex 1ex 4ex}
.mp p,.mp pre,.mp ul,.mp ol,.mp dl {margin:0 0 20px 0}
.mp h2 {margin:10px 0 0 0}
.mp > p,.mp > pre,.mp > ul,.mp > ol,.mp > dl {margin-left:8ex}
.mp h3 {margin:0 0 0 4ex}
.mp dt {margin:0;clear:left}
.mp dt.flush {float:left;width:8ex}
.mp dd {margin:0 0 0 9ex}
.mp h1,.mp h2,.mp h3,.mp h4 {clear:left}
.mp pre {margin-bottom:20px}
.mp pre+h2,.mp pre+h3 {margin-top:22px}
.mp h2+pre,.mp h3+pre {margin-top:5px}
.mp img {display:block;margin:auto}
.mp h1.man-title {display:none}
.mp,.mp code,.mp pre,.mp tt,.mp kbd,.mp samp,.mp h3,.mp h4 {font-family:monospace;font-size:14px;line-height:1.42857142857143}
.mp h2 {font-size:16px;line-height:1.25}
.mp h1 {font-size:20px;line-height:2}
.mp {text-align:justify;background:#fff}
.mp,.mp code,.mp pre,.mp pre code,.mp tt,.mp kbd,.mp samp {color:#131211}
.mp h1,.mp h2,.mp h3,.mp h4 {color:#030201}
.mp u {text-decoration:underline}
.mp code,.mp strong,.mp b {font-weight:bold;color:#131211}
.mp em,.mp var {font-style:italic;color:#232221;text-decoration:none}
.mp a,.mp a:link,.mp a:hover,.mp a code,.mp a pre,.mp a tt,.mp a kbd,.mp a samp {color:#0000ff}
.mp b.man-ref {font-weight:normal;color:#434241}
.mp pre {padding:0 4ex}
.mp pre code {font-weight:normal;color:#434241}
.mp h2+pre,h3+pre {padding-left:0}
ol.man-decor,ol.man-decor li {margin:3px 0 10px 0;padding:0;float:left;width:33%;list-style-type:none;text-transform:uppercase;color:#999;letter-spacing:1px}
ol.man-decor {width:100%}
ol.man-decor li.tl {text-align:left}
ol.man-decor li.tc {text-align:center;letter-spacing:4px}
ol.man-decor li.tr {text-align:right;float:right}
</style>
<style type='text/css' media='all'>
/* style: toc */
.man-navigation {display:block !important;position:fixed;top:0;left:113ex;height:100%;width:100%;padding:48px 0 0 0;border-left:1px solid #dbdbdb;background:#eee}
.man-navigation a,.man-navigation a:hover,.man-navigation a:link,.man-navigation a:visited {display:block;margin:0;padding:5px 2px 5px 30px;color:#999;text-decoration:none}
.man-navigation a:hover {color:#111;text-decoration:underline}
</style>
</head>
<!--
The following styles are deprecated and will be removed at some point:
div#man, div#man ol.man, div#man ol.head, div#man ol.man.
The .man-page, .man-decor, .man-head, .man-foot, .man-title, and
.man-navigation should be used instead.
-->
<body id='manpage'>
<div class='mp' id='man'>
<div class='man-navigation' style='display:none'>
<a href="#NAME">NAME</a>
<a href="#SYNOPSIS">SYNOPSIS</a>
<a href="#DESCRIPTION">DESCRIPTION</a>
<a href="#PARAMETERS">PARAMETERS</a>
<a href="#OUTPUT">OUTPUT</a>
<a href="#EXAMPLES">EXAMPLES</a>
<a href="#SEE-ALSO">SEE ALSO</a>
<a href="#REFERENCES">REFERENCES</a>
<a href="#AUTHORS">AUTHORS</a>
</div>
<ol class='man-decor man-head man head'>
<li class='tl'>strong_conn(1)</li>
<li class='tc'>www.complex-networks.net</li>
<li class='tr'>strong_conn(1)</li>
</ol>
<h2 id="NAME">NAME</h2>
<p class="man-name">
<code>strong_conn</code> - <span class="man-whatis">Find the strongly connected components of a directed graph</span>
</p>
<h2 id="SYNOPSIS">SYNOPSIS</h2>
<p><code>strong_conn</code> <var>graph_in</var> [SHOW]</p>
<h2 id="DESCRIPTION">DESCRIPTION</h2>
<p><code>strong_conn</code> 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 <code>SHOW</code> is
provided, the program dumps on output also the list of nodes belonging
to each component.</p>
<h2 id="PARAMETERS">PARAMETERS</h2>
<dl>
<dt><var>graph_in</var></dt><dd><p> input graph (edge list) if equal to <code>-</code> (dash), read the edge list
from STDIN.</p></dd>
<dt class="flush">SHOW</dt><dd><p> If the (optional) second parameter is equal to <code>SHOW</code>, the program
will dump on output the list of all the nodes belonging to each
strongly connected component.</p></dd>
</dl>
<h2 id="OUTPUT">OUTPUT</h2>
<p><code>strong_conn</code> prints on the standard output the size of all the
strongly connected components of the directed graph given as input,
one per line:</p>
<pre><code> size_1
size_2
size_3
.....
</code></pre>
<p>where <code>size_1</code> is the size of the first component, <code>size_2</code> is the
size of the second component, and so on. Notice that the sizes are not
sorted. If <code>SHOW</code> is given, the program shows the list of nodes
belonging to each strongly connected component, in the format:</p>
<pre><code>size_1: node_1 node_2 node_3 ...
size_2: node_1 node_2 node_3 ...
</code></pre>
<h2 id="EXAMPLES">EXAMPLES</h2>
<p>The following command:</p>
<pre><code> $ strong_conn web-NotreDame.net
53968
1
1
1
1
1
1
....
$
</code></pre>
<p>shows on output the size of the strongly connected component of the
graph <code>web-NotreDame.net</code> (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:</p>
<pre><code> $ 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
....
$
</code></pre>
<p>It is better to save the output of <code>strong_conn</code> into a file, e.g. by
using:</p>
<pre><code> $ strong_conn web-NotreDame.net SHOW > web-NotreDame.net_scc
</code></pre>
<h2 id="SEE-ALSO">SEE ALSO</h2>
<p><span class="man-ref">components<span class="s">(1)</span></span>, <span class="man-ref">node_components<span class="s">(1)</span></span>, <span class="man-ref">largest_component<span class="s">(1)</span></span></p>
<h2 id="REFERENCES">REFERENCES</h2>
<ul>
<li><p>V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles,
Methods and Applications", Chapter 6, Cambridge University Press
(2017)</p></li>
<li><p>V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles,
Methods and Applications", Appendix 8, Cambridge University Press
(2017)</p></li>
</ul>
<h2 id="AUTHORS">AUTHORS</h2>
<p>(c) Vincenzo 'KatolaZ' Nicosia 2009-2017 <code><v.nicosia@qmul.ac.uk></code>.</p>
<ol class='man-decor man-foot man foot'>
<li class='tl'>www.complex-networks.net</li>
<li class='tc'>September 2017</li>
<li class='tr'>strong_conn(1)</li>
</ol>
</div>
</body>
</html>
|
