[pgrouting-dev] pgRouting and the Shortest Path Shooting Star algorithm

Fri Mar 9 04:22:13 EST 2012

Hello

I get different results on each run. Your result is one of them.

Both the target_id and rule ids are edgeids refering to gid and should be correct. They originally referred to objid, but I remapped them to gid.
I will reduce the size of the network and send you new testdata.

Regards
Espen

> Date: Thu, 8 Mar 2012 09:21:12 -0500
> From: woodbri at swoodbridge.com
> To: espoern at hotmail.com; pgrouting-dev at lists.osgeo.org
> Subject: Re: [pgrouting-dev] pgRouting and the Shortest Path Shooting Star algorithm
> 
> Espen,
> 
> I have CC the list as there might be helpful information to others in my 
> response.
> 
> I get the following results on my Linux system. Is this what you are 
> getting on your system?
> 
> trsp_bug=# SELECT kollektivnett32.objid::integer, qry1.*
> FROM turn_restrict_shortest_path(
> 'SELECT gid AS id,
> source::int4,
> target::int4,
> minutes::double precision AS cost,
> rminutes::double precision AS reverse_cost
> FROM kollektivnett32',
> 17914,
> 24470,
> true,
> true,
> 'SELECT to_cost,
> gid AS target_id,
> rule AS via_path
> FROM kollektivnett32_turns
> WHERE costtype=''V''') qry1
> inner join kollektivnett32
> on qry1.edge_id=kollektivnett32.gid;
> 
> objid | vertex_id | edge_id | cost
> -------+-----------+---------+-------------------
> 39510 | 17914 | 39553 | 1.22921517354843
> 39503 | 19542 | 39546 | 1.16385126125265
> 39502 | 15062 | 39545 | 1.13463764875839
> 39501 | 10238 | 39544 | 0.894134798291999
> 39495 | 19538 | 39538 | 0.866380394768565
> 39496 | 19468 | 39539 | 0.933687082563116
> 39497 | 19470 | 39540 | 0.657732599215612
> 39498 | 19473 | 39541 | 0.908336115840503
> 39499 | 19452 | 39542 | 0.375975675882557
> 39500 | 9999 | 39543 | 0.467548379399679
> 39493 | 18169 | 39536 | 0.722558560770379
> 39492 | 19474 | 39535 | 0.359215445372181
> 39491 | 18166 | 39534 | 0.372316300710597
> 39490 | 6151 | 39533 | 0.7529314841121
> 39514 | 14128 | 39557 | 0.247611717608335
> 39513 | 2820 | 39556 | 0.642005590638696
> 39494 | 19535 | 39537 | 1.08148812344578
> 39475 | 19518 | 39518 | 0.985412403126148
> 39476 | 19519 | 39519 | 1.00870667860245
> 39477 | 19524 | 39520 | 1.10356478488934
> 39478 | 7347 | 39521 | 2.31489365914156
> 2912 | 19418 | 2630 | 0.710630767866117
> (22 rows)
> 
> Ok, I have a couple of observations:
> 
> 1. the route does not get to the destination node which seems like that 
> might indicate a bug
> 
> 2. I see you are using "rule AS via_path", is rule formatted the way you 
> would pass it to shooting_star? If so this is wrong. I unfortunately 
> implemented via_path to be a list of edges in the reverse order of rule.
> 
> IF for RULE:
> target_id: 1, rule: 2,3,4,5
> 
> THEN for via_path
> target_id: 1, via_path: 5,4,3,2
> 
> Since all your restrictions only involve a single edge this does not 
> matter. So moving on to the next potential problem. Consistency of edge 
> ids could be a problem.
> 
> For example, in the kollektivnett32_turns table what are the target_id 
> and rule ids? These should be the edge ids not the node ids and you 
> using: gid, objectid_1, objectid, or some other field for these values?
> 
> When you select your edges in the first query you have "gid as id", you 
> have to match the column used in the kollektivnett32_turns table as the 
> edge id to define the id in the first query. So if the 
> kollektivnett32_turns uses objectid values your first query needs to be 
> "objectid::integer as id"
> 
> Also it would be good it you can reduce the problem to a simple 10-20 
> node/edge graph that is easier to debug and understand. Most cases can 
> be demonstrated using a simple graph like:
> 
> o o
> | |
> | |
> o---------o---o--------o
> | | | |
> | | | |
> o-------o---------o---o--------o---------o
> | | | |
> | | | |
> o---------o---o--------o
> | |
> | |
> o o
> 
> Just label the nodes and the edges, and set up the restrictions, then 
> you can run simple tests to verify that it works as expected on simple 
> cases.
> 
> -Steve
> 
> On 3/8/2012 5:12 AM, Espen O wrote:
> > Hi
> >
> > Here is our testdata http://dl.dropbox.com/u/525315/example.rar
> >
> > It contains the following:
> >
> > *File *
> >
> > 
> >
> > *Description *
> >
> > Kollektivnett32.sql
> >
> > 
> >
> > Network table
> >
> > kollektivnett32_turns.sql
> >
> > 
> >
> > Turn restrictions table
> >
> > example_query.sql
> >
> > 
> >
> > Example query from node 17914 to 24470
> >
> > expected_route.jpg
> >
> > 
> >
> > Image of expected result (24,2 minutes including turn costs)
> >
> > Regards Espen
> >
> >
> > > Date: Wed, 7 Mar 2012 10:43:50 -0500
> > > From: woodbri at swoodbridge.com
> > > To: pgrouting-dev at lists.osgeo.org
> > > Subject: Re: [pgrouting-dev] pgRouting and the Shortest Path Shooting
> > Star algorithm
> > >
> > > On 3/7/2012 8:39 AM, Espen O wrote:
> > > > Hi
> > > >
> > > > We are very interested in version 1.03/1.05 of pgRouting and the
> > > > Shortest Path Shooting Star algorithm. However, there is a problem with
> > > > way restrictions in shooting star if there is more than one rule for an
> > > > edge. It also doesn’t seem to take into account the reverse cost.
> > We are
> > > > interested in fixing these bugs.
> > > >
> > > > Stephen Woodbridge has developed an alternative
> > > > “turn_restricted_shortest_path” which is very promising. We have tested
> > > > the Windows version compiled by Sanak (2012/03/04), but it is very
> > > > unstable and seems to return inconsistent answers when running the same
> > > > input data multiple times.
> > >
> > > Hi Espen,
> > >
> > > I would like to get a copy of you graph and queries that return
> > > inconsistent results. I have not seen this behavior and I think I need
> > > to understand what is happening. If we have a bug I want to get it fixed.
> > >
> > > Can you dump your database something like:
> > >
> > > pg_dump -fP -Z0 -f mydump.sql.gz -t <table_1> -t <table_2> ... -U <user>
> > > -h localhost <mydatabase>
> > >
> > > and email that and the queries you are running. I would be greatly
> > > appreciated and I will analyze it and get any bugs fixed that we need to.
> > >
> > > Thanks,
> > > -Steve
> > >
> > > > We are working on Windows 2008 server 32 bit, not Linux. Is there
> > anyone
> > > > who can give us the detailed setup for compiling on Windows (pgRouting
> > > > 1.03 2010/01/30 by Martin is the most stable we have tested) so we can
> > > > start to debug the source code? We have tried Sanaks recipe
> > > > (/sanak/pgrouting/blob/master/BUILD.msvc90), but we get a lot of errors
> > > > (Microsoft Visual C++ 2008 Express Edition and the required libraries).
> > > >
> > > > Regards
> > > > Espen
> > > >
> > > >
> > > > _______________________________________________
> > > > pgrouting-dev mailing list
> > > > pgrouting-dev at lists.osgeo.org
> > > > http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
> > >
> > > _______________________________________________
> > > pgrouting-dev mailing list
> > > pgrouting-dev at lists.osgeo.org
> > > http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120309/18acd79b/attachment.html