1 #ifndef OSRM_PARTITIONER_REMOVE_UNCONNECTED_HPP 2 #define OSRM_PARTITIONER_REMOVE_UNCONNECTED_HPP 3 4 #include "util/log.hpp" 5 #include "util/typedefs.hpp" 6 7 #include <boost/assert.hpp> 8 9 #include <algorithm> 10 #include <vector> 11 12 namespace osrm 13 { 14 namespace partitioner 15 { 16 using Partition = std::vector<CellID>; 17 18 template <typename GraphT> removeUnconnectedBoundaryNodes(const GraphT & edge_based_graph,std::vector<Partition> & partitions)19std::size_t removeUnconnectedBoundaryNodes(const GraphT &edge_based_graph, 20 std::vector<Partition> &partitions) 21 { 22 auto num_unconnected = 0; 23 auto could_not_fix = 0; 24 for (int level_index = partitions.size() - 1; level_index >= 0; level_index--) 25 { 26 struct Witness 27 { 28 NodeID id; 29 std::size_t induced_border_edges; 30 }; 31 std::vector<Witness> witnesses; 32 for (NodeID node = 0; node < edge_based_graph.GetNumberOfNodes(); ++node) 33 { 34 witnesses.clear(); 35 36 bool is_source = false; 37 bool is_target = false; 38 39 const auto cell_id = partitions[level_index][node]; 40 for (auto edge : edge_based_graph.GetAdjacentEdgeRange(node)) 41 { 42 const auto data = edge_based_graph.GetEdgeData(edge); 43 const auto target = edge_based_graph.GetTarget(edge); 44 const auto target_cell_id = partitions[level_index][target]; 45 if (target_cell_id == cell_id) 46 { 47 is_source |= data.forward; 48 is_target |= data.backward; 49 } 50 else 51 { 52 witnesses.push_back({target, 0}); 53 } 54 } 55 56 const auto unconnected = witnesses.size() > 0 && !is_source && !is_target; 57 58 if (unconnected) 59 { 60 num_unconnected++; 61 62 if (level_index < static_cast<int>(partitions.size() - 1)) 63 { 64 auto new_end = std::remove_if( 65 witnesses.begin(), witnesses.end(), [&](const auto &witness) { 66 return partitions[level_index + 1][node] != 67 partitions[level_index + 1][witness.id]; 68 }); 69 witnesses.resize(new_end - witnesses.begin()); 70 } 71 if (witnesses.size() == 0) 72 { 73 could_not_fix++; 74 continue; 75 } 76 77 for (auto &witness : witnesses) 78 { 79 for (auto edge : edge_based_graph.GetAdjacentEdgeRange(node)) 80 { 81 auto target = edge_based_graph.GetTarget(edge); 82 for (auto sublevel_index = level_index; sublevel_index >= 0; 83 --sublevel_index) 84 { 85 if (partitions[sublevel_index][target] != 86 partitions[sublevel_index][witness.id]) 87 witness.induced_border_edges++; 88 } 89 } 90 } 91 92 auto best_witness = std::min_element( 93 witnesses.begin(), witnesses.end(), [](const auto &lhs, const auto &rhs) { 94 return lhs.induced_border_edges < rhs.induced_border_edges; 95 }); 96 BOOST_ASSERT(best_witness != witnesses.end()); 97 98 // assign `node` to same subcells as `best_witness` 99 for (auto sublevel_index = level_index; sublevel_index >= 0; --sublevel_index) 100 { 101 partitions[sublevel_index][node] = partitions[sublevel_index][best_witness->id]; 102 } 103 } 104 } 105 } 106 107 if (could_not_fix > 0) 108 util::Log(logWARNING) << "Could not fix " << could_not_fix << " unconnected boundary nodes"; 109 110 return num_unconnected; 111 } 112 } // namespace partitioner 113 } // namespace osrm 114 115 #endif 116