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
|
#pragma once
#include "routing/base/astar_algorithm.hpp"
#include "routing/base/routing_result.hpp"
#include "routing/road_graph.hpp"
#include "routing/router.hpp"
#include <cstdint>
#include <map>
#include <string>
namespace routing_test
{
using namespace routing;
struct SimpleEdge
{
SimpleEdge(uint32_t to, double weight) : m_to(to), m_weight(weight) {}
uint32_t GetTarget() const { return m_to; }
double GetWeight() const { return m_weight; }
uint32_t m_to;
double m_weight;
};
class UndirectedGraph : public AStarGraph<uint32_t, SimpleEdge, double>
{
public:
void AddEdge(Vertex u, Vertex v, Weight w);
size_t GetNodesNumber() const;
// AStarGraph overrides
// @{
void GetIngoingEdgesList(Vertex const & v, std::vector<Edge> & adj) override;
void GetOutgoingEdgesList(Vertex const & v, std::vector<Edge> & adj) override;
double HeuristicCostEstimate(Vertex const & v, Vertex const & w) override;
// @}
private:
void GetAdjacencyList(Vertex v, std::vector<Edge> & adj) const;
std::map<uint32_t, std::vector<Edge>> m_adjs;
};
class DirectedGraph
{
public:
using Vertex = uint32_t;
using Edge = SimpleEdge;
using Weight = double;
void AddEdge(Vertex from, Vertex to, Weight w);
void GetIngoingEdgesList(Vertex const & v, std::vector<Edge> & adj);
void GetOutgoingEdgesList(Vertex const & v, std::vector<Edge> & adj);
private:
std::map<uint32_t, std::vector<Edge>> m_outgoing;
std::map<uint32_t, std::vector<Edge>> m_ingoing;
};
} // namespace routing_tests
namespace routing
{
class TestAStarBidirectionalAlgo
{
public:
enum class Result
{
OK,
NoPath,
Cancelled
};
Result CalculateRoute(IRoadGraph const & graph, Junction const & startPos,
Junction const & finalPos,
RoutingResult<IRoadGraph::Vertex, IRoadGraph::Weight> & path);
};
std::string DebugPrint(TestAStarBidirectionalAlgo::Result const & result);
} // namespace routing
|