Thereof, we already came to know TOPSORT() for topological sorting, BFS() for breadth first search, and DFS_NUM() for depth first search with numbering.

The function DFS() works as DFS_NUM(); it does not carry out a numbering of the nodes with DFS numbers and completion numbers, though. Its signature is

list<node> DFS(graph& G, node s, node_array<bool>& reached);

It starts a depth first search in the node s and visits all reachable nodes v whose associated value reached[v] has been set to false before the call; it then changes reached[v] to true. So the search can be restricted a priori by means of the node array reached; in most cases, it is initialized with the default value false, so that DFS() searches the whole graph. The function returns a list of the nodes reached during the search.

A directed graph is called strongly connected if each node is reachable from each other node via a path. A strongly connected component is a maximal strongly connected subgraph. Figure 5.19 shows a graph with 4 strongly connected components. In each such component, each node is reachable from each other node; if the component is left, there is no way back any more.

Figure 5.19. Strongly connected components

A graph with 4 strongly connected components. Nodes with the same number belong to the same component.

The strongly connected components of a graph can be computed with the function STRONG_COMPONENTS(). Besides the graph itself, it needs a node_array<int> compnum as an argument. This node array must be valid on the graph; for each node, the number of the component that it belongs to will be recorded therein; the numbering starts with 0. Nodes with the same compnum value belong to the same strongly connected component. The function returns the number of components found.

As an example of use, we want to find out the strongly connected components of our neighborhood graph of 4-letter words. Is it possible that there is only one strongly connected component, that is, that each word can be derived into each other word? Or does the graph decompose into a great many small components? LEDA will give us the answer in a moment!

We build up the graph, compute the strongly connected components, sort these according to the number of nodes (words) contained in them, and output them according to this ordering.

#include <LEDA/graph.h>
#include <LEDA/d_array.h>
#include <LEDA/list.h>
#include <LEDA/basic_graph_alg.h>
#include <LEDA/array.h>
#include <fstream>
#include <iostream>

using leda::GRAPH;
using leda::node;
using leda::edge;
using leda::node_array;
using leda::d_array;
using leda::array;
using leda::string;
using leda::list;
using std::cout;
using std::cin;


int main()
{
  std::ifstream is("Data/4LetterWords.txt");

  
  GRAPH<string, int> G;
  d_array <string, node> D;
  string s;

  // Read all words. Each word becomes a node of G
  while (is >> s) {
    node v = G.new_node(s);
    D[s] = v; // Which node belongs to which word?
    // Find all adjacent words and record adjacency in G
    // Step through all 4 letters of s
    for(int i = 0; i < 4; i++) {
      string s_adjacent = s;
      // Step through all letters of the alphabet
      for(char c = 'A'; c <= 'Z'; c++) {
        if(c == s[i]) continue;
        // Candidate adjacent word: replace letter i
        s_adjacent[i] = c;
        if(D.defined(s_adjacent)) {
          // Adjacent word found
          G.new_edge(D[s], D[s_adjacent], 0);
          // G.new_edge(D[s_adjacent], D[s], 0); // see below
        }       
      }
    }
  }

  G.make_bidirected(); // by this we don't need to insert reverse edges

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

  array<list<node> > component(num_sccs); // can't use list_node here!
  node v;
  forall_nodes(v, G) 
    component[compnum[v]].append(v);

  // compare function for lists: L1 > L2 if it has more elements
  int list_cmp(const list<node>& L1, const list<node>& L2);

  // sort components according to their size
  component.sort(list_cmp);

  // output all components 
  for(int i = 0; i < num_sccs ; i++) {
    int size = component[i].size();
    cout << "\nComponent: " << i << "  Size: " << size << "\n";
    forall(v, component[i])
      cout << G.inf(v) << " ";
    cout << "\n";
  }
}


int list_cmp(const list<node>& L1, const list<node>& L2) 
{
  int size1 = L1.size(); // list_node has no size() method
  int size2 = L2.size();

  if(size1 < size2) return +1;
  else if(size1 > size2) return -1;
  else return 0;
}

The (shortened) output of this program is:

Component: 0  Size: 3767
AAHS AALS ABAS ABBA ABBE ABED ABET ABLE ABLY ABOS ABUT ABYE ABYS ACED ACES ACHE
ACHY ACID ACME ACNE ACRE ACTA ACTS ACYL ADDS ADIT ADOS AEON AERO AERY AFAR AGAR
AGAS AGED AGEE AGER AGES AGHA AGIN AGIO AGLY AGMA AGOG AGON AGUE AHEM AIDE AIDS
...
Component: 1  Size: 5
GURU JUDO KUDO KUDU KURU

Component: 2  Size: 3
ORDO ORZO OUZO

Component: 6  Size: 2
SNYE STYE
...
Component: 12  Size: 2
APSE ARSE

Component: 75  Size: 1
EXPO
...
Component: 76  Size: 1
ZOIC

So there are 77 components altogether. Very most words are contained in one huge component with 3767 words. The next smaller component is indeed very small and comprises only 5 words. Most components consist of isolated words.

	Important
	Like many other graph algorithms of LEDA, STRONG_COMPONENTS() expects a directed graph as input. Since we are dealing here with a graph that is undirected in the classical sense, we additionally insert the reverse edge for every inserted edge; as discussed in Section 5.2.3, we use make_bidirected() for that purpose.

The function COMPONENTS() works like the function STRONG_COMPONENTS() presented here; it considers the underlying graph undirected (in the classical sense), though. So this function is also applicable here.

All functions presented here take a running time of O(n+m).

There are further functions declared in basic_graph_alg.h. For example, there is BICONNECTED_COMPONENTS() for computing the biconnected components of a graph.

More information about these functions can be found on the corresponding manual page.