mariorodriguespt / k-shortest-paths Goto Github PK

What steps will reproduce the problem?
1. use data file 

7

0 1 1
1 0 1
0 2 7
2 0 7 
1 2 1
2 1 1
1 3 3
3 1 3
1 4 2
4 1 2
2 4 4
4 2 4
3 5 6
5 3 6
3 4 1
4 3 1
4 5 2
5 4 2
3 6 100
6 3 100
6 1 1
1 6 1

2.
  Use test program 
   System.out.println("Testing Yen's algorithm for top-k shortest paths!");
        //VariableGraph graph = new VariableGraph("data/network");
        VariableGraph graph = new
VariableGraph("/home/cygnet/usr/NMSWorks/GraphAlgosLit/KSPImplementation/data/te
stUD2");
        DijkstraShortestPathAlg alg = new DijkstraShortestPathAlg(graph);
        //System.out.println(alg.get_shortest_path(graph.get_vertex(0),
graph.get_vertex(20)));
        //System.out.println(alg.get_shortest_path(graph.get_vertex(1),
graph.get_vertex(3)));

        System.out.println("Testing top-k shortest paths!");
        YenTopKShortestPathsAlg yenAlg = new YenTopKShortestPathsAlg(graph);
        List<Path> shortest_paths_list = yenAlg.get_shortest_paths(
                //graph.get_vertex(1), graph.get_vertex(3), 300);
                graph.get_vertex(0), graph.get_vertex(2), 100);
        System.out.println(":"+shortest_paths_list);
        System.out.println(yenAlg.get_result_list().size());
    }
3.

What is the expected output? What do you see instead?
 The output should contain many shortest paths. I see only two shortest paths.
 The output is 

Testing Yen's algorithm for top-k shortest paths!
Testing top-k shortest paths!
:[[0, 1, 2]:2.0, [0, 1, 4, 2]:7.0]
2

What version of the product are you using? On what operating system?
  I am using Linux and the java version of the kshortestpaths implementation.  

What am i doing wrong?
Thanks


Please provide any additional information below.

[deleted issue]

What steps will reproduce the problem?
1. 2.0 works with sample dataset but 2.1 does not

What is the expected output? What do you see instead?
A graph version of all possible paths. I get
Cost: 1.79769e+308 Length: 0

*********************************************
What version of the product are you using? On what operating system?
2.1 C++ - Linux

Please provide any additional information below.

Hi, 

The code doesn't work for the attached file. The graph represented in file
is a connected direct graph. All ok for the supplied test file.

Tested for
10 shortest paths, s = 0 and t= 50,38
Output
terminate called after throwing an instance of 'std::length_error'
  what():  vector::_M_fill_insert
Aborted

~YenTopKShortestPathsAlg(void)
    {
        for (multiset<BasePath*, WeightLess<BasePath>>::iterator it=m_quPathCandidates.begin();
            it!=m_quPathCandidates.end(); it++)
        {
            delete (*it);
        }
        for(vector<BasePath*>::iterator it= m_vResultList.begin();
            it!=m_vResultList.end();it++)
        {
            delete *it;
        }

        clear();
    }

and some other memory leak located in the DijkstraShortestPathAlg & Graph 
Function


see the attachment for detail

Hi,

I have transferred the build system to use CMake. So far, I have tested on Mac 
gcc (10.5), Clang, and gcc 4.6.2 on debian.

I have also added tests (although there are not regression tests).

Here is the repository:
https://github.com/arnaudgelas/KShortestPaths

Arnaud

What steps will reproduce the problem?
1. Once a Graph object is created with some data, it start throwing 
exception if new graph object is created with different data during same 
run of JVM
2.
3.

What is the expected output? What do you see instead?


What version of the product are you using? On what operating system?
OS: Windows 7
Version: 2.1 [Java Version]

Please provide any additional information below.

Dear Sir,

I try to conduct a large scale search, but it fails to works for the
attached file when k=500. It works ok for k=100.

Tested for
1500 shortest paths, s =181  and t= 722
Output
terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check
Aborted

What steps will reproduce the problem?
1. run the program normally using provided test file test_500
2.
3.

What is the expected output? What do you see instead?
the k (3000) shortest paths from node 1 to node 729

What version of the product are you using? On what operating system?
last version (1.0.3) with the updated (corrected) header file 
(QYDirectedPath.h)...boost library Ver 1.35.0 on windows XP SP2

