[pgrouting-users] Shootingstar

Henrik_Berggren · January 25, 2011, 11:27am

Sorry for spaming the mailinglist! But now the mail should be in the right thread.

Has anyone resolved the problem when shootingstar start on a link in the reverse direction?

The route should go from the top point to the bottom point, I'm only using length as cost and reverse_cost and no rules.

The porblem is similar to this http://download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/discussion/topic/345.html

Stephen_Woodbridge1 · January 25, 2011, 3:39pm

On 1/25/2011 6:27 AM, Henrik Berggren wrote:

Sorry for spaming the mailinglist! But now the mail should be in the
right thread.

Has anyone resolved the problem when shootingstar start on a link in the
reverse direction?

The route should go from the top point to the bottom point, I'm only
using length as cost and reverse_cost and no rules.

The porblem is similar to this
http://download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/discussion/topic/345.html

Yes this is the same problem that I just described a solution to. See my response to "Re: Hi It's Cleber Arruda from Sweden" So the subject line is not helpful for categorizing the content.

-Steve

Henrik_Berggren · January 26, 2011, 12:32pm

Hmm, should we reverse the entire network that we "sending" to the shooting_star algorithm? Or what am I missing.

See this blogpost for mor info. (My colleague)

http://thinkgit.blogspot.com/2011/01/pg-routing-shooting-star-issue.html

/Henrik

On 01/25/2011 04:39 PM, Stephen Woodbridge wrote:

On 1/25/2011 6:27 AM, Henrik Berggren wrote:

Sorry for spaming the mailinglist! But now the mail should be in the
right thread.

Has anyone resolved the problem when shootingstar start on a link in the
reverse direction?

The route should go from the top point to the bottom point, I'm only
using length as cost and reverse_cost and no rules.

The porblem is similar to this
http://download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/discussion/topic/345.html

Yes this is the same problem that I just described a solution to. See my response to "Re: Hi It's Cleber Arruda from Sweden" So the subject line is not helpful for categorizing the content.

-Steve
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

dkastl · January 26, 2011, 12:43pm

Hi Henrik,

Two more informations would be useful:

The query (SQL)
Some information about the data (would it be possible to send this small piece of data to be able to take a look?)
If you can’t post this data to the list (Navteq, right?), you can also send me in a direct email.
Daniel

2011/1/26 Henrik Berggren <henke.berggren@gmail.com>

Hmm, should we reverse the entire network that we “sending” to the shooting_star algorithm? Or what am I missing.

See this blogpost for mor info. (My colleague)

http://thinkgit.blogspot.com/2011/01/pg-routing-shooting-star-issue.html

/Henrik

On 01/25/2011 04:39 PM, Stephen Woodbridge wrote:

On 1/25/2011 6:27 AM, Henrik Berggren wrote:

Sorry for spaming the mailinglist! But now the mail should be in the
right thread.

Has anyone resolved the problem when shootingstar start on a link in the
reverse direction?

The route should go from the top point to the bottom point, I’m only
using length as cost and reverse_cost and no rules.

The porblem is similar to this
http://download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/discussion/topic/345.html

Yes this is the same problem that I just described a solution to. See my response to “Re: Hi It’s Cleber Arruda from Sweden” So the subject line is not helpful for categorizing the content.

-Steve

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Stephen_Woodbridge1 · January 26, 2011, 4:20pm

Actually, I think Henrik's problem may be a bug in the shooting star algorithm.

I think what Henrick is find is that is something like this:

   A---s---->B
   | |
   e |
   | |
   C-------->D

If "s" is the start and "e" is the end, shooting start will return the route AB, BD, CD, AC instead of AB, AC because AB is digitized from A to B but if it is digitized B to A the it will return the correct result.

So it seems the shooting star does NOT check for a shorter path going in the opposite direction if it can find a path going forward, even if it is longer.

Henrik, Can you confirm that this is what you are seeing?

-Steve

On 1/26/2011 7:43 AM, Daniel Kastl wrote:

Hi Henrik,

Two more informations would be useful:

    * The query (SQL)
    * Some information about the data (would it be possible to send this
      small piece of data to be able to take a look?)
      If you can't post this data to the list (Navteq, right?), you can
      also send me in a direct email.

Daniel

