Comments (10)
I think I've found the same issue, I can reproduce a crash with the following line:
SELECT driving_distance(E'select 1 as id, 1000000000 as source, 1000000001 as target, 0.9::float8 as cost, 0.8::float8 as reverse_cost', 1000000000, 0.5, True, True);
for driving_distance, at least, the issue is that the boost graph library's adjancey_list, vector implementation, is allocating way too much memory.
on the large numbers where it goes slow, what does your memory usage look like?
from pgrouting.
This should be made into a test case for branch sew-devel-2_0
from pgrouting.
I can confirm this crashes 2.0 or pg 9.2.
from pgrouting.
This does not crash trsp.
pgr_test=# SELECT * FROM turn_restrict_shortest_path(
'SELECT id, source, target, cost FROM network',
4401489, 4401483, false, false, null) ;
seq | id1 | id2 | cost
-----+---------+-----------+------------------
0 | 4401489 | 134034463 | 12.1046145920234
1 | 4401485 | 134034455 | 53.5613132396201
2 | 4401483 | -1 | 0
(3 rows)
This will probably crash any of our boost implementations based on the way a graph is defined, because if I remember correctly, boost uses the vertex id to index into an array. I'll ask for more info on the boost list.
from pgrouting.
Response from Boost list.
On Wed, 15 May 2013, Stephen Woodbridge wrote:
Hi all,
I'm trying to understand/fix some bugs in pgRouting that use the boost libraries. I know C not not C++, so I can understand most of the more C-ish parts. We have an old bug that I believe is caused when we add an edge and it has large vertex ids or when there is a large number between the min and max vertex numbers.
We currently identify the min id number and down shift the ids by that, but that does not help if I add an edge (1)->(100000000). I could renumber all the nodes and then un-renumber them when done if I have to.
For adjacency lists with vecS as the vertex container type (the default), there is an assumption that vertex numbers are in the range 0...num_vertices(g)-1 (inclusive). Thus, if you want to use a vertex number 10000, your graph will need to have at least 10001 vertices (before you add the edge). There are several data structures in the graph class that whose sizes are proportional to the number of vertices, so using very large vertex numbers can end up eating large amounts of memory. There should not be any limits on vertex counts other than available memory; the vertex index type is usually size_t or some other large-enough type if I remember correctly.
Questions:
- is this a known limitiation in Boost graph?
We have run it with larger numbers of vertices before (but more often with compressed_sparse_row_graph), so it should not be a limitation.
- is there a different type of adjacency list mechanism that does not have this issue
Are you using widely separated vertex numbers (i.e., you use large numbers as vertex IDs but don't actually have a large number of vertices)? If so, you can try using labeled_graph. Otherwise,
- currently the code crashes the database backend, ideally I would like to catch any issues in the C++ wrapper, free memory and return an error code to the C caller so we don't kill the server or leak lots of memory.
I suspect you are hitting a buffer overflow here, so that won't be easy to trap. Compiling with _GLIBCXX_DEBUG defined (with GCC) will turn some of those problems into assertion failures, but that still won't help you get an error code. I think the best thing to try would be to fix any overflow issues; you are likely to get an exception if you try to add more vertices or edges than will fit into virtual memory (which probably won't happen, since you will most likely run out of physical memory first, and it's up to your OS what happens in that case).
Here is a link to our boost wrapper code:
https://github.com/pgRouting/pgrouting/blob/develop/src/dijkstra/src/boost_wrapper.cpp
We use that pattern for a lot of functions so if there is a better pattern, I might be able to update most(all?) of the functions that use this.
I see a few potential improvements:
- If you have all of the edge properties up front, you can create the adjacency list (or a compressed_sparse_row_graph, which will use less memory) directly using your edges and their properties, rather than adding them one-at-a-time. Even if you do need to use add_edge, you can add the edge properties as a fourth argument to that function. The constructor to adjacency_list to consider using is:
template <class EdgeIterator, class EdgePropertyIterator>
adjacency_list(EdgeIterator first, EdgeIterator last,
EdgePropertyIterator ep_iter,
vertices_size_type n,
edges_size_type m = 0,
const GraphProperty& p = GraphProperty())
- Using a raw pointer as a property map (as on lines 115 and 117) often breaks, especially on Visual C++. The recipe to use for that is:
boost::make_iterator_property_map
(predecessors.begin(),
get(boost::vertex_index, graph))
- You can use edge_predecessor_recorder as a visitor to Dijkstra's algorithm to get the edges in the path directly from the algorithm, rather than needing to find them yourself. Use http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/bfs_visitor.html as a template for what to do, replacing predecessor_recorder with edge_predecessor_recorder and using a property map that stores edge_descriptors rather than vertex_descriptors.
- Including "using namespace boost" and "using namespace std" together is likely to break in the future, since C++11's namespace std includes many of the same names as namespace boost does. Visual C++ has C++11 mode enabled by default in newer versions.
I could really use some help resolving this issue.
Meanwhile, I'm off to write a C main() to run this outside of the database and in gdb to see whats happening.
OK. You might be able to attach to the database server itself with gdb as well, but Valgrind might be a more useful tool for seeing what the problem is.
-- Jeremiah Willcock
from pgrouting.
I have create a command line test tools in "develop" branch in src/dijkstra/tester/ that can be run in gdb or valgrind to evaluate changes to the boost wrapper.
from pgrouting.
Does this affect pgRouting 2.0?
from pgrouting.
Yes, and it will have to wait for post 2.0 for a fix.
from pgrouting.
pgr_dijstra, pgr_ksp and pgr_dirvingDistance should work with big numbers
Moving the issue to milestone 2.2 for the other functions
from pgrouting.
I was reading in detail this issue, it mentions functions that we do not support any more like:
- shortest_path
- turn_restrict_shortest_path
- driving_distance
Instead of shortest_path use pgr_dijkstra
SELECT * FROM pgr_dijkstra('SELECT id, source, target, cost FROM network', 4401489, 4401483, false) ;
seq | path_seq | node | edge | cost | agg_cost
-----+----------+---------+-----------+------------------+------------------
1 | 1 | 4401489 | 134034463 | 12.1046145920234 | 0
2 | 2 | 4401485 | 134034455 | 53.5613132396201 | 12.1046145920234
3 | 3 | 4401483 | -1 | 0 | 65.6659278316435
Instead of driving_distance use pgr_drivingdistance
SELECT * from pgr_drivingdistance('select 1 as id, 1000000000 as source, 1000000001 as target, 0.9::float8 as cost, 0.8::float8 as reverse_cost', 1000000000, 0.5, True);
seq | node | edge | cost | agg_cost
-----+------------+------+------+----------
1 | 1000000000 | -1 | 0 | 0
Instead of turn_restrict_shortest_path use pgr_trsp
SELECT * FROM pgr_trsp(
'SELECT id, source, target, cost FROM network',
4401489, 4401483, false, false, null) ;
seq | id1 | id2 | cost
-----+---------+-----------+------------------
0 | 4401489 | 134034463 | 12.1046145920234
1 | 4401485 | 134034455 | 53.5613132396201
2 | 4401483 | -1 | 0
(3 rows)
For the queries posted on this issue the functions in V2.1 work.
I am closing this issue.
from pgrouting.
Related Issues (20)
- Support for contraction hierarchies
- Update tests on develop are failing
- Discrepancy in Routing Results Between pgr_TSP Versions (3.1.2 vs. 3.2.1)
- pgr_lingraph not giving expected results
- pgr_lengauerTarjanDominatorTree triggers an assertion
- TRSP for railroads doesn't work HOT 2
- Add details to CONTRIBUTING.md
- pgtap/mincut/compare.test.sql test data is flawed HOT 1
- pgrouting 3.6.0 fails to build on OSX HOT 2
- 3.6.0 fails to build with on 32 bit architectures HOT 2
- Add test for railroad wiki
- Boost 1.84 changed a StoerWagner
- Standardize spaningTree functions output
- pgr_ksp Seems to Ignore Parallel Edges HOT 1
- After 2607 build not working properly on macos HOT 1
- Clang tidy does not work
- Build failed on develop branch in M1 Mac Pro + Homebrew environment HOT 2
- Add macos-14 to macos CI HOT 1
- pgr_nodeNetwork returns old_id as int and not bigint
- pgr_dijkstra crashes Postgres14 using sample data and examples HOT 13
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from pgrouting.