Please provide any additional information below.
I have ran the program normally (environment and parameters are given 
above) for the test file provided (test_500) on e-machines desktop T6414 
AMD Athlon 64 Processor (3200++)...memory size = 512 MB...I halted the 
program after more than 2.5 hours of running time....but in the original 
paper....the reference paper... the expected running time would be less 
than this..... I would kindly ask for the reason of that...thnx for ur time

1. //3.2 remove the vertices and arcs in the graph  
should remove arcs (d(pk), i), i ∈ N, of p1, . . . , pk−1 from the 
network;
2. Set<Path> 
this is not OK for two paths have the same weight

What steps will reproduce the problem?
1. Execute the YenTopKShortestPathsAlgTest JUnit test with the following:
- the attached network file as data input.
- //look for the KShortestPaths between node 1 and node 3
   List<Path> shortest_paths_list = yenAlg.get_shortest_paths(
    graph.get_vertex(1), graph.get_vertex(3), k);
where is k >=5
the problem appears with other node pairs

What is the expected output? What do you see instead?
Null pointer exception: line 207 class YenTopKShortestPathsAlg

What version of the product are you using? On what operating system?
Java version 0.9 of the project, Windows XP, java version 1.6.0_03

Please provide any additional information below.
Surrounding the code between line 207 and 215 with:

if (dijkstra_alg.get_start_vertex_distance_index().get(cur_recover_vertex)
!= null 
     && dijkstra_alg.get_start_vertex_distance_index().get(succ_vertex) !=
null) {
    ........
}

seems to solve the issue, however I didn't go through the code to see if
it's the correct way to do it.

Thanks

What is the expected output? What do you see instead?
I am getting several errors. I have attached the error log. 

What version of the product are you using? On what operating system?
C++ version 2.0 . Ubuntu 11.10 - Linux 

Please provide any additional information below.

Kindly let me know the procedure how to compile and which files should be 
compiled in a sequence.

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.

What steps will reproduce the problem?
1. Using Borland C++ Builder 6 to compile this project.
2. There are a error in QYKShortestPaths.cpp during compiling the project.
3. The bug is in "void CQYKShortestPaths::_SearchTopKShortestPaths()" and 
line 127 :
// Call _Restore4CostAjustment again for the deviated_node
_RestoreEdges4CostAjustment(node_list_in_path, deviated_node_id, 
node_list_in_path.at(i+1), true);
4. The error message tells me that "Undefined symbol "i" on line 127.

What is the expected output? What do you see instead?


What version of the product are you using? On what operating system?
I use k-shortest-paths-1.0.2
My operating system is Windows XP SP2

Please provide any additional information below.
Please tell me how tow modify this error.

When the graph in the attached file (test_17) is taken as the input, not
all results can be returned. 

According to the old definition of 'Comparator', some candidates can not
put into the queue because there is another candidate in the queue with the
same cost and the same length. 

What steps will reproduce the problem?
1. Run the program as normal.

What is the expected output? What do you see instead?
The data in m_candidatePathsSet should be deleted in the destructor for the
QYKShortestPath class.

What version of the product are you using? On what operating system?
I am using version 1.0.3 of the project. I am running Windows XP with
Microsoft Visual Studio .NET 2003.

Please provide any additional information below.

The STL set function requires that the sorting criterion define a "strict 
weak ordering." In other words, the ordering has to be antisymmetric, 
transitive, and irreflexive.

Your Comparator function for CQYDirectedPath violates both the 
antisymmetric and irreflexive properties. Assume x and y are two paths with 
identical costs and lengths. Your implementation will have both x < y and y 
< x. Thus, not antisymmetric. Also, x < x will return true when it should 
return false.

If you add a third parameter, I used the ID, the Comparator function works 
as expected. This assumes that the IDs are unique, but I think that is a 
safe assumption.

I really believe this error should be fixed. Most of the time, the bug has 
no impact upon the results. However, in some cases this bug does lead to 
incorrect results and it may generate a run time error on some compilers.

I have attached my fix to the bug.

CPP Version of KShortest Path. File: QYShortestPath.cpp Line 151

During my experiments: On a certain graph (Road Network Luxemburg) with
certain s-t-Relations, the KShortest Path seqfaults at line 154 cause index
out of range of vector m_vEdges.

I think thix fixes it:
Replace
for (std::size_t j = 0; j < edges_count; ++j)
with
for (std::size_t j = 0; j < m_vEdges.size(); ++j)

m_vEdges.size() can be different from edges_count since some edges may
become disconnected and hence not added to m_vEdges.
This bug is usually not discovered since m_vEdges and edges_count mostly
vary only little and a vector often reserve more space than needed so
exceeding the vector boundaries is not discoverd (and may add some random
stuff to the new graph).

