Strongly connected components refer to connected components in a directed graph, and is useful to simplify a directed graph, for instance, merging all vertices in the same strongly connected components to be a big vertex, could produce a Directed Acyclic Graph (DAG) with less number of vertices. This post documents two well-known algorithms (i.e., Kosaraju’s Algorithm and Tarjan’s Algorithm) that solve the strongly connected component problem.

Topological sorting is an operation performed on Directed Acyclic Graph (DAG) to generate a order of all vertices, so that vertex v would not appear before vertex u if there exists a path from vertex u to vertex v.

Weakly connected components refer to connected components in an undirected graph, also known as friend circle problem. This post documents three common solutions to figure out the number of connected components in graphs.

I had a post, Container Types in C++, where I introduced a bit about one of the C++ containters std::map.
Yesterday I ran into an interesting use case of map, namely, I wanted to use map with customized key, bi-match unsigned integer pair. This post talks about the way to customize key for std::map, and issues and solution to get a bi-match unsigned integer pair work correctly as the key.

DFS (Deepth First Search) and BFS (Breadth First Search) are two approaches to traverse tree. It is relatively easy to implement BFS in an iterative manner (with the help of queue). While it is a bit challenging to do DFS without reursion.

Reuse distance calculation is a problem related to cache design and evaluation. With a sequence of address references, reuse distance is defined as the number of unique addresses between two references to the same address. For example, in “A B C A C B”, the first B has an infinite reuse distance since it has never been rereferenced, while the second B has a reuse distance of 2.

Several algorithms were discovered long time ago. The following three are included in this post:

• Stack approach - Mattson et al. in 1970;
• Bit Vector approach - Bennett & Kruskal in 1975;
• AVL Tree approach - Olken in 1981;