blob: 878e36d95106e7840330b199f841ef415956ed75 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
/* Distributed under the OSI-approved BSD 3-Clause License. See accompanying
file Copyright.txt or https://cmake.org/licensing for details. */
#pragma once
#include "cmConfigure.h" // IWYU pragma: keep
#include <cstddef>
#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
{
public:
// Represent the graph with an adjacency list.
using NodeList = cmGraphNodeList;
using EdgeList = cmGraphEdgeList;
using Graph = cmGraphAdjacencyList;
cmComputeComponentGraph(Graph const& input);
~cmComputeComponentGraph();
/** Run the computation. */
void Compute();
/** Get the adjacency list of the component graph. */
Graph const& GetComponentGraph() const { return this->ComponentGraph; }
EdgeList const& GetComponentGraphEdges(size_t 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(size_t c) const { return this->Components[c]; }
/** Get map from original node index to component index. */
std::vector<size_t> const& GetComponentMap() const
{
return this->TarjanComponents;
}
static const size_t INVALID_COMPONENT;
private:
void TransferEdges();
Graph const& InputGraph;
Graph ComponentGraph;
// Tarjan's algorithm.
struct TarjanEntry
{
size_t Root;
size_t VisitIndex;
};
std::vector<size_t> TarjanVisited;
std::vector<size_t> TarjanComponents;
std::vector<TarjanEntry> TarjanEntries;
std::vector<NodeList> Components;
std::stack<size_t> TarjanStack;
size_t TarjanWalkId;
size_t TarjanIndex;
void Tarjan();
void TarjanVisit(size_t i);
// Connected components.
};
|
