blob: 202888cf9c0dc96ad31f2cfaa3b9c53b72cc19fb [file] [log] [blame]
/* Distributed under the OSI-approved BSD 3-Clause License. See accompanying
file Copyright.txt or for details. */
#ifndef cmComputeComponentGraph_h
#define cmComputeComponentGraph_h
#include "cmConfigure.h" // IWYU pragma: keep
#include <stack>
#include <vector>
#include "cmGraphAdjacencyList.h"
/** \class cmComputeComponentGraph
* \brief Analyze a graph to determine strongly connected components.
* Convert a directed graph into a directed acyclic graph whose nodes
* correspond to strongly connected components of the original graph.
* We use Tarjan's algorithm to enumerate the components efficiently.
* An advantage of this approach is that the components are identified
* in a topologically sorted order.
class cmComputeComponentGraph
// Represent the graph with an adjacency list.
using NodeList = cmGraphNodeList;
using EdgeList = cmGraphEdgeList;
using Graph = cmGraphAdjacencyList;
cmComputeComponentGraph(Graph const& input);
/** Get the adjacency list of the component graph. */
Graph const& GetComponentGraph() const { return this->ComponentGraph; }
EdgeList const& GetComponentGraphEdges(int c) const
return this->ComponentGraph[c];
/** Get map from component index to original node indices. */
std::vector<NodeList> const& GetComponents() const
return this->Components;
NodeList const& GetComponent(int c) const { return this->Components[c]; }
/** Get map from original node index to component index. */
std::vector<int> const& GetComponentMap() const
return this->TarjanComponents;
void TransferEdges();
Graph const& InputGraph;
Graph ComponentGraph;
// Tarjan's algorithm.
struct TarjanEntry
int Root;
int VisitIndex;
std::vector<int> TarjanVisited;
std::vector<int> TarjanComponents;
std::vector<TarjanEntry> TarjanEntries;
std::vector<NodeList> Components;
std::stack<int> TarjanStack;
int TarjanWalkId;
int TarjanIndex;
void Tarjan();
void TarjanVisit(int i);
// Connected components.