Learning objectives
Algorithms from basic_graph_alg.h 
Computing strongly connected components with STRONG_COMPONENTS() 
The header file
basic_graph_alg.h
declares, among others, the basic graph algorithms for
traversing a graph systematically and decomposing it into components.
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.
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 4letter 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,

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.
Exercise 64.  In Figure 3.3 we
drew the layers around the word LOVE. Compute these layers
with the function 