Skip to content
Snippets Groups Projects

JPS Graph algorithm

    • Open Issue created by Tomáš Pecka @peckato1 
    13/37 Test #14: alib2graph_algo ........................................***Failed    0.06 sec
GraphFordFulkersonTest::runTests:
testing network #1
testing network #2
testing network #3
testing network #4
testing network #5
testing network #7
testing network #8
Result (GraphFordFulkersonTest::runTests) : OK

GraphFordFulkersonCutTest::runTests:
testing network #1
testing network #2
testing network #3
testing network #4
testing network #5
testing network #6
testing network #7
testing network #8
Result (GraphFordFulkersonCutTest::runTests) : OK

ShortestPathTest::testBFSGraph:
Result (ShortestPathTest::testBFSGraph) : OK

ShortestPathTest::testIDDFSGraph:
Result (ShortestPathTest::testIDDFSGraph) : OK

ShortestPathTest::testDijkstraGraph:
Result (ShortestPathTest::testDijkstraGraph) : OK

ShortestPathTest::testBFSGrid:
Result (ShortestPathTest::testBFSGrid) : OK

ShortestPathTest::testDijkstraGrid:
Result (ShortestPathTest::testDijkstraGrid) : OK

ShortestPathTest::testAStarGrid:
Result (ShortestPathTest::testAStarGrid) : OK

ShortestPathTest::testAllNonGridAlgorithm:
Result (ShortestPathTest::testAllNonGridAlgorithm) : OK

ShortestPathTest::testAllGridAlgorithm:
Result (ShortestPathTest::testAllGridAlgorithm) : OK

ShortestPathTest::testAllGridAlgorithmRandom:
assertion : ShortestPathTest::testAllGridAlgorithmRandom : 406
Exception - Expression: fabs(jps.second - mm.second) < EPS
Result (ShortestPathTest::testAllGridAlgorithmRandom) : Fail

Overal result: Tests: 11 Assertions: 1 Failures: 0

    Opravit a zároveň přepsat tyhle eps porovnání do Catch2 Approx. Další relativní porovnání je tuším v measure

    Edited
    To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information

    Child items ...

    • Activity

    • Tomáš Pecka mentioned in merge request !62 (merged)

      mentioned in merge request !62 (merged)

    • Tomáš Pecka
      Tomáš Pecka @peckato1 ·
      Author Owner 
      test-alib2graph_algo is a Catch v2.6.1 host application.
Run with -? for options

-------------------------------------------------------------------------------
Shortest Path
  All Grid Random
-------------------------------------------------------------------------------
/media/data/zdrojaky/alt/automata-library/alib2graph_algo/test-src/shortest_path/ShortestPathTest.cpp:354
...............................................................................

/media/data/zdrojaky/alt/automata-library/alib2graph_algo/test-src/shortest_path/ShortestPathTest.cpp:387: FAILED:
  CHECK( fabs(jps.second - mm.second) < EPS )
with expansion:
  0.8284271247 < 0.000001
with messages:
  dijkstra.second := 40.2426406871
  dijkstraBi.second := 40.2426406871
  bellmanFord.second := 40.2426406871
  spfa.second := 40.2426406871
  astar.second := 40.2426406871
  astarBi.second := 40.2426406871
  jps.second := 41.0710678119
  mm.second := 40.2426406871

===============================================================================
test cases:   3 |   2 passed | 1 failed
assertions: 103 | 102 passed | 1 failed

      problem je v graph::shortest_path::JPS::findPath

    • Jan Trávníček
      Jan Trávníček @travnja3 ·
      Owner

      Můžeme v případě chyby vypisovat vstup algoritmům? Pošleme bug report Honzovi Uhlíkovi:-)

    • Tomáš Pecka
      Tomáš Pecka @peckato1 ·
      Author Owner

      No staci kamkoliv do scope toho testu pridat INFO("nejaky text s dvojkou " << 2); nebo CAPTURE(expr1==expr2, expr3, foo.bar()) a pokud neprojde pristi REQUIRE nebo CHECK, tak to vypise.

      Ten vypis zezhora je prave tim, ze jsem pred ty CHECK makra pridal CAPTURE(dijkstra.second, dijkstraBi.second, bellmanFord.second, spfa.second, astar.second, astarBi.second, jps.second, mm.second);

      Edited by Tomáš Pecka
    • Tomáš Pecka
      Tomáš Pecka @peckato1 ·
      Author Owner

      cc @uhlikja2

      /media/data/zdrojaky/alt/automata-library/alib2graph_algo/test-src/shortest_path/ShortestPathTest.cpp:388: FAILED:
  CHECK( fabs(jps.second - mm.second) < EPS )
