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
|
.\" generated with Ronn/v0.7.3
.\" http://github.com/rtomayko/ronn/tree/0.7.3
.
.TH "COMPONENTS" "1" "September 2017" "www.complex-networks.net" "www.complex-networks.net"
.
.SH "NAME"
\fBcomponents\fR \- Find the connected components of a graph
.
.SH "SYNOPSIS"
\fBcomponents\fR \fIgraph_in\fR [SHOW]
.
.SH "DESCRIPTION"
\fBcomponents\fR finds the connected components of the undirected graph given as input using the Depth\-First Search algorithm, and prints the size of each of them\. If the optional second parameter \fBSHOW\fR is provided, the program dumps on output also the list of nodes belonging to each component\.
.
.SH "PARAMETERS"
.
.TP
\fIgraph_in\fR
input graph (edge list) if equal to \fB\-\fR (dash), read the edge list from STDIN\.
.
.TP
SHOW
If the (optional) second parameter is equal to \fBSHOW\fR, the program will dump on output the list of all the nodes belonging to each connected component\.
.
.SH "OUTPUT"
\fBcomponents\fR prints on the standard output the size of all the connected components of the undirected graph given as input, one per line:
.
.IP "" 4
.
.nf
size_1
size_2
size_3
\.\.\.\.\.
.
.fi
.
.IP "" 0
.
.P
where \fBsize_1\fR is the size of the first component, \fBsize_2\fR is the size of the second component, and so on\. Notice that the sizes are not sorted\. If \fBSHOW\fR is given, the program shows the list of nodes belonging to each component, in the format:
.
.IP "" 4
.
.nf
size_1: node_1 node_2 node_3 \.\.\.
size_2: node_1 node_2 node_3 \.\.\.
.
.fi
.
.IP "" 0
.
.SH "EXAMPLES"
The following command:
.
.IP "" 4
.
.nf
$ components er_1000_5000\.txt
1000
$
.
.fi
.
.IP "" 0
.
.P
shows on output the size of the only connected component of the graph \fBer_1000_5000\.txt\fR\. In this case the graph has only one connected component (it is a super\-critical Erdos\-Renyi random graph with 1000 nodes and 5000 edges)\. A more interesting example can be obtained using the graph \fBer_1000_2000\.txt\fR:
.
.IP "" 4
.
.nf
$ components er_1000_2000\.txt
985
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
$
.
.fi
.
.IP "" 0
.
.P
In this case, the graph has 16 connected components: one of those components contains 985 nodes, while the other 15 components consist of isolated nodes\. If we want to know who are the nodes belonging to each connected component, we run:
.
.IP "" 4
.
.nf
$ components er_1000_2000\.txt SHOW
985: 0 1 2 3 4 5 6 7 8 9 10 11 12\.\.\.\.\.
\.\.\.
1: 63
1: 75
1: 218
1: 222
1: 368
1: 398
1: 441
1: 566
1: 572
1: 663
1: 715
1: 756
1: 863
1: 883
1: 917
$
.
.fi
.
.IP "" 0
.
.P
If we run:
.
.IP "" 4
.
.nf
$ components er_1000_2000\.txt SHOW > er_1000_2000\.txt_components
.
.fi
.
.IP "" 0
.
.P
the result of \fBcomponents\fR will be saved in the file \fBer_1000_2000\.txt_components\fR\.
.
.SH "SEE ALSO"
strong_conn(1), node_components(1), largest_component(1)
.
.SH "REFERENCES"
.
.IP "\(bu" 4
V\. Latora, V\. Nicosia, G\. Russo, "Complex Networks: Principles, Methods and Applications", Chapter 3, Cambridge University Press (2017)
.
.IP "\(bu" 4
V\. Latora, V\. Nicosia, G\. Russo, "Complex Networks: Principles, Methods and Applications", Appendix 8, Cambridge University Press (2017)
.
.IP "" 0
.
.SH "AUTHORS"
(c) Vincenzo \'KatolaZ\' Nicosia 2009\-2017 \fB<v\.nicosia@qmul\.ac\.uk>\fR\.
|
