Forum #18 - Topic #71 - Message List
Hello!! I have a big problem with the shooting_star algorithm...please help me!!
I try to test the algorithm on a simple situation
CREATE TABLE roads_edges (
gid integer,
source integer,
target integer,
cost double precision,
reverse_cost double precision,
to_cost double precision,
x1 double precision,
y1 double precision,
x2 double precision,
y2 double precision,
"rule" text
) WITHOUT OIDS;
INSERT INTO roads_edges (gid, source, target, cost, reverse_cost, to_cost, x1, y1, x2, y2, "rule") VALUES
(2, 2, 3, 25.495097567963924, 25.495097567963924, NULL, 60, 115, 85, 120, NULL),
(4, 5, 6, 29.068883707497267, 29.068883707497267, NULL, 1, 1, 20, 23, NULL),
(5, 6, 4, 40.049968789001575, 40.049968789001575, NULL, 20, 23, 60, 25, NULL),
(6, 4, 7, 27.313000567495326, 27.313000567495326, NULL, 60, 25, 85, 36, NULL),
(7, 8, 1, 59, 59, NULL, 1, 87.5, 60, 87.5, NULL),
(8, 1, 9, 25, 25, NULL, 60, 87.5, 85, 87.5, NULL),
(10, 11, 3, 15, 15, NULL, 85, 135, 85, 120, NULL),
(13, 7, 12, 35, 35, NULL, 85, 36, 85, 1, NULL),
(9, 9, 10, 65, 65, NULL, 85, 87.5, 150, 87.5, NULL),
(1, 1, 2, 27.5, 27.5, NULL, 60, 87.5, 60, 115, NULL),
(11, 3, 9, 32.5, 32.5, -1, 85, 120, 85, 87.5, '9'),
(12, 9, 7, 51.5, 51.5, -1, 85, 87.5, 85, 36, '9'),
(11, 3, 9, 32.5, 32.5, -1, 85, 120, 85, 87.5, '8'),
(3, 1, 4, 62.5, -1, NULL, 60, 87.5, 60, 25, NULL);
In my example it is not possible to pass from edge 9 to edges 12 and 11 , or from edge 8 to edge 11: that's right?
Then I run this query:
SELECT * FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM roads_edges order by gid', 9, 10, false, true);
The result is:
vertex_id edge_id cost
15 9 65
13 11 32.5
3 10 15
16 10 15
1)You can see that the result path pass from edge 9 to edge 11!!!
2)Why was the last edge (edge 10) repeated?
Sorry for my bad english:-( and thanks in advance:-)
-
Message #266
1)From your example I can see that it is better to go from edge 9 to 11 and 12 that to any other edge, cause the cost of passage (-1) is less than even length of the othe edges.
I should also say that if there is no other way but restricted one, algorithm will follow that restricted way even if the cost will be very high (because any result is better than no result).
2) Sorry, that's a known issue. It will be fixed soon.
anton11/27/07 22:52:16 -
Message #267
First thanks for your quick response
I thought that a negative cost would not permit the transition path from that node
However, I try to set to_cost=1000000, but the output not changes:-(
I was expecting that the path in output was: 9-->8-->1-->2-->10 Instead the path is always 9-->11-->10-->10
I try also to change the query:
SELECT * FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM roads_edges order by gid', 10, 9, false, true);
--with to_cost=-1 the output is 11-->9
(even if the first edge - 10 - not appear in the output)
--with to_cost=1000000 the server crashes!!
Maybe I not understand well how to work this algorithm:-(
vale8111/27/07 23:15:55 -
Message #268
Yes, you're right. Sometimes restriction rights aren'r set correctly.
Thank you for the report, I will try to fix it today or tomorrow.
anton11/28/07 12:37:50 -
Message #270
Thanks again for your help!
I'm very interested to the problem: I have to apply this algorithm to a much more complex situation and then I must understand well how it works!!!
vale8111/28/07 17:40:33 -
Message #278
Sorry for the delay - I was sick.
Well, I could solve both your problems - now it cares of all turn restrictions and doesn't crash anymore.
I'm going to release 1.01 bugfix version next week, so please wait.
anton12/08/07 13:07:40 -
Message #286
Hi Anton!!
Thank you very very much!! Thanks also for your work!!
I'm waiting for your new release and I hope that it solves my problem:-)
Regards
Vale
vale8112/10/07 17:36:31 -
Message #287
Thank you!
It is already here. Just go to the home page and download 1.01 version.
Few words about the dubbed edges in a result set.
First about the reason. When you use directed graph with reverse cost, Shooting* adds 'normal' edges with cost and also creates 'fake' edges with reverse_cost cost value for other direction. When you specify start and target edges by id you always choose 'normal' ones and it may happen that thay are going other direction or (in case of dead-ends) connected only with corresponded 'fake' edge. So, algorithm first comes along specified edge and then (as long as there is no other way or this way is shorter) along 'fake' one. Same with end edges. When you get a result, ids for 'fake' edges are converted to corresponded 'normal' ids and that's why sometimes you see start or end edges twice.
There are two reasons why I didn't fix this issue with the new release.
First, when I construct the list of edges which represents the result I don't know if it consists dubbed edges or not and I allocate the memory according to the number of edges. It is possible to search through the list and reallocate the memory, but it will take more time and I don't feel safe with this operation.
And second, I think it is quite easy to fix it with SQL wrapper function (which is done already, just try it) or at the client side.
So, please try the new version. And I'm waiting for your feedback.
anton12/10/07 18:14:11 -
Message #288
You were fast!!!
Thanks again:-)
Now I will try the new version:-)and let you know as soon as possible:-)
Vale
vale8112/10/07 19:14:23 -
Message #290
Hello Anton!
I try the new release. The server doesen't crash anymore:-)but.....
Do you remember my example? In my example it is not possible to pass from edge 9 to edges 12 and 11 , or from edge 8 to edge 11
EDGE _ RULE
11 _ 9
11 _ 8
12 _ 9
....
So I set to_cost=10000000000 in this case. (column rule is a text type, column to_cost is double precision)
Tell me if I take a mistake.
Then I choose two cases:
1)select * from shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM roads_edges order by gid',9,13,false, true);
The output is
vertex ; edge ; cost
15 ; 9 ; 65
13 ; 8 ; 25
4 ; 8 ; 25
13 ; 12 ; 51.5
10 ; 13 ;35
In this case the edge 8 is dubbed because it Is crossed twice. It's right (because it no possible to turn from edge 9 to edge 12, but it is possible from edge 8 to 12), but maybe it's strange
2)select * from shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM roads_edges order by gid',9,10,false, true);
The output is
vertex ; edge ; cost
15 ; 9 ; 65
13 ; 11; 32.5
3 ; 10; 15
16 ; 10 ; 15
The output is wrong!!! I was expected that the output were 9-->8-->1-->2-->10 All this link are two-way link
Please, Tell me what do you think!
vale8112/10/07 23:43:38 -
Message #291
It is very strange, 'cause I always get correct result for your example. It looks like 9-9-8-1-2-10-10.
I'm running it right now.
Ok, tomorrow I will come to the office and will investigate this problem.
anton12/11/07 00:23:11 -
Message #294
Really??
Maybe I made a mistake when I imported the new version.
I only launch routing_core_wrapper.sql and routing_core.sql. It's right? Sorry for all my questions:-((
vale8112/11/07 00:33:59 -
Message #297
Yeah, it looks like this:
gta=# SELECT * FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM roads_edges order by gid', 9, 10, true, true);
vertex_id | edge_id | cost
14 | 9 | 65
16 | 9 | 65
14 | 8 | 25
1 | 1 | 27.5
2 | 2 | 25.4950975679639
4 | 10 | 15
17 | 10 | 15
(7 rows)
Please, check your topology.anton12/11/07 09:39:40
