[Cartoweb-users] Questions about about pgdijkstra

[Sylvain Pasche]

Hello,

See answers inline.

Le lundi 16 janvier 2006 à 10:12 -0500, Fay Du a écrit :
> Hi all:
> 
>  
> 
>   I have a few questions about pgdijkstra module. I have posted the
> questions before. Since nobody responses my questions, I re-post them
> again.
> 
>  
> 
> 1. If I pass directed =true to shortest_path function, which means all
> road segments have directions? Can I set highways which need to be
> considerate direction (one-way), and local roads have no directions
> (two-way) in one route? You know, in real life, you can drive on
> one-way and two-way street in one trip. The route is a combination of
> one-way and two-way roads.
> 

directed controls if your graph is directed or not.

In a non directed graph, if you have an edge (A -> B), the path will be
able to go from A to B or B to A.

In a directed graph, if you have en edge (A -> B), the path will only be
able to go from A to B.

You can also use the reverse_cost as explained on:
http://www.cartoweb.org/downloads/pgdijkstra/README.txt

(see also explanation below)

> 2. Another question about direction. Do traffic directions have to
> match road segment direction? For example, a road segment start node
> id is 4, and end node id is 5, but traffic direction is actually from
> Node 5 to Node 4. Does shortest_path function support this situation?
> How? Do I have to flip one-way road segments to match traffic
> direction?
> 

I'm not sure to have understood your question. The shortest_path
function is only able to compute paths based on a set of edges, as given
through the source and target columns of the sql query fed to
shortest_path(). It has no knowledge of roads or traffic.

In fact you are free from that to interpret the nodes identifier the way
you want in your application.

> 
> 3. The algorithm optimize route based on cost, not the length of
> segment
> 

shortest_path() optimizes the route based on the value in the cost
column of the sql query given as the first parameter of that function.

The update_cost_from_distance() function is a helper function you can
use to set the cost from the geometry distance if you have a
geographical shape you want to import.

> 
> 4. When 2 edge share start point and end point, create_graph_tables
> cannot process them and crash with an error. In order to run the
> function, according to CarcoWeb User Manual (PartII. User Manual,
> 1.2.4.2.2, graph importation), I need to delete the edges which share
> start/end points from the table. I don’t think it is right. The
> attachment show two edges (red and blue) share start point and end
> point. There is nothing wrong with them. But  create_graph_tables
> cannot assign edge id for them. They have same start point and end
> points, create_graph_tables cannot treat them as two different edges.
> Did I miss something?
> 

I think you are referring to this bug:

http://bugzilla.maptools.org/show_bug.cgi?id=1180

This is an issue right now which need to be fixed. If you have a
solution, it is welcome though ;-)

> 
> 5. I run against sample data (roads_europe). 
> 
>  
> 
> 1) Calculate from node 27 to node 19. Set has_reverse_cost to true and
> set the graph is directed.
> 
> SELECT * FROM shortest_path('SELECT id, source, target, cost,
> reverse_cost FROM roads_europe_edges',  27, 19, true, true);
> 
> It returned 47 rows
> 
>  
> 
> 2) Calculate from node 19 to node 27. Set has_reverse_cost to false
> and set the graph is directed.
> 
> SELECT * FROM shortest_path('SELECT id, source, target, cost FROM
> roads_europe_edges', 
> 
>          19, 27, true, false);
> 
> It returned a message: no path found.
> 
>  
> 
> If second statement cannot return a path, how the first statement can
> calculate reverse cost?
> 

When you set reverse_cost = true, and you have in the sql query
something like:

source:A, target:B, cost=10, reverse_cost=20

The graph will be built with 2 edges:

(A -> B, cost = 10)
and
(B -> A, cost = 20)

If you set reverse_cost = false, you will only have on edge
 (A -> B, cost=10)
( the reverse_cost column will not be used).

This is why when you set reverse_cost = false, you need to have edges in
the two directions appearing in your query if you want to go in the two
directions. This may explain why you have "no path found".

What you could do is:

SELECT * FROM shortest_path(
'SELECT id, source, target, cost, reverse_cost FROM roads_europe_edges
union 
SELECT id, target as source, source as target , cost, reverse_cost FROM
roads_europe_edges',  19, 27, true, false);


Regards,

Sylvain