Uniform cost search

[Fabrizio]

Hello,
Let's suppose we have a traveler scenario, where cities be connected
by roads. Roads are represented by weighted edges, the weight is the
time needed to traverse it.

The problem I'm trying to solve is that, starting from a city, I'd
like to list the cities I can reach, travelling at most a known amount
of time.

I'd like to use a traversal method, accumulating the cost and pruning
the tree when it become greater than the maximum allowed cost. The
problem is that I should keep a different accumulator for each path,
and I can't see how I could do it using the api.

If I don't find a clean solution I could solve by hand the problem,
writing a recursive function, keeping a set of all the traversed
nodes. But it would be a shame missing a cleaner solution.

Any suggestion?
Thank you in advance.
--
fabrizio

[Andreas Ronge]

Hi
Hi

Have you looked at this:
http://blogs.neotechnology.com/peter/2010/04/cool-spatial-algos-with-neo4j-part1-routing-with-a.html
Looks like it is related to your problem of accumulated cost for paths.
Also, check the Ruby wrapper for the graph algorithm:
http://neo4j.rubyforge.org/guides/algo.html#a-paths
(instead of writing your own AStar class as in the example.)

/Andreas

> --
> You received this message because you are subscribed to the Google Groups "neo4jrb" group.
> To post to this group, send email to neo...@googlegroups.com.
> To unsubscribe from this group, send email to neo4jrb+u...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/neo4jrb?hl=en.
>
>

[Fabrizio]

Hello Andreas,
the solution proposed in those examples have the wrong arity, it
answers to the question: what's the best path between two nodes? My
question is: what are the nearest nodes to my node?

Do you think that I should study the java library deeply, in order to
understand how my traversal could be done efficiently at that level?

Another choice could be using the neo4j-spatial, changing a little bit
my spatial representation:
http://wiki.neo4j.org/content/Finding_things_close_to_other_things

Coordinate myPosition = new Coordinate(13.76, 55.56);
List<SpatialDatabaseRecord> results =
layer.findClosestPointsTo(myPosition, 10.0);

There is a ruby wrapper for that library: https://github.com/craigtaverner/neo4j-spatial.rb.
I still have to check it, I'm not sure it supports the method I need.

Even if it works it's not so simple. The geo distance represents only
a part of the cost I need to calculate, the distance is only a simple
approximation...

Thank you.
--
fabrizio

On Apr 15, 12:23 pm, Andreas Ronge <andreas.ro...@gmail.com> wrote:
> Hi
> Hi
>

> Have you looked at this:http://blogs.neotechnology.com/peter/2010/04/cool-spatial-algos-with-...

[Craig Taverner]

Since you mention 'Neo4j Spatial', I thought perhaps I should comment.

You said that a geo distance is only part of the total cost you need to consider. But if you can map your total cost space into a 2D (or perhaps 3D) space, then you could still use Neo4j-Spatial. The main problem I think you might have is that normally in a graph, you have costs between relations that do not produce a uniform space. For example, in a pure projected geographic space, if you go from A->B->C->A (cyclic loop) you really do get back to the same place (in terms of costs like x or y). But for other costs this might not be true. If it is true, then you can map the entire graph only one absolute space, you can certainly use Neo4j Spatial to do what you are after. Otherwise you need a clever approximation. If you already use geo in your cost, and it is an approximation, then perhaps your original idea is still valid (use geo first, then re-sort top-n on real costs later).

Having said all this, I am also certain that there are graph algorithms for what you want, so a review of the spatial algos is probably your best bet.

[Fabrizio]

Thank you Craig.
Actually I'm modeling the terrain for a game, I have many costs to
consider.
In example I have the visibility distance between players and the
reachability cost between them. The fastest route between two points
is usually different than the straight line.
I'm trying this model: geo locate players, and use spatial algorithms
on their positions to know who are their nearest enemies (this solves
partially the visibility problem). Then, on a terrain graph that
represents the cost to go from a location to another, I can calculate
the fastest route using an A* algorithm for every seen enemy.
This could work, I think.

Thank you again for your help.

On Apr 18, 12:00 am, Craig Taverner <cr...@amanzi.com> wrote:
> Since you mention 'Neo4j Spatial', I thought perhaps I should comment.
>
> You said that a geo distance is only part of the total cost you need to
> consider. But if you can map your total cost space into a 2D (or perhaps 3D)
> space, then you could still use Neo4j-Spatial. The main problem I think you
> might have is that normally in a graph, you have costs between relations
> that do not produce a uniform space. For example, in a pure projected
> geographic space, if you go from A->B->C->A (cyclic loop) you really do get
> back to the same place (in terms of costs like x or y). But for other costs
> this might not be true. If it is true, then you can map the entire graph
> only one absolute space, you can certainly use Neo4j Spatial to do what you
> are after. Otherwise you need a clever approximation. If you already use geo
> in your cost, and it is an approximation, then perhaps your original idea is
> still valid (use geo first, then re-sort top-n on real costs later).
>
> Having said all this, I am also certain that there are graph algorithms for
> what you want, so a review of the spatial algos is probably your best bet.
>

[Peter Neubauer]

Cool,
Let us know how it works out!

[Craig Taverner]

Hi Fabrizio,

OK. In your case it make sense to use the ideas you described, but not my idea. You have a real spatial scenario, and spatial distance is interesting and relevant, so you can use it as an initial calculation, but you still need to do the route calculate for your final result. The key point being that different routes to the same point have different costs. With the spatial index, the route is irrelevant, only the position in absolute space.

Good luck and let us know how it goes.

Regards, Craig