diff options
author | Mikhail Gorbushin <m.gorbushin@corp.mail.ru> | 2019-04-30 15:45:42 +0300 |
---|---|---|
committer | Vladimir Byko-Ianko <bykoianko@gmail.com> | 2019-05-24 17:29:38 +0300 |
commit | 8e27a78819854ec87c34970782f865a3e77da902 (patch) | |
tree | 194b98a2c18bc20f2b0b8251490fe4522c188796 /routing | |
parent | 57e8186b5a325a7592cb699c2a301d633053b155 (diff) |
Stage 4. Add BFS tests.
Diffstat (limited to 'routing')
-rw-r--r-- | routing/routing_tests/CMakeLists.txt | 1 | ||||
-rw-r--r-- | routing/routing_tests/bfs_tests.cpp | 176 |
2 files changed, 177 insertions, 0 deletions
diff --git a/routing/routing_tests/CMakeLists.txt b/routing/routing_tests/CMakeLists.txt index 39a8e816ff..de02f8995d 100644 --- a/routing/routing_tests/CMakeLists.txt +++ b/routing/routing_tests/CMakeLists.txt @@ -7,6 +7,7 @@ set( astar_progress_test.cpp astar_router_test.cpp async_router_test.cpp + bfs_tests.cpp checkpoint_predictor_test.cpp coding_test.cpp cross_mwm_connector_test.cpp diff --git a/routing/routing_tests/bfs_tests.cpp b/routing/routing_tests/bfs_tests.cpp new file mode 100644 index 0000000000..625d3d2eb6 --- /dev/null +++ b/routing/routing_tests/bfs_tests.cpp @@ -0,0 +1,176 @@ +#include "testing/testing.hpp" + +#include "routing/base/bfs.hpp" + +#include "routing/routing_tests/routing_algorithm.hpp" + +#include <cstdint> +#include <set> + +namespace +{ +using namespace routing_test; + +double constexpr kWeight = 1.0; + +UndirectedGraph BuildUndirectedGraph() +{ + UndirectedGraph graph; + + // Inserts edges in a format: <source, target, weight>. + graph.AddEdge(0, 4, kWeight); + graph.AddEdge(5, 4, kWeight); + graph.AddEdge(4, 1, kWeight); + graph.AddEdge(4, 3, kWeight); + graph.AddEdge(3, 2, kWeight); + graph.AddEdge(7, 4, kWeight); + graph.AddEdge(7, 6, kWeight); + graph.AddEdge(7, 8, kWeight); + graph.AddEdge(8, 9, kWeight); + graph.AddEdge(8, 10, kWeight); + + return graph; +} + +DirectedGraph BuildDirectedGraph() +{ + DirectedGraph graph; + + // Inserts edges in a format: <source, target, weight>. + graph.AddEdge(0, 4, kWeight); + graph.AddEdge(5, 4, kWeight); + graph.AddEdge(4, 1, kWeight); + graph.AddEdge(4, 3, kWeight); + graph.AddEdge(3, 2, kWeight); + graph.AddEdge(7, 4, kWeight); + graph.AddEdge(7, 6, kWeight); + graph.AddEdge(7, 8, kWeight); + graph.AddEdge(8, 9, kWeight); + graph.AddEdge(8, 10, kWeight); + + return graph; +} + +DirectedGraph BuildDirectedCyclicGraph() +{ + DirectedGraph graph; + + // Inserts edges in a format: <source, target, weight>. + graph.AddEdge(0, 1, kWeight); + graph.AddEdge(1, 2, kWeight); + graph.AddEdge(2, 3, kWeight); + graph.AddEdge(3, 4, kWeight); + graph.AddEdge(4, 2, kWeight); + + return graph; +} + +DirectedGraph BuildSmallDirectedCyclicGraph() +{ + DirectedGraph graph; + + // Inserts edges in a format: <source, target, weight>. + graph.AddEdge(0, 1, kWeight); + graph.AddEdge(1, 2, kWeight); + graph.AddEdge(2, 0, kWeight); + + return graph; +} +} // namespace + +namespace routing_test +{ +using namespace routing; + +UNIT_TEST(BFS_AllVisit_Undirected) +{ + UndirectedGraph graph = BuildUndirectedGraph(); + + std::set<uint32_t> visited; + + BFS<UndirectedGraph> bfs(graph); + bfs.Run(0 /* start */, true /* isOutgoing */, + [&](BFS<UndirectedGraph>::State const & state) + { + visited.emplace(state.m_vertex); + return true; + }); + + std::vector<uint32_t> const expectedInVisited = {1, 2, 3, 4 ,5, 6, 7, 8, 9, 10}; + for (auto const v : expectedInVisited) + TEST_NOT_EQUAL(visited.count(v), 0, ("vertex =", v, "was not visited.")); +} + +UNIT_TEST(BFS_AllVisit_Directed_Forward) +{ + DirectedGraph graph = BuildDirectedGraph(); + + std::set<uint32_t> visited; + + BFS<DirectedGraph> bfs(graph); + bfs.Run(0 /* start */, true /* isOutgoing */, + [&](BFS<DirectedGraph>::State const & state) + { + visited.emplace(state.m_vertex); + return true; + }); + + std::vector<uint32_t> const expectedInVisited = {1, 2, 3, 4}; + for (auto const v : expectedInVisited) + TEST_NOT_EQUAL(visited.count(v), 0, ("vertex =", v, "was not visited.")); +} + +UNIT_TEST(BFS_AllVisit_Directed_Backward) +{ + DirectedGraph graph = BuildDirectedGraph(); + + std::set<uint32_t> visited; + + BFS<DirectedGraph> bfs(graph); + bfs.Run(2 /* start */, false /* isOutgoing */, + [&](BFS<DirectedGraph>::State const & state) + { + visited.emplace(state.m_vertex); + return true; + }); + + std::vector<uint32_t> expectedInVisited = {0, 3, 4, 5, 7}; + for (auto const v : expectedInVisited) + TEST_NOT_EQUAL(visited.count(v), 0, ("vertex =", v, "was not visited.")); +} + +UNIT_TEST(BFS_AllVisit_DirectedCyclic) +{ + DirectedGraph graph = BuildDirectedCyclicGraph(); + + std::set<uint32_t> visited; + + BFS<DirectedGraph> bfs(graph); + bfs.Run(0 /* start */, true /* isOutgoing */, + [&](BFS<DirectedGraph>::State const & state) + { + visited.emplace(state.m_vertex); + return true; + }); + + std::vector<uint32_t> expectedInVisited = {1, 2, 3, 4}; + for (auto const v : expectedInVisited) + TEST_NOT_EQUAL(visited.count(v), 0, ("vertex =", v, "was not visited.")); +} + +UNIT_TEST(BFS_ReconstructPathTest) +{ + DirectedGraph graph = BuildSmallDirectedCyclicGraph(); + + BFS<DirectedGraph> bfs(graph); + bfs.Run(0 /* start */, true /* isOutgoing */, [&](auto const & state) { return true; }); + + std::vector<uint32_t> path = bfs.ReconstructPath(2, false /* reverse */); + std::vector<uint32_t> expected = {0, 1, 2}; + TEST_EQUAL(path, expected, ()); + + path = bfs.ReconstructPath(2, true /* reverse */); + expected = {2, 1, 0}; + TEST_EQUAL(path, expected, ()); +} +} // namespace routing_test |