2011/1/26 Henrik Berggren <henke.berggren@gmail.com
<mailto:henke.berggren@gmail.com>>

    Hmm, should we reverse the entire network that we "sending" to the
    shooting_star algorithm? Or what am I missing.

    See this blogpost for mor info. (My colleague)

    http://thinkgit.blogspot.com/2011/01/pg-routing-shooting-star-issue.html

    /Henrik

    On 01/25/2011 04:39 PM, Stephen Woodbridge wrote:

        On 1/25/2011 6:27 AM, Henrik Berggren wrote:

            Sorry for spaming the mailinglist! But now the mail should
            be in the
            right thread.

            Has anyone resolved the problem when shootingstar start on a
            link in the
            reverse direction?

            The route should go from the top point to the bottom point,
            I'm only
            using length as cost and reverse_cost and no rules.

            The porblem is similar to this
            http://download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/discussion/topic/345.html

        Yes this is the same problem that I just described a solution
        to. See my response to "Re: Hi It's Cleber Arruda from Sweden"
        So the subject line is not helpful for categorizing the content.

        -Steve
        _______________________________________________
        Pgrouting-users mailing list
        Pgrouting-users@lists.osgeo.org
        <mailto:Pgrouting-users@lists.osgeo.org>
        http://lists.osgeo.org/mailman/listinfo/pgrouting-users

    _______________________________________________
    Pgrouting-users mailing list
    Pgrouting-users@lists.osgeo.org <mailto:Pgrouting-users@lists.osgeo.org>
    http://lists.osgeo.org/mailman/listinfo/pgrouting-users

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de/>

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Anton_Patrushev · January 27, 2011, 4:34am

Hi Steve, Henrik,

When we operate with edges as start and end for SP algo in directed
graph with reverse cost, we need to create additional edges to
represent reverse direction and (most funny part) decide which one -
original or additionally created - to use as a start/end. I guess
something goes wrong at this stage - it seams like additionally added
(reverse) edges are never selected.

Waiting for Henrik's data and query example.

Anton.

Henrik_Berggren · January 27, 2011, 4:01pm

I will post SQL query and a set of data tomorrow. But I think this is a bug just like Stephen wrote.

The problem I/we have is exactly the same as this: http://download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/discussion/topic/345.html

/H

On 01/27/2011 05:34 AM, Anton Patrushev wrote:

Hi Steve, Henrik,

When we operate with edges as start and end for SP algo in directed
graph with reverse cost, we need to create additional edges to
represent reverse direction and (most funny part) decide which one -
original or additionally created - to use as a start/end. I guess
something goes wrong at this stage - it seams like additionally added
(reverse) edges are never selected.

Waiting for Henrik's data and query example.

Anton.
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

dkastl · February 3, 2011, 2:35am

Hi list,

Just for the record:
The Shooting Star issue has been solved and the changes are available in the “master” branch.
https://github.com/pgRouting/pgrouting

Thanks to Henrik and Per for the good description of the problem and Sweco for the support.

Daniel

2011/1/28 Henrik Berggren <henke.berggren@gmail.com>

I will post SQL query and a set of data tomorrow. But I think this is a bug just like Stephen wrote.

The problem I/we have is exactly the same as this: http://download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/discussion/topic/345.html

/H

On 01/27/2011 05:34 AM, Anton Patrushev wrote:

Hi Steve, Henrik,

When we operate with edges as start and end for SP algo in directed
graph with reverse cost, we need to create additional edges to
represent reverse direction and (most funny part) decide which one -
original or additionally created - to use as a start/end. I guess
something goes wrong at this stage - it seams like additionally added
(reverse) edges are never selected.

Waiting for Henrik’s data and query example.

Anton.

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Worth_Lutz · October 19, 2011, 12:59pm

Just stumbled upon this and am not sure this affects me. I'm trying to
understand the shootingstar_smart_sp and google pointed out this message.

Am I correct in thinking that this fix is not in version 1.05 loaded through
the ubuntuGIS repository?

Is a compile from source necessary if I find this fix necessary?

Thanks

Worth Lutz

_____

From: pgrouting-users-bounces@lists.osgeo.org
[mailto:pgrouting-users-bounces@lists.osgeo.org] On Behalf Of Daniel Kastl
Sent: Wednesday, February 02, 2011 9:36 PM
To: pgRouting users mailing list
Subject: Re: [pgrouting-users] Shootingstar

Hi list,

Just for the record:

The Shooting Star issue has been solved and the changes are available in the
"master" branch.

https://github.com/pgRouting/pgrouting

Thanks to Henrik and Per for the good description of the problem and Sweco
for the support.

Daniel

2011/1/28 Henrik Berggren <henke.berggren@gmail.com>

I will post SQL query and a set of data tomorrow. But I think this is a bug
just like Stephen wrote.

The problem I/we have is exactly the same as this:
http://download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/discussion/t
opic/345.html

/H

On 01/27/2011 05:34 AM, Anton Patrushev wrote:

Hi Steve, Henrik,

When we operate with edges as start and end for SP algo in directed
graph with reverse cost, we need to create additional edges to
represent reverse direction and (most funny part) decide which one -
original or additionally created - to use as a start/end. I guess
something goes wrong at this stage - it seams like additionally added
(reverse) edges are never selected.

Waiting for Henrik's data and query example.

Anton.
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

--
Georepublic UG & Georepublic Japan
eMail: <mailto:daniel.kastl@georepublic.de> daniel.kastl@georepublic.de
Web: <http://georepublic.de/> http://georepublic.de

_____

No virus found in this message.
Checked by AVG - www.avg.com
Version: 10.0.1191 / Virus Database: 1435/3419 - Release Date: 02/02/11