2

I have created a directed graph from the nodes stored within my Postgres db but the resulting graph doesn't seem to be fully connected and as a result my shortest path algorithm is not able to find a path between start and end nodes.

When creating a graph, using networkx, from the nodes stored in my db (created by OSM2PO), I iterate through them adding edges to targets and their cost.

Am I along the correct lines, with using this graph creation algorithm? I have seen examples of converting OSM to graphs using the XML format and understand how they are iterating through the ways to populate the graph. What I don't understand is when using my implementation, there are multiple nodes of the same type referring to different 'edges' or paths to different target nodes, how is the algorithm just going through the database and connecting source to targets not working.

Improve this question
2
  • For anybody struggling with the same problem.
    – user3199699
    Commented Feb 12, 2016 at 15:26
  • The issue here is that the data created by OSM2PO for the postgresql database refers to "target" and "source" id's. I assumed these id's would detail the next/previous node it was connected to but I believe this actually refers to the beginning or end node in a collection of 'ways'. When building a graph to apply route finding algorithms like A* Djikstras you need to use the geometry information provided by each node to create an edge between the two points described ((x1,y1),(x2,y2)).
    – user3199699
    Commented Feb 12, 2016 at 15:33

1 Answer 1

Reset to default
1

No. The osm2po-PgRoutingWriter creates a standard table layout needed by PgRouting. The source- and target-columns are the keys for the routing. x1,y1,x2,y2 will only be needed if you want to proceed with A*. But in order to start and to get a first working result (using Dijkstra), just ignore it. What pgRouting does is the following: A simple row containing start-cost-target (other attributes omitted) must be doubled to reflect forward and reverse directions: So one row results to source->target and target->source. If the reverse_cost is high, it means that it is a oneway. So it's up to you if you want to include it or not. No, this is not a layout given by most examples, saying from Vertex A you can reach B,C,E - instead you'll find sth. like this here:

A -> B
A -> C
A -> D
B -> E
B -> F
C -> G

And depending on the reverse_cost you can also derive

B -> A
C -> A
D -> A
...
G -> C
Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.