Line data    Source code

       1             : #include <catch2/catch_test_macros.hpp>
       2             : #include <catch2/matchers/catch_matchers_floating_point.hpp>
       3             : #include <memory>
       4             : 
       5             : #include "Alg/ShortestPath/Dijkstra.hpp"
       6             : #include "Static/Demand.hpp"
       7             : #include "Static/algos/AllOrNothing.hpp"
       8             : #include "Static/supply/BPRNotConvexNetwork.hpp"
       9             : #include "data/SUMO/NetworkTAZ.hpp"
      10             : #include "data/SUMO/TAZ.hpp"
      11             : #include "test/problem/graphs.hpp"
      12             : 
      13             : using namespace std;
      14             : using Catch::Matchers::WithinAbs;
      15             : 
      16             : extern string baseDir;
      17             : extern string benchmarkDir;
      18             : 
      19          14 : void testPath(std::vector<Alg::Graph::Node> expected, Alg::Graph::Path got) {
      20          14 :     if(expected.size() == 0) {
      21           2 :         REQUIRE(1 == got.size());
      22           2 :         REQUIRE(-1 == got.front().id);
      23           2 :         REQUIRE(Alg::Graph::NODE_INVALID == got.front().u);
      24           2 :         REQUIRE(Alg::Graph::NODE_INVALID == got.front().v);
      25           2 :         REQUIRE_THAT(got.front().w, WithinAbs(0, 1e-10));
      26             : 
      27           1 :         return;
      28             :     }
      29          26 :     REQUIRE(got.size() == expected.size() - 1);
      30          13 :     auto itExpected = expected.begin();
      31          13 :     auto itGot      = got.begin();
      32          41 :     for(; itGot != got.end(); ++itExpected, ++itGot) {
      33          28 :         auto itExpectedNext = itExpected;
      34          28 :         ++itExpectedNext;
      35          56 :         REQUIRE(*itExpected == itGot->u);
      36          84 :         REQUIRE(*itExpectedNext == itGot->v);
      37             :     }
      38             : }
      39             : 
      40           5 : TEST_CASE("Dijkstra's algorithm", "[shortestpath][shortestpath-onemany][dijkstra]") {
      41           6 :     SECTION("Start 0") {
      42           2 :         Alg::Graph G = graph1();
      43             : 
      44           1 :         Alg::ShortestPath::ShortestPathOneMany *shortestPath = new Alg::ShortestPath::Dijkstra();
      45           1 :         shortestPath->solve(G, 0);
      46             : 
      47           2 :         testPath({0}, shortestPath->getPath(0));
      48           2 :         testPath({0, 1}, shortestPath->getPath(1));
      49           2 :         testPath({0, 1, 2}, shortestPath->getPath(2));
      50           2 :         testPath({0, 1, 2, 3}, shortestPath->getPath(3));
      51           2 :         testPath({0, 1, 2, 3, 4}, shortestPath->getPath(4));
      52           2 :         testPath({0, 1, 2, 5}, shortestPath->getPath(5));
      53           2 :         testPath({0, 1, 2, 5, 6}, shortestPath->getPath(6));
      54             : 
      55           2 :         REQUIRE_THAT(shortestPath->getPathWeight(0), WithinAbs(0, 1e-10));
      56           2 :         REQUIRE_THAT(shortestPath->getPathWeight(1), WithinAbs(1, 1e-10));
      57           2 :         REQUIRE_THAT(shortestPath->getPathWeight(2), WithinAbs(3, 1e-10));
      58           2 :         REQUIRE_THAT(shortestPath->getPathWeight(3), WithinAbs(4, 1e-10));
      59           2 :         REQUIRE_THAT(shortestPath->getPathWeight(4), WithinAbs(6, 1e-10));
      60           2 :         REQUIRE_THAT(shortestPath->getPathWeight(5), WithinAbs(5, 1e-10));
      61           2 :         REQUIRE_THAT(shortestPath->getPathWeight(6), WithinAbs(9, 1e-10));
      62             : 
      63           1 :         delete shortestPath;
      64             :     }
      65           6 :     SECTION("Start 1") {
      66           2 :         Alg::Graph G = graph1();
      67             : 
      68           1 :         Alg::ShortestPath::ShortestPathOneMany *shortestPath = new Alg::ShortestPath::Dijkstra();
      69           1 :         shortestPath->solve(G, 1);
      70             : 
      71           2 :         testPath({}, shortestPath->getPath(0));
      72           2 :         testPath({1}, shortestPath->getPath(1));
      73           2 :         testPath({1, 2}, shortestPath->getPath(2));
      74           2 :         testPath({1, 2, 3}, shortestPath->getPath(3));
      75           2 :         testPath({1, 2, 3, 4}, shortestPath->getPath(4));
      76           2 :         testPath({1, 2, 5}, shortestPath->getPath(5));
      77           2 :         testPath({1, 2, 5, 6}, shortestPath->getPath(6));
      78             : 
      79           2 :         REQUIRE_THAT(shortestPath->getPathWeight(0), WithinAbs(Alg::Graph::Edge::WEIGHT_INF, 1e-10));
      80           2 :         REQUIRE_THAT(shortestPath->getPathWeight(1), WithinAbs(0, 1e-10));
      81           2 :         REQUIRE_THAT(shortestPath->getPathWeight(2), WithinAbs(2, 1e-10));
      82           2 :         REQUIRE_THAT(shortestPath->getPathWeight(3), WithinAbs(3, 1e-10));
      83           2 :         REQUIRE_THAT(shortestPath->getPathWeight(4), WithinAbs(5, 1e-10));
      84           2 :         REQUIRE_THAT(shortestPath->getPathWeight(5), WithinAbs(4, 1e-10));
      85           2 :         REQUIRE_THAT(shortestPath->getPathWeight(6), WithinAbs(8, 1e-10));
      86             : 
      87           1 :         delete shortestPath;
      88             :     }
      89             : 
      90           6 :     SECTION("crossroads1") {
      91           2 :         shared_ptr<SUMO::Network> sumoNetwork = SUMO::Network::loadFromFile(baseDir + "data/network/crossroads1/crossroads1.net.xml");
      92           2 :         SUMO::TAZs                sumoTAZs;
      93           1 :         SUMO::NetworkTAZs         sumo{*sumoNetwork, sumoTAZs};
      94             : 
      95           2 :         Static::BPRNotConvexNetwork::Loader<SUMO::NetworkTAZs> loader;
      96           1 :         Static::BPRNotConvexNetwork                           *network = loader.load(sumo);
      97             : 
      98             :         // Demand
      99           2 :         Static::Demand demand;
     100             : 
     101           2 :         Static::SolutionBase                               xn;
     102           2 :         Alg::Graph                                         G = network->toGraph(xn);
     103           2 :         unique_ptr<Alg::ShortestPath::ShortestPathOneMany> sp(new Alg::ShortestPath::Dijkstra());
     104           1 :         sp.get()->solve(G, loader.adapter.toNodes("2").first);
     105             : 
     106           1 :         const double RIGHT_TURN = 2.0;
     107           1 :         const double LEFT_TURN  = 5.0;
     108             : 
     109           1 :         const double v1 = 13.89, l1 = 14.07;
     110           1 :         const double v2 = 8.33, l2 = 18.80;
     111           1 :         const double v3 = 13.89, l3 = 33.24;
     112           1 :         const double v4 = 8.33, l4 = 39.34;
     113           1 :         const double t1 = l1 / (v1 * 0.9);
     114           1 :         const double t2 = l2 / (v2 * 0.9);
     115           1 :         const double t3 = l3 / (v3 * 0.9);
     116           1 :         const double t4 = l4 / (v4 * 0.9);
     117             : 
     118           1 :         const double r1 = 60.0;
     119             :         // const double r2 = 30.0;
     120           1 :         const double C = 90.0;
     121             : 
     122           1 :         const double t21 = r1 * r1 / (2.0 * C);
     123           1 :         const double t23 = r1 * r1 / (2.0 * C);
     124           1 :         const double t24 = r1 * r1 / (2.0 * C);
     125             : 
     126           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("2").first), WithinAbs(0, 1e-6));
     127           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("2").second), WithinAbs(t2, 1e-6));
     128             : 
     129           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("-1").first), WithinAbs(t2 + t21 + RIGHT_TURN, 1e-6));
     130           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("-1").second), WithinAbs(t2 + t21 + RIGHT_TURN + t1, 1e-6));
     131             : 
     132           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("-4").first), WithinAbs(t2 + t24, 1e-6));
     133           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("-4").second), WithinAbs(t2 + t24 + t4, 1e-6));
     134             : 
     135           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("-3").first), WithinAbs(t2 + t23 + LEFT_TURN, 1e-6));
     136           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("-3").second), WithinAbs(t2 + t23 + LEFT_TURN + t3, 1e-6));
     137             : 
     138           1 :         delete network;
     139             :     }
     140             : 
     141           6 :     SECTION("crossroads2") {
     142           2 :         shared_ptr<SUMO::Network> sumoNetwork = SUMO::Network::loadFromFile(baseDir + "data/network/crossroads2/crossroads2.net.xml");
     143           2 :         SUMO::TAZs                sumoTAZs;
     144           1 :         SUMO::NetworkTAZs         sumo{*sumoNetwork, sumoTAZs};
     145             : 
     146           2 :         Static::BPRNotConvexNetwork::Loader<SUMO::NetworkTAZs> loader;
     147           1 :         Static::BPRNotConvexNetwork                           *network = loader.load(sumo);
     148             : 
     149             :         // Demand
     150           2 :         Static::Demand demand;
     151             : 
     152           2 :         Static::SolutionBase                               xn;
     153           2 :         Alg::Graph                                         G = network->toGraph(xn);
     154           2 :         unique_ptr<Alg::ShortestPath::ShortestPathOneMany> sp(new Alg::ShortestPath::Dijkstra());
     155           1 :         sp.get()->solve(G, loader.adapter.toNodes("2").first);
     156             : 
     157           1 :         const double RIGHT_TURN = 2.0;
     158             :         // const double LEFT_TURN   = 5.0;
     159           1 :         const double TURN_AROUND = 20;
     160             : 
     161           1 :         const double v1 = 13.89, l1 = 14.07;
     162           1 :         const double v2 = 8.33, l2 = 18.80;
     163           1 :         const double v3 = 13.89, l3 = 33.24;
     164           1 :         const double v4 = 8.33, l4 = 39.34;
     165           1 :         const double t1 = l1 / (v1 * 0.9);
     166           1 :         const double t2 = l2 / (v2 * 0.9);
     167           1 :         const double t3 = l3 / (v3 * 0.9);
     168           1 :         const double t4 = l4 / (v4 * 0.9);
     169             : 
     170           1 :         const double r1 = 60.0;
     171           1 :         const double r2 = 30.0;
     172           1 :         const double C  = 90.0;
     173             : 
     174           1 :         const double t21 = r1 * r1 / (2.0 * C);
     175             :         // const double t23 = r1 * r1 / (2.0 * C);
     176           1 :         const double t24 = r1 * r1 / (2.0 * C);
     177             : 
     178           1 :         const double t13 = r2 * r2 / (2.0 * C);
     179             : 
     180           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("2").first), WithinAbs(0, 1e-6));
     181           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("2").second), WithinAbs(t2, 1e-6));
     182             : 
     183           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("-1").first), WithinAbs(t2 + t21 + RIGHT_TURN, 1e-6));
     184           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("-1").second), WithinAbs(t2 + t21 + RIGHT_TURN + t1, 1e-6));
     185             : 
     186           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("1").first), WithinAbs(t2 + t21 + RIGHT_TURN + t1 + TURN_AROUND, 1e-6));
     187           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("1").second), WithinAbs(t2 + t21 + RIGHT_TURN + t1 + TURN_AROUND + t1, 1e-6));
     188             : 
     189           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("-3").first), WithinAbs(t2 + t21 + RIGHT_TURN + t1 + TURN_AROUND + t1 + t13, 1e-6));
     190           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("-3").second), WithinAbs(t2 + t21 + RIGHT_TURN + t1 + TURN_AROUND + t1 + t13 + t3, 1e-6));
     191             : 
     192           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("3").first), WithinAbs(t2 + t21 + RIGHT_TURN + t1 + TURN_AROUND + t1 + t13 + t3 + TURN_AROUND, 1e-6));
     193           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("3").second), WithinAbs(t2 + t21 + RIGHT_TURN + t1 + TURN_AROUND + t1 + t13 + t3 + TURN_AROUND + t3, 1e-6));
     194             : 
     195           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("-4").first), WithinAbs(t2 + t24, 1e-6));
     196           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("-4").second), WithinAbs(t2 + t24 + t4, 1e-6));
     197             : 
     198           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("4").first), WithinAbs(t2 + t24 + t4 + TURN_AROUND, 1e-6));
     199           2 :         REQUIRE_THAT(sp.get()->getPathWeight(loader.adapter.toNodes("4").second), WithinAbs(t2 + t24 + t4 + TURN_AROUND + t4, 1e-6));
     200             : 
     201           1 :         delete network;
     202             :     }
     203             : 
     204           6 :     SECTION("Large") {
     205           2 :         shared_ptr<SUMO::Network> sumoNetwork = SUMO::Network::loadFromFile(benchmarkDir + "data/dynaminator-data/porto-armis.net.xml");
     206           2 :         SUMO::TAZs                sumoTAZs    = SUMO::TAZ::loadFromFile(benchmarkDir + "data/dynaminator-data/porto-armis.taz.xml");
     207           1 :         SUMO::NetworkTAZs         sumo{*sumoNetwork, sumoTAZs};
     208             : 
     209           2 :         Static::BPRNotConvexNetwork::Loader<SUMO::NetworkTAZs> loader;
     210           1 :         Static::BPRNotConvexNetwork                           *network = loader.load(sumo);
     211             : 
     212             :         // Demand
     213           2 :         VISUM::OFormatDemand oDemand = VISUM::OFormatDemand::loadFromFile(benchmarkDir + "data/dynaminator-data/matrix.9.0.10.0.2.fma");
     214             : 
     215           1 :         Static::Demand::Loader<const VISUM::OFormatDemand &, const Static::SUMOAdapter &> demandLoader;
     216             : 
     217           2 :         Static::Demand demand = demandLoader.load(oDemand, loader.adapter);
     218             : 
     219           2 :         Static::SolutionBase                               xn;
     220           2 :         Alg::Graph                                         G = network->toGraph(xn);
     221           2 :         unique_ptr<Alg::ShortestPath::ShortestPathOneMany> sp(new Alg::ShortestPath::Dijkstra());
     222           1 :         sp.get()->solve(G, 4455);
     223             : 
     224           2 :         REQUIRE(sp.get()->getPrev(2952).u != -1);
     225           2 :         REQUIRE(sp.get()->getPrev(4252).u != -1);
     226             : 
     227           1 :         delete network;
     228             :     }
     229           5 : }