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 Relationship
s 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 );