pgRouting

Forum #18 - Topic #47 - Message List

Shooting Star with different results …

Hi there.

I’ve encountered the following situation on a small dataset (I can send it if needed):

-the path from edge A to B is different from the path B to A

-both ‘directed’ and ‘has_reverse_cost’ are set to false

-cost = reverse_cost = length

-First call: shortest_path_shooting_star('SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM

roads_edges', 1783, 8, false, false)

-Second call: shortest_path_shooting_star('SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM

roads_edges', 8, 1783, false, false)

Can you help me with an explanation to understand why is happening like this?

Thank you,

Gray

grayraven
09/19/07 22:24:23
Tree View Flat View (newer first) Flat View (older first)
  • Message #177

    Yes. Not only ShootingStar have problem but also Shortest path astar, too. Can Any body give a explanation about that?

    DuyTan?
    09/20/07 18:25:01
  • Message #178

    Would it be possible to provide us with some sample code and the results you got? Otherwise it's difficult to give an answer.

    PS: I know, there is no way to attach files to the forum pages, but you could just create a Wiki page for your problem and link from here.

    daniel
    09/21/07 15:40:52
    • Message #179

      Thank you for prompt response.

      The shape file and screenshot are located at: http://rapidshare.com/files/57197687/sample.zip.html

      All i have done is to load it to postgre, then:

      ALTER TABLE roads ADD COLUMN source_id int4; ALTER TABLE roads ADD COLUMN target_id int4; ALTER TABLE roads ADD COLUMN edge_id int4;

      SELECT assign_vertex_id('roads', 0.01); SELECT create_graph_tables('roads', 'int4');

      ALTER TABLE roads_edges ADD COLUMN directed boolean; ALTER TABLE roads_edges ADD COLUMN has_reverse_cost boolean; ALTER TABLE roads_edges ADD COLUMN x1 float8; ALTER TABLE roads_edges ADD COLUMN y1 float8; ALTER TABLE roads_edges ADD COLUMN x2 float8; ALTER TABLE roads_edges ADD COLUMN y2 float8; ALTER TABLE roads_edges ADD COLUMN rule varchar; ALTER TABLE roads_edges ADD COLUMN to_cost int4;

      update roads_edges set x1 = X(StartPoint? (r.the_geom)) from roads as r WHERE r.edge_id=id; update roads_edges set y1 = Y(StartPoint? (r.the_geom)) from roads as r WHERE r.edge_id=id; update roads_edges set x2 = X(EndPoint? (r.the_geom)) from roads as r WHERE r.edge_id=id; update roads_edges set y2 = Y(EndPoint? (r.the_geom)) from roads as r WHERE r.edge_id=id;

      SELECT update_cost_from_distance('roads');

      -- prepare reverse UPDATE roads_edges SET reverse_cost = cost WHERE id IN (SELECT id FROM roads , roads_edges WHERE RESTRICTED = 0 AND edge_id=id); UPDATE roads_edges SET reverse_cost = 50000 WHERE id IN (SELECT id FROM roads , roads_edges WHERE RESTRICTED = 1 AND edge_id=id);

      UPDATE roads_edges SET directed = true; UPDATE roads_edges SET has_reverse_cost = true;

      --First call: shortest_path_shooting_star('SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM roads_edges', 1783, 8, false, false)

      --Second call: shortest_path_shooting_star('SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM roads_edges', 8, 1783, false, false)

      Gray

      grayraven
      09/21/07 20:10:48
      • Message #185

        Exaple code here: DataBase?:

        "X1","Y1","X2","Y2","Source","Target","length" 599164.4138858100,1189471.3356142601,599143.0752617900,1189460.2646382500,115,116,24.0396211468 598793.8669414700,1189385.7613421800,598906.6543975700,1189406.6509422001,271,272,114.7065734600 599037.0453096899,1189439.9196782301,599038.4338536901,1189422.8746862200,287,288,17.1014562908 599038.4338536901,1189422.8746862200,599044.7035497000,1189345.9102061500,288,274,77.2298509101 598906.3464295700,1189415.0831982100,599037.0453096899,1189439.9196782301,314,287,133.0377690920 599037.0453096899,1189439.9196782301,599143.0752617900,1189460.2646382500,287,116,107.9641984190 599164.4138858100,1189471.3356142601,599168.3794538199,1189447.2626542400,115,319,24.3974001451 599144.2016617900,1189516.1475183000,599143.0752617900,1189460.2646382500,320,116,55.8942310069 599143.0752617900,1189460.2646382500,599145.2841577900,1189443.0139502401,116,321,17.3915341066 599145.2841577900,1189443.0139502401,599167.6004458100,1189376.8470381801,321,250,69.9096079870 599038.4338536901,1189422.8746862200,599145.2841577900,1189443.0139502401,288,321,108.7316763480 599145.2841577900,1189443.0139502401,599168.3794538199,1189447.2626542400,321,319,23.4828487206 598906.9223015700,1189397.9736941899,599038.4338536901,1189422.8746862200,350,288,133.8482265310 598906.6543975700,1189406.6509422001,598906.3464295700,1189415.0831982100,272,314,8.4378780315 598906.3464295700,1189415.0831982100,598904.3830375701,1189470.2910062601,314,335,55.2428628257 598906.6543975700,1189406.6509422001,598906.9223015700,1189397.9736941899,272,350,8.6813826979 598906.9223015700,1189397.9736941899,598910.4722535700,1189271.4217580799,350,284,126.6097364210 599369.0500460001,1189487.0067822800,599168.3794538199,1189447.2626542400,289,319,204.5685271050 Query: A->B select gid, astext(the_geom)as the_geom from shortest_path_astar_as_geometry_internal_id_directed('road',350,321,false,false) and B->A select gid, astext(the_geom)as the_geom from shortest_path_astar_as_geometry_internal_id_directed('road',321,350,false,false)

        The path from edge A to B is different from the path B to A

        DuyTan?
        09/27/07 19:11:58
        • Message #186

          Hi,

          I would like to have edge ids also to test this data. By the way, are you sure that you are using edge ids (not vertex ids)?

          anton
          10/01/07 09:42:12
          • Message #187

            There are 16 record, you can choose 1->16 numbers for edge ids. Note: When i run with: SELECT * FROM shortest_path_astar('SELECT gid AS id, source::int4,

            target::int4, length::double precision AS cost,reverse_cost::double precision

            AS reverse_cost, x1, y1, x2, y2 FROM road',350, 321, false, false);

            or reverse vertexs source=321, target=350

            The result is A the same B but shortest_path_astar_as_geometry_internal_id_directed is different.

            I solved by rewriting with a programing language, connect to database Postgres.

            DuyTan?
            10/01/07 10:26:16
            • Message #188

              I'm sorry, I don't have enought time to test your data.

              Can you please list edge ids you got as a result from shortest_path_astar_as_geometry_internal_id_directed for both cases?

              anton
              10/01/07 10:58:27
            • Message #190

              --You can test with database dump follow: -- PostgreSQL database dump --

              -- Started on 2007-10-01 09:23:09

              SET client_encoding = 'UTF8'; SET standard_conforming_strings = off; SET check_function_bodies = false; SET client_min_messages = warning; SET escape_string_warning = off;

              SET search_path = public, pg_catalog;

              SET default_tablespace = ;

              SET default_with_oids = false;

              -- -- TOC entry 3150 (class 1259 OID 19820) -- Dependencies: 3536 3537 3538 1669 5 -- Name: road; Type: TABLE; Schema: public; Owner: postgres; Tablespace: --

              CREATE TABLE road (

              gid integer NOT NULL, length numeric, x1 numeric, y1 numeric, x2 numeric, y2 numeric, source bigint, target bigint, reverse_cost numeric, the_geom geometry, CONSTRAINT enforce_dims_the_geom CHECK ((ndims(the_geom) = 2)), CONSTRAINT enforce_geotype_the_geom CHECK (((geometrytype(the_geom) = 'MULTILINESTRING'::text) OR (the_geom IS NULL))), CONSTRAINT enforce_srid_the_geom CHECK ((srid(the_geom) = -1))

              );

              ALTER TABLE public.road OWNER TO postgres;

              -- -- TOC entry 3149 (class 1259 OID 19818) -- Dependencies: 3150 5 -- Name: road_gid_seq; Type: SEQUENCE; Schema: public; Owner: postgres --

              CREATE SEQUENCE road_gid_seq

              INCREMENT BY 1 NO MAXVALUE NO MINVALUE CACHE 1;

              ALTER TABLE public.road_gid_seq OWNER TO postgres;

              -- -- TOC entry 3544 (class 0 OID 0) -- Dependencies: 3149 -- Name: road_gid_seq; Type: SEQUENCE OWNED BY; Schema: public; Owner: postgres --

              ALTER SEQUENCE road_gid_seq OWNED BY road.gid;

              -- -- TOC entry 3545 (class 0 OID 0) -- Dependencies: 3149 -- Name: road_gid_seq; Type: SEQUENCE SET; Schema: public; Owner: postgres --

              SELECT pg_catalog.setval('road_gid_seq', 16, true);

              -- -- TOC entry 3535 (class 2604 OID 19822) -- Dependencies: 3150 3149 3150 -- Name: gid; Type: DEFAULT; Schema: public; Owner: postgres --

              ALTER TABLE road ALTER COLUMN gid SET DEFAULT nextval('road_gid_seq'::regclass);

              -- -- TOC entry 3541 (class 0 OID 19820) -- Dependencies: 3150 -- Data for Name: road; Type: TABLE DATA; Schema: public; Owner: postgres --

              INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (1, 24.0396211468, 599164.4138858100, 1189471.3356142601, 599143.0752617900, 1189460.2646382500, 115, 116, 24.0396211468, '01050000000100000001020000000200000052D7E8D3F8482241FDD0EA555F263241ACB68826CE4822412255BF4354263241'); INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (2, 114.7065734600, 598793.8669414700, 1189385.7613421800, 598906.6543975700, 1189406.6509422001, 271, 272, 114.7065734600, '0105000000010000000102000000030000007CC0DFBB134622414352E7C209263241E2D8BF77CD462241E804D9231B263241D0320D4FF5462241F125A4A61E263241'); INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (3, 17.1014562908, 599037.0453096899, 1189439.9196782301, 599038.4338536901, 1189422.8746862200, 287, 288, 17.1014562908, '01050000000100000001020000000200000002D53217FA472241620870EB3F263241481222DEFC4722419D6FEBDF2E263241'); INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (4, 77.2298509101, 599038.4338536901, 1189422.8746862200, 599044.7035497000, 1189345.9102061500, 288, 274, 77.2298509101, '010500000001000000010200000003000000481222DEFC4722419D6FEBDF2E263241AD6D9A3CFF472241986582521926324192AA376809482241204503E9E1253241'); INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (5, 133.0377690920, 598906.3464295700, 1189415.0831982100, 599037.0453096899, 1189439.9196782301, 314, 287, 133.0377690920, '0105000000010000000102000000020000007D375FB1F44622415B7A4C152726324102D53217FA472241620870EB3F263241'); INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (6, 107.9641984190, 599037.0453096899, 1189439.9196782301, 599143.0752617900, 1189460.2646382500, 287, 116, 107.9641984190, '01050000000100000001020000000200000002D53217FA472241620870EB3F263241ACB68826CE4822412255BF4354263241'); INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (7, 55.8942310069, 599144.2016617900, 1189516.1475183000, 599143.0752617900, 1189460.2646382500, 320, 116, 55.8942310069, '010500000001000000010200000002000000E9364067D048224177C2C3258C263241ACB68826CE4822412255BF4354263241'); INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (8, 17.3915341066, 599143.0752617900, 1189460.2646382500, 599145.2841577900, 1189443.0139502401, 116, 321, 17.3915341066, '010500000001000000010200000002000000ACB68826CE4822412255BF43542632415E217D91D2482241233E920343263241'); INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (9, 69.9096079870, 599145.2841577900, 1189443.0139502401, 599167.6004458100, 1189376.8470381801, 321, 250, 69.9096079870, '0105000000010000000102000000040000005E217D91D2482241233E920343263241559532A7D54822417BC2D7483D263241D6070FD1DE4822418A307ADF2B26324141A26D33FF4822416D7ED7D800263241'); INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (10, 108.7316763480, 599038.4338536901, 1189422.8746862200, 599145.2841577900, 1189443.0139502401, 288, 321, 108.7316763480, '010500000001000000010200000002000000481222DEFC4722419D6FEBDF2E2632415E217D91D2482241233E920343263241'); INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (11, 23.4828487206, 599145.2841577900, 1189443.0139502401, 599168.3794538199, 1189447.2626542400, 321, 319, 23.4828487206, '0105000000010000000102000000020000005E217D91D2482241233E9203432632413EC547C200492241EE4E3D4347263241'); INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (12, 133.8482265310, 598906.9223015700, 1189397.9736941899, 599038.4338536901, 1189422.8746862200, 350, 288, 133.8482265310, '0105000000010000000102000000020000005FE937D8F5462241D30544F915263241481222DEFC4722419D6FEBDF2E263241'); INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (13, 8.4378780315, 598906.6543975700, 1189406.6509422001, 598906.3464295700, 1189415.0831982100, 272, 314, 8.4378780315, '010500000001000000010200000002000000D0320D4FF5462241F125A4A61E2632417D375FB1F44622415B7A4C1527263241'); INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (14, 55.2428628257, 598906.3464295700, 1189415.0831982100, 598904.3830375701, 1189470.2910062601, 314, 335, 55.2428628257, '0105000000010000000102000000030000007D375FB1F44622415B7A4C15272632415028E239F1462241D3DD928D5626324113801DC4F0462241EB627F4A5E263241'); INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (15, 8.6813826979, 598906.6543975700, 1189406.6509422001, 598906.9223015700, 1189397.9736941899, 272, 350, 8.6813826979, '010500000001000000010200000002000000D0320D4FF5462241F125A4A61E2632415FE937D8F5462241D30544F915263241'); INSERT INTO road (gid, length, x1, y1, x2, y2, source, target, reverse_cost, the_geom) VALUES (16, 126.6097364210, 598906.9223015700, 1189397.9736941899, 598910.4722535700, 1189271.4217580799, 350, 284, 126.6097364210, '0105000000010000000102000000040000005FE937D8F5462241D30544F91526324174FDCCE5FC462241C4FBB4C2A32532410550D634FD462241E22E76339C2532417838CBF1FC4622415C56F86B97253241');

              -- -- TOC entry 3540 (class 2606 OID 19827) -- Dependencies: 3150 3150 -- Name: road_pkey; Type: CONSTRAINT; Schema: public; Owner: postgres; Tablespace: --

              ALTER TABLE ONLY road

              ADD CONSTRAINT road_pkey PRIMARY KEY (gid);

              -- Completed on 2007-10-01 09:23:09

              -- -- PostgreSQL database dump complete -- CREATE TYPE geoms AS (

              gid int4, the_geom geometry

              );

              CREATE OR REPLACE FUNCTION shortest_path_astar_as_geometry_internal_id_directed(

              geom_table varchar, source int4, target int4, dir boolean, rc boolean) RETURNS SETOF GEOMS AS

              $$ DECLARE

              r record; path_result record; v_id integer; e_id integer; geom geoms;

              query text;

              BEGIN

              query := 'SELECT gid,the_geom FROM '

              'shortest_path_astar(SELECT gid as id, source::integer, ' 'target::integer, length::double precision as cost, ' 'x1::double precision, y1::double precision, ' 'x2::double precision, y2::double precision ';

              IF rc THEN query := query ' ,reverse_cost::double precision AS reverse_cost '; END IF;

              query := query 'FROM ' quote_ident(geom_table) ' , '

              quote_literal(source) ' , '

              quote_literal(target) ' , dir, rc), '

              quote_ident(geom_table) ' where edge_id = gid ';

              FOR path_result IN EXECUTE query LOOP

              geom.gid := path_result.gid; geom.the_geom := path_result.the_geom;

              RETURN NEXT geom;

              END LOOP; RETURN;

              END; $$ LANGUAGE 'plpgsql' VOLATILE STRICT;

              DuyTan?
              10/01/07 11:30:29
              • Message #191

                edge ids is numbered from 1 to 16. The result test follow: select gid from shortest_path_astar_as_geometry_internal_id_directed('road',350,321,false,true)

                gid 15 13 5 6 8 select gid from shortest_path_astar_as_geometry_internal_id_directed('road',321,350,false,true)

                gid 10 12

                DuyTan?
                10/01/07 11:49:06
                • Message #193

                  OK, can you also try the following:

                  1. dijkstra function

                  2. shortest_path_astar_as_geometry_internal_id_directed('road',350,321,false,false) and shortest_path_astar_as_geometry_internal_id_directed('road',321,350,false,false)

                  anton
                  10/01/07 12:00:57
                  • Message #195

                    2. shortest_path_astar_as_geometry_internal_id_directed('road',350,321,false,false) and shortest_path_astar_as_geometry_internal_id_directed('road',321,350,false,false)

                    I tryed 2 above functions. The result is also wrong. I will try with dijkstra funtion. I can't undertand why it wrong? I can understand cost: shortest_path_astar_as_geometry_internal_id_directed but i can guess how it wrong with obove database

                    DuyTan?
                    10/01/07 12:11:59
  • Message #194

    Database:

    gid, x1, y1, x2, y2, source, target, length) 1,599164.4138858100,1189471.3356142601,599143.0752617900,1189460.2646382500, 115, 116, 24.0396211468

    2,598793.8669414700,1189385.7613421800,598906.6543975700,1189406.6509422001, 271, 272, 114.7065734600

    3,599037.0453096899,1189439.9196782301,599038.4338536901,1189422.8746862200, 287, 288, 17.1014562908

    4,599038.4338536901,1189422.8746862200, 599044.7035497000,1189345.9102061500, 288, 274, 77.2298509101

    5,598906.3464295700,1189415.0831982100,599037.0453096899,1189439.9196782301, 314, 287, 133.0377690920

    6,599037.0453096899,1189439.9196782301,599143.0752617900,1189460.2646382500, 287, 116, 107.9641984190

    7,599144.2016617900,1189516.1475183000,599143.0752617900,1189460.2646382500, 320, 116, 55.8942310069

    8,599143.0752617900,1189460.2646382500,599145.2841577900,1189443.0139502401, 116, 321, 17.3915341066

    9,599145.2841577900,1189443.0139502401,599167.6004458100,1189376.8470381801, 321, 250, 69.9096079870

    10,599038.4338536901,1189422.8746862200,599145.2841577900,1189443.0139502401, 288, 321, 108.7316763480

    11,599145.2841577900,1189443.0139502401,599168.3794538199,1189447.2626542400, 321, 319, 23.4828487206

    12,598906.9223015700,1189397.9736941899,599038.4338536901,1189422.8746862200, 350, 288, 133.8482265310

    13,598906.6543975700,1189406.6509422001,598906.3464295700,1189415.0831982100, 272, 314, 8.4378780315

    14,598906.3464295700,1189415.0831982100,598904.3830375701,1189470.2910062601, 314, 335, 55.2428628257

    15,598906.6543975700,1189406.6509422001,598906.9223015700,1189397.9736941899, 272, 350, 8.6813826979

    16,598906.9223015700,1189397.9736941899,598910.4722535700,1189271.4217580799, 350, 284, 126.6097364210

    DuyTan?
    10/01/07 12:03:42
    • Message #196

      The result tried: select gid from shortest_path_astar_as_geometry_internal_id_directed('road',350,321,false,false)

      gid 15 13 5 6 8

      select gid from shortest_path_astar_as_geometry_internal_id_directed('road',321,350,false,false)

      gid 10 12

      select gid from shortest_path_dijkstra1_as_geometry_internal_id_directed('road',350,321,0.001,false,false)

      gid 12 10

      select gid from shortest_path_dijkstra1_as_geometry_internal_id_directed('road',321,350,0.001,false,false)

      gid 10 12

      It is difficulty to exlain

      DuyTan?
      10/01/07 13:12:24
Tree View Flat View (newer first) Flat View (older first)