Kosaraju

template<class G> class Kosaraju

#include <kosaraju.hpp>

Computes the strongly connected components of a directed graph. If there is a path from a vertex u to a vertex v, then scc(u) <= scc(v).

Public Functions

inline Kosaraju(const G &graph)

inline int sccCount() const: Returns the number of strongly connected components of the graph.

inline const std::vector<std::vector<int>> &sccs() const: Returns a vector containing the strongly connected components of the graph.

inline int scc(const int v) const: Returns the ID of the strongly connected component containing a given vertex.

Private Functions

inline void findPostOrdering(const int v)

inline void findSccs(const int v)

Private Members

const G *m_graph

std::vector<int> m_postOrdering

const int NOT_VISITED = -2

const int VISITED_1 = -1

std::vector<int> m_states

std::vector<std::vector<int>> m_sccs