1 #ifndef NOM_GRAPH_ALGORITHMS_H 2 #error "This should only be included by Graph/Algorithms.h" 7 using NodeRef =
typename Graph<T, U>::NodeRef;
16 typename Graph<T, U>::EdgeRef edge;
36 template <
typename T,
typename U = T>
class Tarjans {
39 using WrappedGraph = Graph<NodeWrapper, EdgeWrapper>;
40 using WrappedSubgraph = Subgraph<NodeWrapper, EdgeWrapper>;
44 std::vector<typename WrappedGraph::NodeRef> Stack;
45 Graph<T, U> *InputGraph;
46 WrappedGraph WrappedInputGraph;
47 std::vector<WrappedSubgraph> WrappedSCCs;
55 std::unordered_map<typename Graph<T, U>::NodeRef,
56 typename WrappedGraph::NodeRef>
59 for (
const auto &n : InputGraph->getMutableNodes()) {
60 NodeWrapper wrappedNode(n);
62 WrappedInputGraph.createNode(std::move(wrappedNode));
65 for (
const auto &e : InputGraph->getMutableEdges()) {
66 EdgeWrapper wrappedEdge = {e};
67 WrappedInputGraph.createEdge(n_to_wrappedNode[e->tail()],
68 n_to_wrappedNode[e->head()],
69 std::move(wrappedEdge));
75 void connect(
typename WrappedGraph::NodeRef n) {
76 n->mutableData()->Index = Index;
77 n->mutableData()->LowLink = Index;
80 Stack.emplace_back(n);
81 n->mutableData()->OnStack =
true;
83 for (
const auto &outEdge : n->getOutEdges()) {
84 typename WrappedGraph::NodeRef newNode = outEdge->head();
86 if (newNode->data().Index == -1) {
88 n->mutableData()->LowLink =
89 std::min(n->data().LowLink, newNode->data().LowLink);
91 }
else if (newNode->data().OnStack) {
92 n->mutableData()->LowLink =
93 std::min(n->data().LowLink, newNode->data().Index);
98 if (n->data().LowLink == n->data().Index) {
99 WrappedSubgraph wrappedSCC;
101 typename WrappedGraph::NodeRef w;
104 w->mutableData()->OnStack =
false;
106 wrappedSCC.addNode(w);
111 const auto &sccNodes = wrappedSCC.getNodes();
112 for (
const auto &sccNode : sccNodes) {
113 for (
const auto &outEdge : sccNode->getOutEdges()) {
114 if (std::find(sccNodes.begin(), sccNodes.end(), outEdge->head()) !=
116 wrappedSCC.addEdge(outEdge);
120 WrappedSCCs.emplace_back(wrappedSCC);
130 for (
auto wrappedNode : wrappedSubgraph.getNodes()) {
131 s.addNode(wrappedNode->data().node);
133 for (
auto wrappedEdge : wrappedSubgraph.getEdges()) {
134 s.addEdge(wrappedEdge->data().edge);
139 std::vector<Subgraph<T, U>> run() {
140 for (
auto n : WrappedInputGraph.getMutableNodes()) {
141 if (n->data().Index == -1) {
146 std::vector<Subgraph<T, U>> sccs;
147 for (
auto wrappedSCC : WrappedSCCs) {
148 sccs.emplace_back(unwrapSubgraph(wrappedSCC));
156 template <
typename T,
typename U>
157 std::vector<Subgraph<T, U>> tarjans(Graph<T, U> *g) {
Subgraph< T, U > unwrapSubgraph(const WrappedSubgraph &wrappedSubgraph)
Helper function for recovering a valid subgraph output.
Tarjans(Graph< T, U > *g)
Constructor wraps the input graph with an annotated graph set up with the datastructures needed for t...
void connect(typename WrappedGraph::NodeRef n)
Helper function for finding strongly connected components.
Tarjans algorithm implementation.