FM / util

/srv/osrm/osrm-backend/unit_tests/util

Name	Size	Mode	Actions
bearing.cpp	3104	0644	edit dl rm
bit_range.cpp	2772	0644	edit dl rm
conditional_restrictions_parsing.cpp	1497	0644	edit dl rm
connectivity_checksum.cpp	2498	0644	edit dl rm
coordinate_calculation.cpp	18815	0644	edit dl rm
duration_parsing.cpp	3052	0644	edit dl rm
dynamic_graph.cpp	5277	0644	edit dl rm
filtered_integer_range.cpp	1338	0644	edit dl rm
group_by.cpp	1476	0644	edit dl rm
hilbert_values.cpp	3896	0644	edit dl rm
indexed_data.cpp	5589	0644	edit dl rm
io.cpp	6850	0644	edit dl rm
json_render.cpp	2149	0644	edit dl rm
opening_hours_parsing.cpp	18764	0644	edit dl rm
packed_vector.cpp	9606	0644	edit dl rm
permutation.cpp	792	0644	edit dl rm
query_heap.cpp	4043	0644	edit dl rm
range_table.cpp	3146	0644	edit dl rm
rectangle.cpp	6923	0644	edit dl rm
serialization.cpp	4303	0644	edit dl rm
static_graph.cpp	6655	0644	edit dl rm
static_rtree.cpp	19478	0644	edit dl rm
string_util.cpp	1157	0644	edit dl rm
vector_view.cpp	1929	0644	edit dl rm
viewport.cpp	571	0644	edit dl rm
web_mercator.cpp	2975	0644	edit dl rm

Edit: /srv/osrm/osrm-backend/unit_tests/util/dynamic_graph.cpp (5277B)

#include "util/dynamic_graph.hpp"
#include "util/typedefs.hpp"

#include "../common/range_tools.hpp"

#include <boost/test/unit_test.hpp>

#include <vector>

BOOST_AUTO_TEST_SUITE(dynamic_graph)

using namespace osrm;
using namespace osrm::util;

struct TestData
{
    EdgeID id;
};

using TestDynamicGraph = DynamicGraph<TestData>;
using TestInputEdge = TestDynamicGraph::InputEdge;

BOOST_AUTO_TEST_CASE(find_test)
{
    /*
     *  (0) -1-> (1)
     *  ^ ^
     *  2 5
     *  | |
     *  (3) -3-> (4)
     *      <-4-
     */
    std::vector<TestInputEdge> input_edges = {TestInputEdge{0, 1, TestData{1}},
                                              TestInputEdge{3, 0, TestData{2}},
                                              TestInputEdge{3, 0, TestData{5}},
                                              TestInputEdge{3, 4, TestData{3}},
                                              TestInputEdge{4, 3, TestData{4}}};
    TestDynamicGraph simple_graph(5, input_edges);

auto eit = simple_graph.FindEdge(0, 1);
    BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 1);

eit = simple_graph.FindEdge(1, 0);
    BOOST_CHECK_EQUAL(eit, SPECIAL_EDGEID);

eit = simple_graph.FindEdgeInEitherDirection(1, 0);
    BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 1);

bool reverse = false;
    eit = simple_graph.FindEdgeIndicateIfReverse(1, 0, reverse);
    BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 1);
    BOOST_CHECK(reverse);

eit = simple_graph.FindEdge(3, 1);
    BOOST_CHECK_EQUAL(eit, SPECIAL_EDGEID);
    eit = simple_graph.FindEdge(0, 4);
    BOOST_CHECK_EQUAL(eit, SPECIAL_EDGEID);

eit = simple_graph.FindEdge(3, 4);
    BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 3);
    eit = simple_graph.FindEdgeInEitherDirection(3, 4);
    BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 3);

eit = simple_graph.FindEdge(3, 0);
    BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 2);
}

BOOST_AUTO_TEST_CASE(renumber_test)
{
    /*
     *  (0) -1-> (1)
     *  ^ ^
     *  2 5
     *  | |
     *  (3) -3-> (4)
     *      <-4-
     */
    std::vector<TestInputEdge> input_edges = {TestInputEdge{0, 1, TestData{1}},
                                              TestInputEdge{3, 0, TestData{2}},
                                              TestInputEdge{3, 0, TestData{5}},
                                              TestInputEdge{3, 4, TestData{3}},
                                              TestInputEdge{4, 3, TestData{4}}};
    TestDynamicGraph simple_graph(5, input_edges);

/*
     *  (1) -1-> (3)
     *  ^ ^
     *  2 5
     *  | |
     *  (0) -3-> (2)
     *      <-4-
     */
    simple_graph.Renumber({1, 3, 4, 0, 2});

auto eit = simple_graph.FindEdge(1, 3);
    BOOST_CHECK(eit != SPECIAL_EDGEID);
    BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 1);

