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)19 std::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