StronglyConnectedComponentsFinder< NodeIndex, Graph, SccOutput > Class Template Reference

#include <strongly_connected_components.h>

Public Member Functions
void	FindStronglyConnectedComponents (const NodeIndex num_nodes, const Graph &graph, SccOutput *components)
bool	NodeIsInCurrentDfsPath (NodeIndex node) const

Detailed Description

template<typename NodeIndex, typename Graph, typename SccOutput>
class StronglyConnectedComponentsFinder< NodeIndex, Graph, SccOutput >

This implementation is slightly different than a classical iterative version of Tarjan's strongly connected components algorithm. But basically it is still an iterative DFS. We use a class so memory can be reused if one needs to compute many SCC in a row. It also allows more complex behavior in the Graph or SccOutput class that might inspect the current state of the algorithm.

Todo

(user): Possible optimizations:

• Try to reserve the vectors which sizes are bounded by num_nodes.
• Use an index rather than doing push_back(), pop_back() on them.

Definition at line 105 of file strongly_connected_components.h.

Member Function Documentation

FindStronglyConnectedComponents()

template<typename NodeIndex , typename Graph , typename SccOutput >

void StronglyConnectedComponentsFinder< NodeIndex, Graph, SccOutput >::FindStronglyConnectedComponents ( const NodeIndex num_nodes, const Graph & graph, SccOutput * components )

inline

Reset the class fields.

Caching the pointer to this vector.data() avoid re-fetching it and help.

Optimization. This will always be equal to scc_start_index_.back() except when scc_stack_ is empty, in which case its value does not matter.

Loop over all the nodes not yet settled and start a DFS from each of them.

We continue the dfs from this node and set its 1-based index.

Enqueue all its adjacent nodes.

Note

if head_index == kSettledIndex, nothing happens.

Update the start of this strongly connected component.

Note

scc_start_index_ can never be empty since it first element is 1 and by definition min_head_index is 1-based and can't be 0.

We found a strongly connected component.

Definition at line 107 of file strongly_connected_components.h.

NodeIsInCurrentDfsPath()

template<typename NodeIndex , typename Graph , typename SccOutput >

bool StronglyConnectedComponentsFinder< NodeIndex, Graph, SccOutput >::NodeIsInCurrentDfsPath ( NodeIndex node ) const

inline

Advanced usage. This can be used in either the Graph or SccOutput template class to query the current state of the algorithm. It allows to build more complex variant based on the core DFS algo.

Definition at line 181 of file strongly_connected_components.h.

---

The documentation for this class was generated from the following file:

• ortools/graph/strongly_connected_components.h