Example Strongly Connected Components

The following example shows how to use the LEDA function for strongly connected components.

The program creates a graph G with six nodes and five edges.

Then STRONG_COMPONENTS() is called for G and node_array<int> compnum. The values of compnum are in the range [0..c-1] where c is the number of strongly connected components of G. For all nodes v in one strongly connected component of G compnum[v] has the same value, and for two nodes v and w in different strongly connected components compnum[v]!=compnum[w]. STRONG_COMPONENTS() returns the number c of connected components in G.

Remark: The graph algorithms in LEDA are generic, that is, they accept graphs as well as parameterized graphs.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/basic_graph_alg.h>

using namespace leda;

int main()
{
  graph G; 
 
  node n0=G.new_node();node n1=G.new_node();
  node n2=G.new_node();node n3=G.new_node();
  node n4=G.new_node();node n5=G.new_node();

  G.new_edge(n0,n1);G.new_edge(n1,n2);G.new_edge(n2,n0);
  G.new_edge(n4,n5);G.new_edge(n5,n4);

  node_array<int> compnum(G);
  int c=STRONG_COMPONENTS(G,compnum);

  std::cout << "G has " << c 
       	<< " strongly connected components" << std::endl;
	
  node v;
  forall_nodes(v,G) {
    std::cout << "compnum[";
    G.print_node(v);
    std::cout << "]=" << compnum[v] << std::endl;
  }
	//compnum[v]=0 for [0],[1],[2]
	//compnum[v]=1 for [3]
    	//compnum[v]=2 for [4],[5]

  return 0;
}

See also:

Strongly Connected Components

Graphs

Parameterized Graphs

Node Arrays

Basic Graph Algorithms

Graphs and Related Data Types

Manual Entries:

Manual Page Basic Graph Algorithms