We would like to present several path results using weighted path finding - instead of the "lightest" route, we'd like to present the 5 lightest routes. Is that possible? Has anyone done something similar?
On Tue, Oct 2, 2012 at 7:04 PM, Yuval <yuvalper...@gmail.com> wrote:
> We would like to present several path results using weighted path finding
> - instead of the "lightest" route, we'd like to present the 5 lightest
> routes.
> Is that possible?
> Has anyone done something similar?
Seems the idea is to traverse all possible paths... what if there are a lot of paths? Dijkstra allows to find the best route but not the second third etc but all might be too complex.
On Oct 3, 2012, at 1:13, Wes Freeman <freeman....@gmail.com> wrote:
> On Tue, Oct 2, 2012 at 7:04 PM, Yuval <yuvalper...@gmail.com> wrote:
>> We would like to present several path results using weighted path finding - instead of the "lightest" route, we'd like to present the 5 lightest routes.
>> Is that possible?
>> Has anyone done something similar?
So, when you're saying lightest, are you talking about path lengths, or
relationship properties with weights/scores on them?
Yeah, you can limit the result list of my query with LIMIT 5 (or something)
to get the best 5, but if you have hundreds or thousands of paths it
probably would get to be a slow query.
Anyone know a better way to get the top n best paths?
On Tue, Oct 2, 2012 at 7:20 PM, Yuval Perlov <yuvalper...@gmail.com> wrote:
> Seems the idea is to traverse all possible paths... what if there are a
> lot of paths? Dijkstra allows to find the best route but not the second
> third etc but all might be too complex.
> On Oct 3, 2012, at 1:13, Wes Freeman <freeman....@gmail.com> wrote:
> Please correct me if I'm misunderstanding your goal.
> Is "lightest" a calculation of the sum of relationship costs?
> On Tue, Oct 2, 2012 at 7:04 PM, Yuval <yuvalper...@gmail.com> wrote:
>> We would like to present several path results using weighted path finding
>> - instead of the "lightest" route, we'd like to present the 5 lightest
>> routes.
>> Is that possible?
>> Has anyone done something similar?
On Tuesday, October 2, 2012, Wes Freeman wrote:
> So, when you're saying lightest, are you talking about path lengths, or
> relationship properties with weights/scores on them?
> Yeah, you can limit the result list of my query with LIMIT 5 (or
> something) to get the best 5, but if you have hundreds or thousands of
> paths it probably would get to be a slow query.
> Anyone know a better way to get the top n best paths?
> Wes
> On Tue, Oct 2, 2012 at 7:20 PM, Yuval Perlov <yuvalper...@gmail.com<javascript:_e({}, 'cvml', 'yuvalper...@gmail.com');>
> > wrote:
>> Seems the idea is to traverse all possible paths... what if there are a
>> lot of paths? Dijkstra allows to find the best route but not the second
>> third etc but all might be too complex.
>> On Oct 3, 2012, at 1:13, Wes Freeman <freeman....@gmail.com<javascript:_e({}, 'cvml', 'freeman....@gmail.com');>>
>> wrote:
>> Please correct me if I'm misunderstanding your goal.
>> Is "lightest" a calculation of the sum of relationship costs?
>> On Tue, Oct 2, 2012 at 7:04 PM, Yuval <yuvalper...@gmail.com<javascript:_e({}, 'cvml', 'yuvalper...@gmail.com');>
>> > wrote:
>>> We would like to present several path results using weighted path
>>> finding - instead of the "lightest" route, we'd like to present the 5
>>> lightest routes.
>>> Is that possible?
>>> Has anyone done something similar?
On Wednesday, October 3, 2012 3:04:00 AM UTC+4, Yuval wrote:
> We would like to present several path results using weighted path finding > - instead of the "lightest" route, we'd like to present the 5 lightest > routes. > Is that possible? > Has anyone done something similar?
On Wed, Oct 3, 2012 at 12:20 AM, Yuval Perlov <yuvalper...@gmail.com> wrote:
> Seems the idea is to traverse all possible paths... what if there are a lot
> of paths? Dijkstra allows to find the best route but not the second third
> etc but all might be too complex.
Finding the shortest path involves looking at a lot of paths - think
about it, if you didn't, the shortest might be one of the ones you
didn't look at. It is the nature of the problem :)
Dijkstra in particular will find shortest paths to all reachable nodes
using some fixed starting point. Did you need multiple paths between
two fixed points instead? Then Dijkstra is not your friend.
On Wednesday, October 3, 2012 9:24:17 AM UTC+2, Lasse Westh-Nielsen wrote:
> On Wed, Oct 3, 2012 at 12:20 AM, Yuval Perlov <yuval...@gmail.com<javascript:>> > wrote: > > Seems the idea is to traverse all possible paths... what if there are a > lot > > of paths? Dijkstra allows to find the best route but not the second > third > > etc but all might be too complex.
> Finding the shortest path involves looking at a lot of paths - think > about it, if you didn't, the shortest might be one of the ones you > didn't look at. It is the nature of the problem :)
> Dijkstra in particular will find shortest paths to all reachable nodes > using some fixed starting point. Did you need multiple paths between > two fixed points instead? Then Dijkstra is not your friend.
On Wed, Oct 3, 2012 at 8:50 AM, Yuval <yuvalper...@gmail.com> wrote:
> Do you have any idea who might be my friend?
> The end result should be something similar to navigation apps where they
> show you several suggested routes.
I can't name any algorithms, but it will be some form of breadth-first
search that you terminate once you have enough paths. Maybe a modified
Dijkstra that doesn't optimise away longer paths?
Google is probably your friend, or maybe Peter or Craig who did Neo4j Spatial?
> On Wed, Oct 3, 2012 at 8:50 AM, Yuval <yuvalper...@gmail.com> wrote:
>> Do you have any idea who might be my friend?
>> The end result should be something similar to navigation apps where they
>> show you several suggested routes.
> I can't name any algorithms, but it will be some form of breadth-first
> search that you terminate once you have enough paths. Maybe a modified
> Dijkstra that doesn't optimise away longer paths?
> Google is probably your friend, or maybe Peter or Craig who did Neo4j Spatial?
Although the current Dijkstra algorithm could (easily) be modified to
return the top N cheapest paths. The reason it stops is that there's an
explicit check in there.
2012/10/3 Michael Hunger <michael.hun...@neopersistence.com>
> Am 03.10.2012 um 10:00 schrieb Lasse Westh-Nielsen <
> lasse.westh-niel...@neopersistence.com>:
> > On Wed, Oct 3, 2012 at 8:50 AM, Yuval <yuvalper...@gmail.com> wrote:
> >> Do you have any idea who might be my friend?
> >> The end result should be something similar to navigation apps where they
> >> show you several suggested routes.
> > I can't name any algorithms, but it will be some form of breadth-first
> > search that you terminate once you have enough paths. Maybe a modified
> > Dijkstra that doesn't optimise away longer paths?
> > Google is probably your friend, or maybe Peter or Craig who did Neo4j
> Spatial?
allShortestPaths with subsequent path evaluation for some weights is the stop gap solution. As our data set grows we will manipulate the Dijkstra algorithm to return top n. I am guessing algorithms are pluggable but failed to find somewhere that describes the process. Does anyone have a link?
BTW - is there a repository where we can showoff our Neo4j based creation?
On Wednesday, October 3, 2012 12:29:58 PM UTC+2, Mattias Persson wrote:
> Although the current Dijkstra algorithm could (easily) be modified to > return the top N cheapest paths. The reason it stops is that there's an > explicit check in there.
> 2012/10/3 Michael Hunger <michael...@neopersistence.com <javascript:>>
>> What about allShortestPaths?
>> Sent from mobile device
>> Am 03.10.2012 um 10:00 schrieb Lasse Westh-Nielsen < >> lasse.wes...@neopersistence.com <javascript:>>:
>> > On Wed, Oct 3, 2012 at 8:50 AM, Yuval <yuval...@gmail.com <javascript:>> >> wrote: >> >> Do you have any idea who might be my friend?
>> >> The end result should be something similar to navigation apps where >> they >> >> show you several suggested routes.
>> > I can't name any algorithms, but it will be some form of breadth-first >> > search that you terminate once you have enough paths. Maybe a modified >> > Dijkstra that doesn't optimise away longer paths?
>> > Google is probably your friend, or maybe Peter or Craig who did Neo4j >> Spatial?
You cannot apply weights after the fact as you will only have one path per destination node to look at. The weights need to be considered as you go along.
(You were looking for single pair shortest path right?)
Regards,
Lasse
On 8 Oct 2012, at 19:10, Yuval <yuvalper...@gmail.com> wrote:
> allShortestPaths with subsequent path evaluation for some weights is the stop gap solution. As our data set grows we will manipulate the Dijkstra algorithm to return top n.
> I am guessing algorithms are pluggable but failed to find somewhere that describes the process. Does anyone have a link?
> BTW - is there a repository where we can showoff our Neo4j based creation?
> Yuval
> On Wednesday, October 3, 2012 12:29:58 PM UTC+2, Mattias Persson wrote:
> Although the current Dijkstra algorithm could (easily) be modified to return the top N cheapest paths. The reason it stops is that there's an explicit check in there.
> 2012/10/3 Michael Hunger <michael...@neopersistence.com>
> What about allShortestPaths?
> Sent from mobile device
> Am 03.10.2012 um 10:00 schrieb Lasse Westh-Nielsen <lasse.wes...@neopersistence.com>:
> > On Wed, Oct 3, 2012 at 8:50 AM, Yuval <yuval...@gmail.com> wrote:
> >> Do you have any idea who might be my friend?
> >> The end result should be something similar to navigation apps where they
> >> show you several suggested routes.
> > I can't name any algorithms, but it will be some form of breadth-first
> > search that you terminate once you have enough paths. Maybe a modified
> > Dijkstra that doesn't optimise away longer paths?
> > Google is probably your friend, or maybe Peter or Craig who did Neo4j Spatial?
> You cannot apply weights after the fact as you will only have one path per
> destination node to look at. The weights need to be considered as you go
> along.
> (You were looking for single pair shortest path right?)
> Regards,
> Lasse
> On 8 Oct 2012, at 19:10, Yuval <yuvalper...@gmail.com> wrote:
> allShortestPaths with subsequent path evaluation for some weights is the
> stop gap solution. As our data set grows we will manipulate the Dijkstra
> algorithm to return top n.
> I am guessing algorithms are pluggable but failed to find somewhere that
> describes the process. Does anyone have a link?
> BTW - is there a repository where we can showoff our Neo4j based creation?
> Yuval
> On Wednesday, October 3, 2012 12:29:58 PM UTC+2, Mattias Persson wrote:
>> Although the current Dijkstra algorithm could (easily) be modified to
>> return the top N cheapest paths. The reason it stops is that there's an
>> explicit check in there.
>> 2012/10/3 Michael Hunger <michael...@**neopersistence.com>
>>> What about allShortestPaths?
>>> Sent from mobile device
>>> Am 03.10.2012 um 10:00 schrieb Lasse Westh-Nielsen <lasse.wes...@**
>>> neopersistence.com>:
>>> > On Wed, Oct 3, 2012 at 8:50 AM, Yuval <yuval...@gmail.com> wrote:
>>> >> Do you have any idea who might be my friend?
>>> >> The end result should be something similar to navigation apps where
>>> they
>>> >> show you several suggested routes.
>>> > I can't name any algorithms, but it will be some form of breadth-first
>>> > search that you terminate once you have enough paths. Maybe a modified
>>> > Dijkstra that doesn't optimise away longer paths?
>>> > Google is probably your friend, or maybe Peter or Craig who did Neo4j
>>> Spatial?
