1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
#pragma once
#include "routing/directions_engine.hpp"
#include "routing/index_road_graph.hpp"
#include "routing/route.hpp"
#include "routing/traffic_stash.hpp"
#include "traffic/traffic_info.hpp"
#include "routing_common/bicycle_model.hpp"
#include "routing_common/car_model.hpp"
#include "routing_common/pedestrian_model.hpp"
#include "base/cancellable.hpp"
#include <memory>
#include <queue>
#include <set>
#include <vector>
namespace routing
{
/// \returns true when there exists a routing mode where the feature with |types| can be used.
template <class TTypes>
bool IsRoad(TTypes const & types)
{
return CarModel::AllLimitsInstance().HasRoadType(types) ||
PedestrianModel::AllLimitsInstance().HasRoadType(types) ||
BicycleModel::AllLimitsInstance().HasRoadType(types);
}
void FillSegmentInfo(std::vector<Segment> const & segments, std::vector<Junction> const & junctions,
Route::TTurns const & turns, Route::TStreets const & streets,
Route::TTimes const & times, std::shared_ptr<TrafficStash> const & trafficStash,
std::vector<RouteSegment> & routeSegment);
void ReconstructRoute(IDirectionsEngine & engine, IndexRoadGraph const & graph,
std::shared_ptr<TrafficStash> const & trafficStash,
base::Cancellable const & cancellable, std::vector<Junction> const & path,
Route::TTimes && times, Route & route);
/// \brief Converts |edge| to |segment|.
/// \returns Segment() if mwm of |edge| is not alive.
Segment ConvertEdgeToSegment(NumMwmIds const & numMwmIds, Edge const & edge);
/// \brief Fills |times| according to max speed at |graph| and |path|.
void CalculateMaxSpeedTimes(RoadGraphBase const & graph, std::vector<Junction> const & path,
Route::TTimes & times);
/// \brief Checks is edge connected with world graph. Function does BFS while it finds some number
/// of edges,
/// if graph ends before this number is reached then junction is assumed as not connected to the
/// world graph.
template <typename Graph, typename GetVertexByEdgeFn, typename GetOutgoingEdgesFn>
bool CheckGraphConnectivity(typename Graph::Vertex const & start, size_t limit, Graph & graph,
GetVertexByEdgeFn && getVertexByEdgeFn, GetOutgoingEdgesFn && getOutgoingEdgesFn)
{
std::queue<typename Graph::Vertex> q;
q.push(start);
std::set<typename Graph::Vertex> marked;
marked.insert(start);
std::vector<typename Graph::Edge> edges;
while (!q.empty() && marked.size() < limit)
{
auto const u = q.front();
q.pop();
edges.clear();
getOutgoingEdgesFn(graph, u, edges);
for (auto const & edge : edges)
{
auto const & v = getVertexByEdgeFn(edge);
if (marked.count(v) == 0)
{
q.push(v);
marked.insert(v);
}
}
}
return marked.size() >= limit;
}
} // namespace rouing
|
