[pgrouting-dev] pgRouting and the Shortest Path Shooting Star
algorithm
Stephen Woodbridge
woodbri at swoodbridge.com
Fri Mar 9 09:25:32 EST 2012
Espen,
I do not think I can help you because I get the same results every time
I run it. So I have to conclude that there is some problem with your
build. Or something else strange that I can not reproduce here.
Maybe Sanak has time to look into it or not. We thank him for his
attempt to build a Windows version.
Regardless it is good to have a good test case when we need to diagnose
problems. It would be a great service to the community if a Windows
developer had time to create pgRouting packages and occasionally look at
problems like this.
Thanks,
-Steve
On 3/9/2012 4:22 AM, Espen O wrote:
> 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
> >
More information about the pgrouting-dev
mailing list