with expansion:
  0.8284271247 < 0.000001
with messages:
  graph := (WeightedSquareGrid8
  +
  —————————————————————————�-
  ��————————————————————————+
  |...........#...................#....#..#..........|
  |..........................#.............#.........|
  |.............................#....................|
  |....#............#.....................#..........|
  |......................#...........................|
  |...........#.......##.............................|
  |..........#.......................#...............|
  |...................................#..............|
  |..........#.......................................|
  |......................#...........................|
  |...............................................#..|
  |...........................................#......|
  |................#.......#......#....#.............|
  |............#....................#......#.........|
  |...........#.......#.......#..#...............#...|
  |..................................................|
  |..................................................|
  |.............................#....................|
  |.......#..........................................|
  |........................................#.........|
  |..................................................|
  |.#.....................#..........................|
  |....#.............#...............#.......#.......|
  |..................................................|
  |.....#............................................|
  |.#............#......................#............|
  |...................................#..............|
  |..#............................#..#...............|
  |...........................#...................#.#|
  |...........................................#......|
  |..............#..............#.........#..........|
  |..........................#.......................|
  |......................................#...........|
  |#...........................#.....................|
  |....................................#.............|
  |..................................................|
  |..............................#...................|
  |.##............................#..................|
  |.................#..............................#.|
  |...........#............................#.........|
  |......................#........#..................|
  |...................#...........#...............#..|
  |..................................#...............|
  |.............#............................#....#..|
  |...........#.........#.......#...........#........|
  |...............#...............#..........#.......|
  |................#.......#...........#...........#.|
  |...............................#.............#....|
  |...................................#..............|
  |..................................#...............|
  +
  —————————————————————————�-
  ��————————————————————————+
  )
  start := (20, 16)
  goal := (11, 47)
  dijkstra.second := 34.7279220614
  dijkstraBi.second := 34.7279220614
  bellmanFord.second := 34.7279220614
  spfa.second := 34.7279220614
  astar.second := 34.7279220614
  astarBi.second := 34.7279220614
  jps.second := 35.5563491861
  mm.second := 34.7279220614

===============================================================================
    • Jan Uhlík
      Jan Uhlík @uhlikja2 ·
      Contributor

      Po kratkem hledani jsem nasel chybu v algoritmu pro generovani gridu. Ve zkratce: pri generovani se muze stat, ze pocatecni/koncovy vrchol bude oznacen zaroven jako prekazka. Vysledek nasledneho hledani nedokazu z hlavy urcit a stalo by to za vyzkouseni. Jestli je toto jedina chyba, ktera zpusobuje ze algoritmus JPS naleza v nekterych pripadech spatnou nejkratsi cestu netusim. Zkusim si na to v prubehu pristiho tydne najit cas (uz takhle mi trvalo asi 3 hodiny zkompilovat celou knihovnu :D ) a problem vyresit. Poslu pak merge request.

    • Tomáš Pecka changed the description

      changed the description

    • Jan Uhlík
      Jan Uhlík @uhlikja2 ·
      Contributor

      Tak problém je skutečně v samotné implementaci algoritmu JPS. Bohužel, teď nemám čas algoritmus znovu nastudovat a najít chybu v implementaci. Budu se na to snažit vyšetřit nějaký čas, ale dříve jak na konci semestru to nevidím. Zatím jsem opravil a poslal merge request na generování náhodného grafu viz. !69 (merged).

      Zde přikládám nalezené cesty, kde j označuje Jump Point:

      +——————————————————————————————————————————————————+
