1 #ifndef TARJAN_SCC_HPP
2 #define TARJAN_SCC_HPP
3 
4 #include "extractor/node_based_edge.hpp"
5 #include "extractor/query_node.hpp"
6 #include "util/deallocating_vector.hpp"
7 #include "util/percent.hpp"
8 #include "util/typedefs.hpp"
9 
10 #include "util/integer_range.hpp"
11 #include "util/log.hpp"
12 #include "util/std_hash.hpp"
13 #include "util/timing_util.hpp"
14 
15 #include "osrm/coordinate.hpp"
16 #include <boost/assert.hpp>
17 #include <cstdint>
18 
19 #include <algorithm>
20 #include <climits>
21 #include <memory>
22 #include <stack>
23 #include <vector>
24 
25 namespace osrm
26 {
27 namespace extractor
28 {
29 
30 template <typename GraphT> class TarjanSCC
31 {
32     struct TarjanStackFrame
33     {
TarjanStackFrameosrm::extractor::TarjanSCC::TarjanStackFrame34         explicit TarjanStackFrame(NodeID v, NodeID parent) : v(v), parent(parent) {}
35         NodeID v;
36         NodeID parent;
37     };
38 
39     struct TarjanNode
40     {
TarjanNodeosrm::extractor::TarjanSCC::TarjanNode41         TarjanNode() : index(SPECIAL_NODEID), low_link(SPECIAL_NODEID), on_stack(false) {}
42         unsigned index;
43         unsigned low_link;
44         bool on_stack;
45     };
46 
47     std::vector<unsigned> components_index;
48     std::vector<NodeID> component_size_vector;
49     const GraphT &m_graph;
50     std::size_t size_one_counter;
51 
52   public:
TarjanSCC(const GraphT & graph)53     TarjanSCC(const GraphT &graph)
54         : components_index(graph.GetNumberOfNodes(), SPECIAL_NODEID), m_graph(graph),
55           size_one_counter(0)
56     {
57         BOOST_ASSERT(m_graph.GetNumberOfNodes() > 0);
58     }
59 
Run()60     void Run()
61     {
62         TIMER_START(SCC_RUN);
63         const NodeID max_node_id = m_graph.GetNumberOfNodes();
64 
65         // The following is a hack to distinguish between stuff that happens
66         // before the recursive call and stuff that happens after
67         std::stack<TarjanStackFrame> recursion_stack;
68         // true = stuff before, false = stuff after call
69         std::stack<NodeID> tarjan_stack;
70         std::vector<TarjanNode> tarjan_node_list(max_node_id);
71         unsigned component_index = 0, size_of_current_component = 0;
72         unsigned large_component_count = 0;
73         unsigned index = 0;
74         std::vector<bool> processing_node_before_recursion(max_node_id, true);
75         for (const NodeID node : util::irange(0u, max_node_id))
76         {
77             if (SPECIAL_NODEID == components_index[node])
78             {
79                 recursion_stack.emplace(TarjanStackFrame(node, node));
80             }
81 
82             while (!recursion_stack.empty())
83             {
84                 TarjanStackFrame currentFrame = recursion_stack.top();
85                 const NodeID u = currentFrame.parent;
86                 const NodeID v = currentFrame.v;
87                 recursion_stack.pop();
88 
89                 const bool before_recursion = processing_node_before_recursion[v];
90 
91                 if (before_recursion && tarjan_node_list[v].index != UINT_MAX)
92                 {
93                     continue;
94                 }
95 
96                 if (before_recursion)
97                 {
98                     // Mark frame to handle tail of recursion
99                     recursion_stack.emplace(currentFrame);
100                     processing_node_before_recursion[v] = false;
101 
102                     // Mark essential information for SCC
103                     tarjan_node_list[v].index = index;
104                     tarjan_node_list[v].low_link = index;
105                     tarjan_stack.push(v);
106                     tarjan_node_list[v].on_stack = true;
107                     ++index;
108 
109                     for (const auto current_edge : m_graph.GetAdjacentEdgeRange(v))
110                     {
111                         const auto vprime = m_graph.GetTarget(current_edge);
112 
113                         if (SPECIAL_NODEID == tarjan_node_list[vprime].index)
114                         {
115                             recursion_stack.emplace(TarjanStackFrame(vprime, v));
116                         }
117                         else
118                         {
119                             if (tarjan_node_list[vprime].on_stack &&
120                                 tarjan_node_list[vprime].index < tarjan_node_list[v].low_link)
121                             {
122                                 tarjan_node_list[v].low_link = tarjan_node_list[vprime].index;
123                             }
124                         }
125                     }
126                 }
127                 else
128                 {
129                     processing_node_before_recursion[v] = true;
130                     tarjan_node_list[u].low_link =
131                         std::min(tarjan_node_list[u].low_link, tarjan_node_list[v].low_link);
132                     // after recursion, lets do cycle checking
133                     // Check if we found a cycle. This is the bottom part of the recursion
134                     if (tarjan_node_list[v].low_link == tarjan_node_list[v].index)
135                     {
136                         NodeID vprime;
137                         do
138                         {
139                             vprime = tarjan_stack.top();
140                             tarjan_stack.pop();
141                             tarjan_node_list[vprime].on_stack = false;
142                             components_index[vprime] = component_index;
143                             ++size_of_current_component;
144                         } while (v != vprime);
145 
146                         component_size_vector.emplace_back(size_of_current_component);
147 
148                         if (size_of_current_component > 1000)
149                         {
150                             ++large_component_count;
151                             util::Log(logDEBUG) << "large component [" << component_index
152                                                 << "]=" << size_of_current_component;
153                         }
154 
155                         ++component_index;
156                         size_of_current_component = 0;
157                     }
158                 }
159             }
160         }
161 
162         TIMER_STOP(SCC_RUN);
163         util::Log() << "Found " << component_index << " SCC (" << large_component_count
164                     << " large, " << (component_index - large_component_count) << " small)";
165         util::Log() << "SCC run took: " << TIMER_MSEC(SCC_RUN) / 1000. << "s";
166 
167         size_one_counter = std::count_if(component_size_vector.begin(),
168                                          component_size_vector.end(),
169                                          [](unsigned value) { return 1 == value; });
170     }
171 
GetNumberOfComponents() const172     std::size_t GetNumberOfComponents() const { return component_size_vector.size(); }
173 
GetSizeOneCount() const174     std::size_t GetSizeOneCount() const { return size_one_counter; }
175 
GetComponentSize(const unsigned component_id) const176     unsigned GetComponentSize(const unsigned component_id) const
177     {
178         return component_size_vector[component_id];
179     }
180 
GetComponentID(const NodeID node) const181     unsigned GetComponentID(const NodeID node) const { return components_index[node]; }
182 };
183 } // namespace extractor
184 } // namespace osrm
185 
186 #endif /* TARJAN_SCC_HPP */
187