eit = simple_graph.FindEdge(3, 1);
    BOOST_CHECK_EQUAL(eit, SPECIAL_EDGEID);

eit = simple_graph.FindEdgeInEitherDirection(3, 1);
    BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 1);

bool reverse = false;
    eit = simple_graph.FindEdgeIndicateIfReverse(3, 1, reverse);
    BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 1);
    BOOST_CHECK(reverse);

eit = simple_graph.FindEdge(0, 3);
    BOOST_CHECK_EQUAL(eit, SPECIAL_EDGEID);
    eit = simple_graph.FindEdge(1, 2);
    BOOST_CHECK_EQUAL(eit, SPECIAL_EDGEID);

eit = simple_graph.FindEdge(0, 2);
    BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 3);
    eit = simple_graph.FindEdgeInEitherDirection(0, 2);
    BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 3);

eit = simple_graph.FindEdge(0, 1);
    BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 2);
}

BOOST_AUTO_TEST_CASE(filter_test)
{
    /*
     *  (0) -1-> (1)
     *  ^ ^       ^
     *  2 5       1
     *  | |       |
     *  (3) -3-> (4)
     *      <-4-
     */
    std::vector<TestInputEdge> input_edges = {TestInputEdge{0, 1, TestData{1}},
                                              TestInputEdge{3, 0, TestData{2}},
                                              TestInputEdge{3, 0, TestData{5}},
                                              TestInputEdge{3, 4, TestData{3}},
                                              TestInputEdge{4, 1, TestData{1}},
                                              TestInputEdge{4, 3, TestData{4}}};
    TestDynamicGraph simple_graph(5, input_edges);

// only keep 0, 1, 4 -> filter out all edges from/to 3
    auto filtered_simple_graph =
        simple_graph.Filter([](const NodeID node) { return node == 0 || node == 1 || node == 4; });

REQUIRE_SIZE_RANGE(filtered_simple_graph.GetAdjacentEdgeRange(0), 1);
    CHECK_EQUAL_RANGE(filtered_simple_graph.GetAdjacentEdgeRange(0),
                      filtered_simple_graph.FindEdge(0, 1));

REQUIRE_SIZE_RANGE(filtered_simple_graph.GetAdjacentEdgeRange(1), 0);

REQUIRE_SIZE_RANGE(filtered_simple_graph.GetAdjacentEdgeRange(2), 0);

REQUIRE_SIZE_RANGE(filtered_simple_graph.GetAdjacentEdgeRange(3), 0);

REQUIRE_SIZE_RANGE(filtered_simple_graph.GetAdjacentEdgeRange(4), 1);
    CHECK_EQUAL_RANGE(filtered_simple_graph.GetAdjacentEdgeRange(4),
                      filtered_simple_graph.FindEdge(4, 1));
}

BOOST_AUTO_TEST_SUITE_END()

