1 #ifndef NODE_BASED_GRAPH_HPP
2 #define NODE_BASED_GRAPH_HPP
3
4 #include "extractor/class_data.hpp"
5 #include "extractor/node_based_edge.hpp"
6 #include "extractor/node_data_container.hpp"
7 #include "util/dynamic_graph.hpp"
8 #include "util/graph_utils.hpp"
9
10 #include <tbb/parallel_sort.h>
11
12 #include <iostream>
13 #include <memory>
14 #include <utility>
15
16 namespace osrm
17 {
18 namespace util
19 {
20
21 struct NodeBasedEdgeData
22 {
NodeBasedEdgeDataosrm::util::NodeBasedEdgeData23 NodeBasedEdgeData()
24 : weight(INVALID_EDGE_WEIGHT), duration(INVALID_EDGE_WEIGHT),
25 distance(INVALID_EDGE_DISTANCE), geometry_id({0, false}), reversed(false),
26 annotation_data(-1)
27 {
28 }
29
NodeBasedEdgeDataosrm::util::NodeBasedEdgeData30 NodeBasedEdgeData(EdgeWeight weight,
31 EdgeWeight duration,
32 EdgeDistance distance,
33 GeometryID geometry_id,
34 bool reversed,
35 extractor::NodeBasedEdgeClassification flags,
36 AnnotationID annotation_data)
37 : weight(weight), duration(duration), distance(distance), geometry_id(geometry_id),
38 reversed(reversed), flags(flags), annotation_data(annotation_data)
39 {
40 }
41
42 EdgeWeight weight;
43 EdgeWeight duration;
44 EdgeDistance distance;
45 GeometryID geometry_id;
46 bool reversed : 1;
47 extractor::NodeBasedEdgeClassification flags;
48 AnnotationID annotation_data;
49 };
50
51 // Check if two edge data elements can be compressed into a single edge (i.e. match in terms of
52 // their meta-data).
CanBeCompressed(const NodeBasedEdgeData & lhs,const NodeBasedEdgeData & rhs,const extractor::EdgeBasedNodeDataContainer & node_data_container)53 inline bool CanBeCompressed(const NodeBasedEdgeData &lhs,
54 const NodeBasedEdgeData &rhs,
55 const extractor::EdgeBasedNodeDataContainer &node_data_container)
56 {
57 if (!(lhs.flags == rhs.flags))
58 return false;
59
60 auto const &lhs_annotation = node_data_container.GetAnnotation(lhs.annotation_data);
61 auto const &rhs_annotation = node_data_container.GetAnnotation(rhs.annotation_data);
62
63 if (lhs_annotation.is_left_hand_driving != rhs_annotation.is_left_hand_driving)
64 return false;
65
66 if (lhs_annotation.travel_mode != rhs_annotation.travel_mode)
67 return false;
68
69 return lhs_annotation.classes == rhs_annotation.classes;
70 }
71
72 using NodeBasedDynamicGraph = DynamicGraph<NodeBasedEdgeData>;
73
74 /// Factory method to create NodeBasedDynamicGraph from NodeBasedEdges
75 /// Since DynamicGraph expects directed edges, we need to insert
76 /// two edges for undirected edges.
77 inline NodeBasedDynamicGraph
NodeBasedDynamicGraphFromEdges(NodeID number_of_nodes,const std::vector<extractor::NodeBasedEdge> & input_edge_list)78 NodeBasedDynamicGraphFromEdges(NodeID number_of_nodes,
79 const std::vector<extractor::NodeBasedEdge> &input_edge_list)
80 {
81 auto edges_list = directedEdgesFromCompressed<NodeBasedDynamicGraph::InputEdge>(
82 input_edge_list,
83 [](NodeBasedDynamicGraph::InputEdge &output_edge,
84 const extractor::NodeBasedEdge &input_edge) {
85 output_edge.data.weight = input_edge.weight;
86 output_edge.data.duration = input_edge.duration;
87 output_edge.data.distance = input_edge.distance;
88 output_edge.data.flags = input_edge.flags;
89 output_edge.data.annotation_data = input_edge.annotation_data;
90
91 BOOST_ASSERT(output_edge.data.weight > 0);
92 BOOST_ASSERT(output_edge.data.duration > 0);
93 BOOST_ASSERT(output_edge.data.distance >= 0);
94 });
95
96 tbb::parallel_sort(edges_list.begin(), edges_list.end());
97
98 return NodeBasedDynamicGraph(number_of_nodes, edges_list);
99 }
100 } // namespace util
101 } // namespace osrm
102
103 #endif // NODE_BASED_GRAPH_HPP
104