yangshun2532 / k-shortest-paths Goto Github PK
View Code? Open in Web Editor NEWAutomatically exported from code.google.com/p/k-shortest-paths
Automatically exported from code.google.com/p/k-shortest-paths
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.
Original issue reported on code.google.com by [email protected]
on 19 May 2009 at 9:47
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).
Original issue reported on code.google.com by [email protected]
on 23 Feb 2010 at 2:40
Attachments:
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.
Original issue reported on code.google.com by [email protected]
on 17 Feb 2009 at 8:10
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.
Original issue reported on code.google.com by [email protected]
on 1 Sep 2009 at 5:05
Attachments:
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 [email protected]
on 13 Aug 2012 at 11:58
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.
Original issue reported on code.google.com by [email protected]
on 21 Apr 2008 at 5:30
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.
Original issue reported on code.google.com by [email protected]
on 2 Jun 2010 at 3:01
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
Original issue reported on code.google.com by [email protected]
on 9 Jan 2008 at 2:25
Attachments:
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.
Original issue reported on code.google.com by [email protected]
on 9 Jul 2011 at 12:03
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.
Original issue reported on code.google.com by [email protected]
on 7 Oct 2008 at 9:43
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.
Original issue reported on code.google.com by [email protected]
on 11 Jan 2008 at 6:52
Attachments:
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
Original issue reported on code.google.com by [email protected]
on 31 Jan 2009 at 11:02
~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
Original issue reported on code.google.com by [email protected]
on 8 Nov 2012 at 6:49
Attachments:
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,
Original issue reported on code.google.com by [email protected]
on 8 Feb 2011 at 6:04
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
Original issue reported on code.google.com by [email protected]
on 31 Dec 2009 at 12:07
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 [email protected]
on 29 Apr 2009 at 1:55
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
Original issue reported on code.google.com by [email protected]
on 25 Nov 2011 at 6:57
[deleted issue]
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
Original issue reported on code.google.com by [email protected]
on 24 Apr 2008 at 10:24
Attachments:
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.
Original issue reported on code.google.com by [email protected]
on 10 May 2012 at 1:08
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.
Original issue reported on code.google.com by [email protected]
on 2 Apr 2012 at 3:21
Attachments:
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!!!!
Original issue reported on code.google.com by [email protected]
on 3 Apr 2012 at 10:15
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.
Original issue reported on code.google.com by [email protected]
on 10 Mar 2010 at 11:31
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
Original issue reported on code.google.com by [email protected]
on 12 Aug 2008 at 5:27
Attachments:
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.