Quan-Zhi / k-shortest-paths

Automatically exported from code.google.com/p/k-shortest-paths
0 stars 0 forks source link

One bug in finding the shortest pathes #10

Open GoogleCodeExporter opened 8 years ago

GoogleCodeExporter commented 8 years ago
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.

Original issue reported on code.google.com by XiaoJunY...@gmail.com on 29 Apr 2009 at 1:55

GoogleCodeExporter commented 8 years ago
Could you please give more details about the running case? Like, which package 
are
you using? What is the starting/ending point? ......

Original comment by yan.qi....@gmail.com on 29 Apr 2009 at 7:16

GoogleCodeExporter commented 8 years ago
Hi, 
Thank you so much for your reply.
I used the latest version of your codes, KShortestPath_1.0.3 and tested the 
program 
using the test file you provided, the test_17.  The starting point is 0, and 
terminal is 5, K>=2. 

I have also tested it using another 4 nodes complete graph, setting the same 
cost 
for each of the links , like 1, and when I set starting point as 0, terminal as 
3, 
and K>=3, the same error happens.

For the same test file , sometimes, it may run correctly for a certain pair of 
nodes, but for some other pairs of nodes, the error happens.
Attached is the error and I have found that the possible error happens at the 
function "m_candidatePathsSet.insert(new CQYDirectedPath(new_node_id, 
cost_new_path, 
new_path));" in the file "QYKShortestPaths.cpp".

Could you please test it and tell me how to correct it? 

Original comment by XiaoJunY...@gmail.com on 30 Apr 2009 at 1:12

Attachments:

GoogleCodeExporter commented 8 years ago
Surprisingly, I didn't get any problem when I checked the program in my 
machine. I am
using VC6.0, and running the program in WinXP. From the screen-dump, it seems 
that
the problem may be related to the compiler you are using now. Not sure what 
caused
this exception. 

Original comment by yan.qi....@gmail.com on 30 Apr 2009 at 2:01

GoogleCodeExporter commented 8 years ago
I am using MS visual stdio 2005 with windows XP sp3. Have you checked the file 
test_17 with starting point 0 and end point at 5, and K>=3. I do not know why 
when I 
debug it, the exception happens.

Original comment by XiaoJunY...@gmail.com on 30 Apr 2009 at 2:08

GoogleCodeExporter commented 8 years ago
Any suggestions for how to avoid the exception, please?
Thank you so much!

Original comment by XiaoJunY...@gmail.com on 30 Apr 2009 at 2:21

GoogleCodeExporter commented 8 years ago
I can confirm that there is NOT a bug. I am using MS Visual Studio 2003 on 
Windows XP
SP3. The attached image shows the program to be working as expected.

Original comment by timothya...@gmail.com on 19 May 2009 at 9:54

Attachments:

GoogleCodeExporter commented 8 years ago
[deleted comment]
GoogleCodeExporter commented 8 years ago
thank you, timothyahahn, I still have the exception problem as the attached 
image 
shows and I found the problem was with the definition of Comparator. When more 
than 
one paths have the same cost and the same length, my complier begin to 
complain. I 
have solved the problem by adding the pathID as a parameter. 

Original comment by XiaoJunY...@gmail.com on 20 May 2009 at 2:34

Attachments:

GoogleCodeExporter commented 8 years ago
I was able to replicate the bug using the VS 2005 compiler, but it seems that 
both the 
VS 2003 and VS 2008 compilers work fine. Maybe you should post your revised 
code to 
this forum for others who might be using VS 2005.

Original comment by timothya...@gmail.com on 24 Jul 2009 at 8:23