a* traversal cost evaluator - how to customize

[John Fry]

Hi All,

when creating a custom getCost evaluator for an a* traversal which value is actually accumulated to make the path selection.

In the examples/docs below it isn't clear to me how 'lengthEvaluator' or 'estimateEvaluator' are used.

I believe that lengthEvaluator specifies the relationship to use and the estimateEvaluator is used to compute the cost from the relationship's start/end nodes.

I also think that for a potential path being evaluated e.g:

a-->--b-->--c-->--d-->--e-->--f 

that the estimateEvaluator will evaluate a cost in turn for a-b; b-c; c-d; d-e; e-f in turn. Then the astar function will return the path with the smallest accumulation of each of these cost evaluations.

Is this correct?

My goal is to specify my own cost function where the cost per relationship is computed as a function every relationship's start/end node's in and out degree plus some other properties the relationship has.  The total cost per path then needs to be the sum of these individual costs and i need the n most cheapest paths returned. 

I will post the code as an example once I have this figured out.

Thanks for any guidance, John.

public static PathFinder<WeightedPath> aStar(PathExpander expander,
                                             CostEvaluator<Double> lengthEvaluator,
                                             EstimateEvaluator<Double> estimateEvaluator)

Returns an PathFinder which uses the A* algorithm to find the cheapest path between two nodes. The definition of "cheap" is the lowest possible cost to get from the start node to the end node, where the cost is returned from lengthEvaluator and estimateEvaluator. These returned paths cannot contain loops (i.e. a node cannot occur more than once in any returned path). See http://en.wikipedia.org/wiki/A*_search_algorithm for more information.

Parameters:

expander - the PathExpander to use for expanding Relationships for each Path.

lengthEvaluator - evaluator that can return the cost represented by each relationship the algorithm traverses.

estimateEvaluator - evaluator that returns an (optimistic) estimation of the cost to get from the current node (in the traversal) to the end node.

Returns:

an algorithm which finds the cheapest path between two nodes using the A* algorithm.

Node nodeA = createNode( "name", "A", "x", 0d, "y", 0d );
Node nodeB = createNode( "name", "B", "x", 7d, "y", 0d );
Node nodeC = createNode( "name", "C", "x", 2d, "y", 1d );
Relationship relAB = createRelationship( nodeA, nodeC, "length", 2d );
Relationship relBC = createRelationship( nodeC, nodeB, "length", 3d );
Relationship relAC = createRelationship( nodeA, nodeB, "length", 10d );

EstimateEvaluator<Double> estimateEvaluator = new EstimateEvaluator<Double>()
{
    @Override
    public Double getCost( final Node node, final Node goal )
    {
        double dx = (Double) node.getProperty( "x" ) - (Double) goal.getProperty( "x" );
        double dy = (Double) node.getProperty( "y" ) - (Double) goal.getProperty( "y" );
        double result = Math.sqrt( Math.pow( dx, 2 ) + Math.pow( dy, 2 ) );
        return result;
    }
};
PathFinder<WeightedPath> astar = GraphAlgoFactory.aStar(
        PathExpanders.allTypesAndDirections(),
        CommonEvaluators.doubleCostEvaluator( "length" ), estimateEvaluator );
WeightedPath path = astar.findSinglePath( nodeA, nodeB );

[Michael Hunger]

Check out the graphdatabases.com book it has a nice section on A* with usage examples.

I think your understanding is roughly correct:

- costEvaluatior -> length of existing path (sum of cost values)

https://github.com/neo4j/neo4j/blob/3.1/community/graph-algo/src/main/java/org/neo4j/graphalgo/impl/util/DoubleEvaluatorWithDefault.java

- estimateEvaluator -> "estimate" of distance from current node to target node (most A* implementations use sth like line of sight with geo-coords).

See: https://github.com/neo4j/neo4j/blob/3.1/community/graph-algo/src/main/java/org/neo4j/graphalgo/impl/util/GeoEstimateEvaluator.java

Cheers, Michael

> --
> You received this message because you are subscribed to the Google Groups "Neo4j" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to neo4j+un...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[John Fry]

Thanks Michael I will study the info you sent.

[John Fry]

Just to close this off, as Michael correctly stated:

• the cost evaluator is a measurable cost property/attribute present on the relationship.
  
• the cost estimator is the heuristic estimate of cost to the end node to help the optimize the search.