What steps will reproduce the problem?
1. run the program as normal
2. using a complete directed graph(just as the testing file test_17)
3. set the path number more than 3

What is the expected output? What do you see instead?
the program throw an exception

What version of the product are you using? On what operating system?
using MS visual studio 2005 with MS XP2 system

Please provide any additional information below.

What steps will reproduce the problem?
1. c++ MainP.cpp -o MainP.out
2.
3.

What is the expected output? What do you see instead?
Undefined symbols:
  "Graph::Graph(Graph const&)", referenced from:
      YenTopKShortestPathsAlg::YenTopKShortestPathsAlg(Graph const&, BaseVertex*, BaseVertex*)in ccIwu08M.o
  "YenTopKShortestPathsAlg::clear()", referenced from:
      YenTopKShortestPathsAlg::~YenTopKShortestPathsAlg()in ccIwu08M.o
  "YenTopKShortestPathsAlg::has_next()", referenced from:
      testYenAlg()     in ccIwu08M.o
  "Graph::Graph(std::basic_string<char, std::char_traits<char>, std::allocator<char> > const&)", referenced from:
      testYenAlg()     in ccIwu08M.o
      testDijkstraGraph()     in ccIwu08M.o
  "Graph::get_vertex(int)", referenced from:
      testYenAlg()     in ccIwu08M.o
      testYenAlg()     in ccIwu08M.o
      testDijkstraGraph()     in ccIwu08M.o
      testDijkstraGraph()     in ccIwu08M.o
  "Graph::~Graph()", referenced from:
      testYenAlg()     in ccIwu08M.o
      testYenAlg()     in ccIwu08M.o
  "DijkstraShortestPathAlg::get_shortest_path(BaseVertex*, BaseVertex*)", referenced from:
      testDijkstraGraph()     in ccIwu08M.o
  "YenTopKShortestPathsAlg::_init()", referenced from:
      YenTopKShortestPathsAlg::YenTopKShortestPathsAlg(Graph const&, BaseVertex*, BaseVertex*)in ccIwu08M.o
  "DijkstraShortestPathAlg::clear()", referenced from:
      DijkstraShortestPathAlg::~DijkstraShortestPathAlg()in ccIwu08M.o
  "YenTopKShortestPathsAlg::next()", referenced from:
      testYenAlg()     in ccIwu08M.o
ld: symbol(s) not found
collect2: ld returned 1 exit status


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

Please provide any additional information below.

Actually I do not know if I am doing the right thing but I find no information 
related to compiling/running the program. 

What version of the product are you using? On what operating system?
Visual Studio 2008, Windows


Please provide any additional information below.
I have downloaded the "KShortestPath_1.0.3.zip" C++ version and I have 
unzipped the Boost library files. I have added the Boost location in the 
project->Linker->Additional Library Directories

But still when I try to compile the k-shortest-paths program I get the 
following errors
d:\kshortestpath_1.0.3\qyshortestpath.h(39) : fatal error C1083: Cannot 
open include file: 'boost/graph/adjacency_list.hpp': No such file or 
directory

Any idea what is wrong?

Thanks in advance.

Anand.

What steps will reproduce the problem?
1.
2.
3.

What is the expected output? What do you see instead?
When I execute the project from the command line, all data file provided in the 
data directory throws an error. Here is the output error

c:\Users\Windows\Documents\Visual Studio 
2010\Projects\K_Shortest_PATH\Debug>KShortestPATH
Welcome to the real world!
The file data/test_15 can not be opened!

What version of the product are you using? On what operating system?
I am using Visual Studio 2010. Windows Vista OS

Please provide any additional information below.

I am struck in executing the results. Kindly help me out and its very urgent as 
I am struck here.


Thanks a lot in Advance!!!!

What steps will reproduce the problem?
1. Run the program with a source-destination pair that are not connected or
an invalid destination.
2. CQYShortestPath::_GetShortestPath() will return a new Directed Path that
is disconnected.
3. This graph needs to be deleted in QYShortestPath.cpp as part of the 
validity check.

What is the expected output? What do you see instead?
The graph should be deleted. The graph is not deleted.

What version of the product are you using? On what operating system?
I am using version 1.0.3 with MS Visual Studio 2003 on Windows XP.

Please provide any additional information below.

What steps will reproduce the problem?
1. input org or dst vertex to be null

What is the expected output? What do you see instead?
NullPointerException

What version of the product are you using? On what operating system?
Java implementation ver. 2.3

Please provide any additional information below.

It is caused by a validation code in _init() function.
line108: if(_source_vertex != null && _target_vertex != null)
This is to be OR condition.

Please try to check if possible.
best regards,