Major memory leak from multiple Yen instances, and questionable independence of solution

What steps will reproduce the problem?
1. Read in a graph
2. Create multiple YenTopKShortestPathsAlg objects for different sources and 
dests using same graph.

What is the expected output? What do you see instead?
The YenTopKShortestPathsAlg object ought to be destroying the Graph object it 
"copies"  when the YenTopKShortestPathsAlg instance is destroyed.  Instead, the 
Graph is not destroyed and becomes a memory leak.

To compound things, explicitly destroying the copied Graph object in the 
YenTopKShortestPathsAlg destructor causes a crash, because of a pointer/data 
mismatch between the Graph object's "copy" operation and its destructor.  It 
copies only the *pointers* to the data, while the Graph object destructor 
actually destroys the *data* pointed to by those pointers--which is shared 
among multiple copied graph objects.

In effect, the author does not correctly apply consistent data and pointer 
management when copying and destroying objects.

This problem also draws into question whether the algorithm creates independent 
solutions when run with multiple operations on the same graph.  The Yen 
algorithm may actually manipulate the data in the graph, and if that data is 
not actually *copied* as independent data in the "copy" operation, then changes 
to the graph may affect subsequent attempts to run the algorithm.

What version of the product are you using? On what operating system?

2.1, MSVC9

Please provide any additional information below.

A hack to resolve the solution-independence involves reading in the Graph anew 
every time a new YenTopKShortestPathsAlg object uses it. That 
YenTopKShortestPathsAlg object is also modified to use the pointer to the Graph 
directly, instead of making a "copy" of it.  After the YenTopKShortestPathsAlg 
completes, the YenTopKShortestPathsAlg  object is manually destroyed and then 
the Graph object.  This doesn't fix all the memory problems, but does cut 
memory use but cuts the memory usage by an *order of magnitude* (1-2GB vs 
~150MB) for a few hundred path vertex pairs).  Also  the solution will be 
guaranteed to be independent of previous operations.

Suggestions:  dump this custom made Graph library and use something more 
standard such as the Boost graph library.  Also know what data is being shared 
before destroying it, and make sure to account for all your pointers and memory.

Original issue reported on code.google.com by bionicba...@gmail.com on 13 Aug 2012 at 11:58

Quan-Zhi / k-shortest-paths

Major memory leak from multiple Yen instances, and questionable independence of solution #23