org.neo4j.graphalgo
Class GraphAlgoFactory
 java.lang.Object

 org.neo4j.graphalgo.GraphAlgoFactory

public abstract class GraphAlgoFactory extends Object
Static factory methods for the recommended implementations of common graph algorithms for Neo4j. The algorithms exposed here are implementations which are tested extensively and also scale on bigger graphs.


Constructor Summary
Constructors Constructor and Description GraphAlgoFactory()

Method Summary
All Methods Static Methods Concrete Methods Deprecated Methods Modifier and Type Method and Description static PathFinder<Path>
allPaths(PathExpander expander, int maxDepth)
Returns an algorithm which can find all available paths between two nodes.static PathFinder<Path>
allSimplePaths(PathExpander expander, int maxDepth)
Returns an algorithm which can find all simple paths between two nodes.static PathFinder<WeightedPath>
aStar(PathExpander expander, CostEvaluator<Double> lengthEvaluator, EstimateEvaluator<Double> estimateEvaluator)
Returns anPathFinder
which uses the A* algorithm to find the cheapest path between two nodes.static PathFinder<WeightedPath>
dijkstra(PathExpander expander, CostEvaluator<Double> costEvaluator)
Returns aPathFinder
which uses the Dijkstra algorithm to find the cheapest path between two nodes.static PathFinder<WeightedPath>
dijkstra(PathExpander expander, CostEvaluator<Double> costEvaluator, int numberOfWantedPaths)
Seedijkstra(PathExpander, CostEvaluator)
for documentation Instead of finding all shortest paths with equal cost, find the topnumberOfWantedPaths
paths.static PathFinder<WeightedPath>
dijkstra(PathExpander expander, InitialBranchState stateFactory, CostEvaluator<Double> costEvaluator)
Deprecated.Dijkstra should not be used with state onPathExpander
Seedijkstra(PathExpander, CostEvaluator)
. Seedijkstra(PathExpander, CostEvaluator)
for documentation. Uses a cost evaluator which uses the supplied property key to represent the cost (values of type double).static PathFinder<WeightedPath>
dijkstra(PathExpander expander, InitialBranchState stateFactory, String relationshipPropertyRepresentingCost)
Deprecated.Dijkstra should not be used with state onPathExpander
Seedijkstra(PathExpander, CostEvaluator)
. Seedijkstra(PathExpander, CostEvaluator)
for documentation. Uses a cost evaluator which uses the supplied property key to represent the cost (values of type double).static PathFinder<WeightedPath>
dijkstra(PathExpander expander, String relationshipPropertyRepresentingCost)
Seedijkstra(PathExpander, CostEvaluator)
for documentation.static PathFinder<WeightedPath>
dijkstra(PathExpander expander, String relationshipPropertyRepresentingCost, int numberOfWantedPaths)
Seedijkstra(PathExpander, CostEvaluator)
for documentation Instead of finding all shortest paths with equal cost, find the topnumberOfWantedPaths
paths.static PathFinder<Path>
pathsWithLength(PathExpander expander, int length)
Returns an algorithm which can find simple all paths of a certain length between two nodes.static PathFinder<Path>
shortestPath(PathExpander expander, int maxDepth)
Returns an algorithm which can find all shortest paths (that is paths with as shortPath.length()
as possible) between two nodes.static PathFinder<Path>
shortestPath(PathExpander expander, int maxDepth, int maxHitCount)
Returns an algorithm which can find all shortest paths (that is paths with as shortPath.length()
as possible) between two nodes.



Method Detail

allPaths
public static PathFinder<Path> allPaths(PathExpander expander, int maxDepth)
Returns an algorithm which can find all available paths between two nodes. These returned paths can contain loops (i.e. a node can occur more than once in any returned path). Parameters:
expander
 thePathExpander
to use for expandingRelationship
s for eachPath
.maxDepth
 the maxPath.length()
returned paths are allowed to have. Returns:
 an algorithm which finds all paths between two nodes.

allSimplePaths
public static PathFinder<Path> allSimplePaths(PathExpander expander, int maxDepth)
Returns an algorithm which can find all simple paths between two nodes. These returned paths cannot contain loops (i.e. a node cannot occur more than once in any returned path). Parameters:
expander
 thePathExpander
to use for expandingRelationship
s for eachPath
.maxDepth
 the maxPath.length()
returned paths are allowed to have. Returns:
 an algorithm which finds simple paths between two nodes.

shortestPath
public static PathFinder<Path> shortestPath(PathExpander expander, int maxDepth)
Returns an algorithm which can find all shortest paths (that is paths with as shortPath.length()
as possible) between two nodes. These returned paths cannot contain loops (i.e. a node cannot occur more than once in any returned path). Parameters:
expander
 thePathExpander
to use for expandingRelationship
s for eachPath
.maxDepth
 the maxPath.length()
returned paths are allowed to have. Returns:
 an algorithm which finds shortest paths between two nodes.

shortestPath
public static PathFinder<Path> shortestPath(PathExpander expander, int maxDepth, int maxHitCount)
Returns an algorithm which can find all shortest paths (that is paths with as shortPath.length()
as possible) between two nodes. These returned paths cannot contain loops (i.e. a node cannot occur more than once in any returned path). Parameters:
expander
 thePathExpander
to use for expandingRelationship
s for eachPath
.maxDepth
 the maxPath.length()
