threre is memory leakage in the code and sometimes it generate loop paths.

[WarEric]

I also find memory leakage in the code And the valgrind catches the leakage.

eric@eric:~/ksp/src$ /home/eric/download/valgrind-3.15.0/bin/valgrind --leak-check=full ./target ==2845== Memcheck, a memory error detector ==2845== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==2845== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info ==2845== Command: ./target ==2845== Welcome to the real world! ==2845== ==2845== HEAP SUMMARY: ==2845== in use at exit: 760 bytes in 11 blocks ==2845== total heap usage: 32 allocs, 21 frees, 83,889 bytes allocated ==2845== ==2845== 40 bytes in 1 blocks are definitely lost in loss record 2 of 10 ==2845== at 0x4C3045A: operator new(unsigned long) (vg_replace_malloc.c:344) ==2845== by 0x1153AA: DijkstraShortestPathAlg::get_shortest_path(BaseVertex*, BaseVertex*) (in /home/eric/ksp/src/target) ==2845== by 0x11AD21: YenTopKShortestPathsAlg::get_shortest_path(BaseVertex*, BaseVertex*) (in /home/eric/ksp/src/target) ==2845== by 0x11AC31: YenTopKShortestPathsAlg::_init() (in /home/eric/ksp/src/target) ==2845== by 0x10A1A3: YenTopKShortestPathsAlg::YenTopKShortestPathsAlg(Graph const&, BaseVertex*, BaseVertex*) (in /home/eric/ksp/src/target) ==2845== by 0x1098F4: testYenAlg() (in /home/eric/ksp/src/target) ==2845== by 0x109A07: main (in /home/eric/ksp/src/target) ==2845== ==2845== 48 bytes in 1 blocks are definitely lost in loss record 8 of 10 ==2845== at 0x4C3045A: operator new(unsigned long) (vg_replace_malloc.c:344) ==2845== by 0x1155CD: DijkstraShortestPathAlg::improve2vertex(BaseVertex*, bool) (in /home/eric/ksp/src/target) ==2845== by 0x115577: DijkstraShortestPathAlg::determine_shortest_paths(BaseVertex*, BaseVertex*, bool) (in /home/eric/ksp/src/target) ==2845== by 0x1151E6: DijkstraShortestPathAlg::get_shortest_path(BaseVertex*, BaseVertex*) (in /home/eric/ksp/src/target) ==2845== by 0x11AD21: YenTopKShortestPathsAlg::get_shortest_path(BaseVertex*, BaseVertex*) (in /home/eric/ksp/src/target) ==2845== by 0x11AC31: YenTopKShortestPathsAlg::_init() (in /home/eric/ksp/src/target) ==2845== by 0x10A1A3: YenTopKShortestPathsAlg::YenTopKShortestPathsAlg(Graph const&, BaseVertex*, BaseVertex*) (in /home/eric/ksp/src/target) ==2845== by 0x1098F4: testYenAlg() (in /home/eric/ksp/src/target) ==2845== by 0x109A07: main (in /home/eric/ksp/src/target) ==2845== ==2845== 672 (320 direct, 352 indirect) bytes in 1 blocks are definitely lost in loss record 10 of 10 ==2845== at 0x4C3045A: operator new(unsigned long) (vg_replace_malloc.c:344) ==2845== by 0x10A17E: YenTopKShortestPathsAlg::YenTopKShortestPathsAlg(Graph const&, BaseVertex*, BaseVertex*) (in /home/eric/ksp/src/target) ==2845== by 0x1098F4: testYenAlg() (in /home/eric/ksp/src/target) ==2845== by 0x109A07: main (in /home/eric/ksp/src/target) ==2845== ==2845== LEAK SUMMARY: ==2845== definitely lost: 408 bytes in 3 blocks ==2845== indirectly lost: 352 bytes in 8 blocks ==2845== possibly lost: 0 bytes in 0 blocks ==2845== still reachable: 0 bytes in 0 blocks ==2845== suppressed: 0 bytes in 0 blocks ==2845== ==2845== For lists of detected and suppressed errors, rerun with: -s ==2845== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)

[greenEkatherine]

I see many unsafe usages of memory. I think, we could fix memory leakage if refactor this solution with modern C++. @yan-qi don't you mind if I do it?

[yan-qi]

Sure. Please go ahead. Thanks

[tilltnet]

@greenEkatherine that would be awesome, if you would fix those issues! Looking forward to seeing your fork!

I was using an R package called yenpathy, that is using this library. When I tried to find all 500 to 1000 shortest paths in a medium sized network, which requires some 10 thousands of calls to the C++ code the leaked memory would pile up rather quickly and I would run out of memory.

After looking at the code a bit I was able to fix the big leaks and for my examples according to valgrind the memory leaked is now down to about 3%. My yenpathy fork including those changes can be found here.

[yan-qi]

It would be great if @tilltnet could have a PR for the change. Thanks