summaryrefslogtreecommitdiff
path: root/Source/cmComputeComponentGraph.h
blob: 202888cf9c0dc96ad31f2cfaa3b9c53b72cc19fb (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
/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   file Copyright.txt or https://cmake.org/licensing 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
{
public:
  // Represent the graph with an adjacency list.
  using NodeList = cmGraphNodeList;
  using EdgeList = cmGraphEdgeList;
  using Graph = cmGraphAdjacencyList;

  cmComputeComponentGraph(Graph const& input);
  ~cmComputeComponentGraph();

  /** 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;
  }

private:
  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.
};

#endif