1. components(1)
  2. www.complex-networks.net
  3. components(1)

NAME

components - Find the connected components of a graph

SYNOPSIS

components graph_in [SHOW]

DESCRIPTION

components 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 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 connected component.

OUTPUT

components prints on the standard output the size of all the connected components of the undirected 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 component, in the format:

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

EXAMPLES

The following command:

      $ components er_1000_5000.txt 
      1000
      $

shows on output the size of the only connected component of the graph er_1000_5000.txt. 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 er_1000_2000.txt:

      $ components er_1000_2000.txt 
      985
      1
      1
      1
      1
      1
      1
      1
      1
      1
      1
      1
      1
      1
      1
      1
      $

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:

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

If we run:

      $ components er_1000_2000.txt SHOW > er_1000_2000.txt_components

the result of components will be saved in the file er_1000_2000.txt_components.

SEE ALSO

strong_conn(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. September 2017
  3. components(1)