Example Biconnected Components

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

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

Then BICONNECTED_COMPONENTS() is called for G and edge_array<int> compnum. The values of compnum are in the range [0..c-1] where c is the number of biconnected components of G. For all edges e in one biconnected component of G compnum[e] has the same value, and for two edges e and f in different biconnected components compnum[e]!=compnum[f]. BICONNECTED_COMPONENTS() returns the number c of biconnected components.

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();
  node n6=G.new_node(); node n7=G.new_node();

  G.new_edge(n0,n1); G.new_edge(n0,n2);
  G.new_edge(n1,n3); G.new_edge(n2,n3);
  G.new_edge(n4,n5); G.new_edge(n5,n6);
 
  edge_array<int> compnum(G);
  int c=BICONNECTED_COMPONENTS(G,compnum);

  std::cout << "G has " << c << " biconnected components" << std::endl;
	    //G has 4 biconnected components

  edge e;
  forall_edges(e,G) {
    std::cout << "compnum[";
    G.print_edge(e);
    std::cout << "]=" << compnum[e] << std::endl;
  }
	//compnum[e]=0 for [0]->[1],[0]->[2],[1]->[3],[2]->[3]
	//compnum[e]=1 for [5]->[6]
	//compnum[e]=2 for [4]->[5]
	//[7] is isolated node

  return 0;
}

See also:

Biconnected Components

Graphs

Parameterized Graphs

Edge Arrays

Basic Graph Algorithms

Graphs and Related Data Types

Manual Entries:

Manual Page Basic Graph Algorithms