returned paths are allowed to have.maxHitCount
 the maximum number ofPath
s to return. If this number of found paths are encountered the traversal will stop. Returns:
 an algorithm which finds shortest paths between two nodes.

pathsWithLength
public static PathFinder<Path> pathsWithLength(PathExpander expander, int length)
Returns an algorithm which can find simple all paths of a certain length between two nodes. These returned paths cannot contain loops (i.e. a node could not occur more than once in any returned path). Parameters:
expander
 thePathExpander
to use for expandingRelationship
s for eachNode
.length
 thePath.length()
returned paths will have, if any paths were found. Returns:
 an algorithm which finds paths of a certain length between two nodes.

aStar
public static PathFinder<WeightedPath> aStar(PathExpander expander, CostEvaluator<Double> lengthEvaluator, EstimateEvaluator<Double> estimateEvaluator)
Returns anPathFinder
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 fromlengthEvaluator
andestimateEvaluator
. 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
 thePathExpander
to use for expandingRelationship
s for eachPath
.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.

dijkstra
public static PathFinder<WeightedPath> dijkstra(PathExpander expander, CostEvaluator<Double> costEvaluator)
Returns aPathFinder
which uses the Dijkstra 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 fromcostEvaluator
. These returned paths cannot contain loops (i.e. a node cannot occur more than once in any returned path). Dijkstra assumes none negative costs on all considered relationships. If this is not the case behaviour is undefined. Do not use Dijkstra with negative weights or use aCostEvaluator
that handles negative weights. See http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm for more information. Parameters:
expander
 thePathExpander
to use for expandingRelationship
s for eachPath
.costEvaluator
 evaluator that can return the cost represented by each relationship the algorithm traverses. Returns:
 an algorithm which finds the cheapest path between two nodes using the Dijkstra algorithm.

dijkstra
public static PathFinder<WeightedPath> dijkstra(PathExpander expander, String relationshipPropertyRepresentingCost)
Seedijkstra(PathExpander, CostEvaluator)
for documentation. Uses a cost evaluator which uses the supplied property key to represent the cost (values of type double). Parameters:
expander
 thePathExpander
to use for expandingRelationship
s for eachPath
.relationshipPropertyRepresentingCost
 the property to represent cost on each relationship the algorithm traverses. Returns:
 an algorithm which finds the cheapest path between two nodes using the Dijkstra algorithm.

dijkstra
public static PathFinder<WeightedPath> dijkstra(PathExpander expander, String relationshipPropertyRepresentingCost, int numberOfWantedPaths)
Seedijkstra(PathExpander, CostEvaluator)
for documentation Instead of finding all shortest paths with equal cost, find the topnumberOfWantedPaths
paths. This is usually slower than finding all shortest paths with equal cost. Uses a cost evaluator which uses the supplied property key to represent the cost (values of type double). Parameters:
expander
 thePathExpander
to use for expandingRelationship
s for eachPath
.relationshipPropertyRepresentingCost
 the property to represent cost on each relationship the algorithm traverses.numberOfWantedPaths
 number of paths to find. Returns:
 an algorithm which finds the cheapest path between two nodes using the Dijkstra algorithm.

dijkstra
public static PathFinder<WeightedPath> dijkstra(PathExpander expander, CostEvaluator<Double> costEvaluator, int numberOfWantedPaths)
Seedijkstra(PathExpander, CostEvaluator)
for documentation Instead of finding all shortest paths with equal cost, find the topnumberOfWantedPaths
paths. This is usually slower than finding all shortest paths with equal cost. Parameters:
expander
 thePathExpander
to use for expandingRelationship
s for eachPath
.costEvaluator
 evaluator that can return the cost represented by each relationship the algorithm traverses.numberOfWantedPaths
 number of paths to find. Returns:
 an algorithm which finds the cheapest path between two nodes using the Dijkstra algorithm.

dijkstra
@Deprecated public static PathFinder<WeightedPath> dijkstra(PathExpander expander, InitialBranchState stateFactory, CostEvaluator<Double> costEvaluator)
Deprecated. Dijkstra should not be used with state onPathExpander
Seedijkstra(PathExpander, CostEvaluator)
. Seedijkstra(PathExpander, CostEvaluator)
for documentation. Uses a cost evaluator which uses the supplied property key to represent the cost (values of type double). Parameters:
expander
 thePathExpander
to use for expandingRelationship
s for eachPath
.stateFactory
 initial state for the traversal branches.costEvaluator
 the cost evaluator for each relationship the algorithm traverses. Returns:
 an algorithm which finds the cheapest path between two nodes using the Dijkstra algorithm.

dijkstra
@Deprecated public static PathFinder<WeightedPath> dijkstra(PathExpander expander, InitialBranchState stateFactory, String relationshipPropertyRepresentingCost)
Deprecated. Dijkstra should not be used with state onPathExpander
Seedijkstra(PathExpander, CostEvaluator)
. Seedijkstra(PathExpander, CostEvaluator)
for documentation. Uses a cost evaluator which uses the supplied property key to represent the cost (values of type double). Parameters:
expander
 thePathExpander
to use for expandingRelationship
s for eachPath
.stateFactory
 initial state for the traversal branches.relationshipPropertyRepresentingCost
 the property to represent cost on each relationship the algorithm traverses. Returns:
 an algorithm which finds the cheapest path between two nodes using the Dijkstra algorithm.