|...........#...................#....#..#..........|
|..........................#.............#.........|
|.............................#....................|
|....#............#.....................#..........|
|......................#...........................|
|...........#.......##.............................|
|..........#.......................#...............|
|...................................#..............|
|..........#.......................................|
|......................#...........................|
|...............................................#..|
|...........................................#...x..|
|................#.......#......#....#......xxxx...|
|............#....................#......#.x.......|
|...........#.......#.......#..#xxxxxxxxxxx....#...|
|..............................x...................|
|.............................x....................|
|......................xxxxxxx#....................|
|.......#.............x............................|
|.................xxxx...................#.........|
|................x.................................|
|.#.....................#..........................|
|....#.............#...............#.......#.......|
|..................................................|
|.....#............................................|
|.#............#......................#............|
|...................................#..............|
|..#............................#..#...............|
|...........................#...................#.#|
|...........................................#......|
|..............#..............#.........#..........|
|..........................#.......................|
|......................................#...........|
|#...........................#.....................|
|....................................#.............|
|..................................................|
|..............................#...................|
|.##............................#..................|
|.................#..............................#.|
|...........#............................#.........|
|......................#........#..................|
|...................#...........#...............#..|
|..................................#...............|
|.............#............................#....#..|
|...........#.........#.......#...........#........|
|...............#...............#..........#.......|
|................#.......#...........#...........#.|
|...............................#.............#....|
|...................................#..............|
|..................................#...............|
+——————————————————————————————————————————————————+

+——————————————————————————————————————————————————+
|...........#...................#....#..#..........|
|..........................#.............#.........|
|.............................#....................|
|....#............#.....................#..........|
|......................#...........................|
|...........#.......##.............................|
|..........#.......................#...............|
|...................................#..............|
|..........#.......................................|
|......................#...........................|
|...........................xxxxxxxxxxxxxxxxx...#..|
|..........................x....j....j......#xxxx..|
|................#......j#x.....#....#.............|
|............#..........xx..j..jj.#......#.........|
|...........#.......#..x....#j.#j..............#...|
|.....................x.....j..j...................|
|....................x........j....................|
|...................x.........#j...................|
|.......#..........x..........j..........j.........|
|.................x......................#.........|
|................x......j..........................|
|.#...............jj....#j.........j...............|
|....#.............#...............#.......#.......|
|..................................................|
|.....#............................................|
|.#............#......................#............|
|...................................#..............|
|..#............................#..#...............|
|...........................#...................#.#|
|...........................................#......|
|..............#..............#.........#..........|
|..........................#.......................|
|......................................#...........|
|#...........................#.....................|
|....................................#.............|
|..................................................|
|..............................#...................|
|.##............................#..................|
|.................#..............................#.|
|...........#............................#.........|
|......................#........#..................|
|...................#...........#...............#..|
|..................................#...............|
|.............#............................#....#..|
|...........#.........#.......#...........#........|
|...............#...............#..........#.......|
|................#.......#...........#...........#.|
|...............................#.............#....|
|...................................#..............|
|..................................#...............|
+——————————————————————————————————————————————————+

35.5563==34.727
      Edited by Jan Uhlík
    • Tomáš Pecka
      Tomáš Pecka @peckato1 ·
      Author Owner

      Asi ten JPS přesunu pryč, už mě ty failující testy na CI/OBS nebaví řešit.

    • Tomáš Pecka mentioned in commit 17adc97a

      mentioned in commit 17adc97a

    • Tomáš Pecka mentioned in merge request !99 (merged)

      mentioned in merge request !99 (merged)

    • Tomáš Pecka mentioned in commit 56d14585

      mentioned in commit 56d14585

    • Tomáš Pecka
      Tomáš Pecka @peckato1 ·
      Author Owner

      Merge request !99 (merged) odstranuje JPS. Backup je ve vetvi issue132-jps.

    • Tomáš Pecka mentioned in commit c4bc905a

      mentioned in commit c4bc905a

    • Tomáš Pecka changed title from tests alib2graph_algo to JPS Graph algorithm

      changed title from tests alib2graph_algo to JPS Graph algorithm

    • Tomáš Pecka assigned to @uhlikja2

      assigned to @uhlikja2

    • Tomáš Pecka added C-algorithm P-medium T-bug labels

      added C-algorithm P-medium T-bug labels

    • Jan Trávníček mentioned in commit 2545b124

      mentioned in commit 2545b124

    • Jan Trávníček
      Jan Trávníček @travnja3 ·
      Owner

      There is an issue in the shortest path algos still: https://gitlab.fit.cvut.cz/algorithms-library-toolkit/automata-library/commits/issue-132-seed. Build of the branch fails.

    Please register or sign in to reply