#include "util/dynamic_graph.hpp" #include "util/typedefs.hpp" #include "../common/range_tools.hpp" #include #include BOOST_AUTO_TEST_SUITE(dynamic_graph) using namespace osrm; using namespace osrm::util; struct TestData { EdgeID id; }; using TestDynamicGraph = DynamicGraph; using TestInputEdge = TestDynamicGraph::InputEdge; BOOST_AUTO_TEST_CASE(find_test) { /* * (0) -1-> (1) * ^ ^ * 2 5 * | | * (3) -3-> (4) * <-4- */ std::vector input_edges = {TestInputEdge{0, 1, TestData{1}}, TestInputEdge{3, 0, TestData{2}}, TestInputEdge{3, 0, TestData{5}}, TestInputEdge{3, 4, TestData{3}}, TestInputEdge{4, 3, TestData{4}}}; TestDynamicGraph simple_graph(5, input_edges); auto eit = simple_graph.FindEdge(0, 1); BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 1); eit = simple_graph.FindEdge(1, 0); BOOST_CHECK_EQUAL(eit, SPECIAL_EDGEID); eit = simple_graph.FindEdgeInEitherDirection(1, 0); BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 1); bool reverse = false; eit = simple_graph.FindEdgeIndicateIfReverse(1, 0, reverse); BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 1); BOOST_CHECK(reverse); eit = simple_graph.FindEdge(3, 1); BOOST_CHECK_EQUAL(eit, SPECIAL_EDGEID); eit = simple_graph.FindEdge(0, 4); BOOST_CHECK_EQUAL(eit, SPECIAL_EDGEID); eit = simple_graph.FindEdge(3, 4); BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 3); eit = simple_graph.FindEdgeInEitherDirection(3, 4); BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 3); eit = simple_graph.FindEdge(3, 0); BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 2); } BOOST_AUTO_TEST_CASE(renumber_test) { /* * (0) -1-> (1) * ^ ^ * 2 5 * | | * (3) -3-> (4) * <-4- */ std::vector input_edges = {TestInputEdge{0, 1, TestData{1}}, TestInputEdge{3, 0, TestData{2}}, TestInputEdge{3, 0, TestData{5}}, TestInputEdge{3, 4, TestData{3}}, TestInputEdge{4, 3, TestData{4}}}; TestDynamicGraph simple_graph(5, input_edges); /* * (1) -1-> (3) * ^ ^ * 2 5 * | | * (0) -3-> (2) * <-4- */ simple_graph.Renumber({1, 3, 4, 0, 2}); auto eit = simple_graph.FindEdge(1, 3); BOOST_CHECK(eit != SPECIAL_EDGEID); BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 1); eit = simple_graph.FindEdge(3, 1); BOOST_CHECK_EQUAL(eit, SPECIAL_EDGEID); eit = simple_graph.FindEdgeInEitherDirection(3, 1); BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 1); bool reverse = false; eit = simple_graph.FindEdgeIndicateIfReverse(3, 1, reverse); BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 1); BOOST_CHECK(reverse); eit = simple_graph.FindEdge(0, 3); BOOST_CHECK_EQUAL(eit, SPECIAL_EDGEID); eit = simple_graph.FindEdge(1, 2); BOOST_CHECK_EQUAL(eit, SPECIAL_EDGEID); eit = simple_graph.FindEdge(0, 2); BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 3); eit = simple_graph.FindEdgeInEitherDirection(0, 2); BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 3); eit = simple_graph.FindEdge(0, 1); BOOST_CHECK_EQUAL(simple_graph.GetEdgeData(eit).id, 2); } BOOST_AUTO_TEST_CASE(filter_test) { /* * (0) -1-> (1) * ^ ^ ^ * 2 5 1 * | | | * (3) -3-> (4) * <-4- */ std::vector input_edges = {TestInputEdge{0, 1, TestData{1}}, TestInputEdge{3, 0, TestData{2}}, TestInputEdge{3, 0, TestData{5}}, TestInputEdge{3, 4, TestData{3}}, TestInputEdge{4, 1, TestData{1}}, TestInputEdge{4, 3, TestData{4}}}; TestDynamicGraph simple_graph(5, input_edges); // only keep 0, 1, 4 -> filter out all edges from/to 3 auto filtered_simple_graph = simple_graph.Filter([](const NodeID node) { return node == 0 || node == 1 || node == 4; }); REQUIRE_SIZE_RANGE(filtered_simple_graph.GetAdjacentEdgeRange(0), 1); CHECK_EQUAL_RANGE(filtered_simple_graph.GetAdjacentEdgeRange(0), filtered_simple_graph.FindEdge(0, 1)); REQUIRE_SIZE_RANGE(filtered_simple_graph.GetAdjacentEdgeRange(1), 0); REQUIRE_SIZE_RANGE(filtered_simple_graph.GetAdjacentEdgeRange(2), 0); REQUIRE_SIZE_RANGE(filtered_simple_graph.GetAdjacentEdgeRange(3), 0); REQUIRE_SIZE_RANGE(filtered_simple_graph.GetAdjacentEdgeRange(4), 1); CHECK_EQUAL_RANGE(filtered_simple_graph.GetAdjacentEdgeRange(4), filtered_simple_graph.FindEdge(4, 1)); } BOOST_AUTO_TEST_SUITE_END()