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 > Am 02.06.2016 um 23:14 schrieb John Fry <frydom.j...@gmail.com>: > > > 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 ); > > -- > 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+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. -- 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+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
