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