### 5.3.2. Basic graph algorithms

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.

#### Algorithms for systematic searching

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.

#### Strongly connected components

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

Filename: WordComponents.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
```#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?
// Step through all 4 letters of s
for(int i = 0; i < 4; i++) {
// 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
// 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
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.

#### Running times and further information

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.

 Exercise 64. In Figure 3.3 we drew the layers around the word LOVE. Compute these layers with the function `BFS()`. Use a GraphWin and the method `set_position()` of `GraphWin` for visualizing the layers.