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

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 an PathFinder which uses the A* algorithm to find the cheapest path between two nodes.
static PathFinder<WeightedPath>	dijkstra(PathExpander expander, CostEvaluator<Double> costEvaluator) Returns a PathFinder which uses the Dijkstra algorithm to find the cheapest path between two nodes.
static PathFinder<WeightedPath>	dijkstra(PathExpander expander, CostEvaluator<Double> costEvaluator, int numberOfWantedPaths) See dijkstra(PathExpander, CostEvaluator) for documentation Instead of finding all shortest paths with equal cost, find the top numberOfWantedPaths paths.
static PathFinder<WeightedPath>	dijkstra(PathExpander expander, InitialBranchState stateFactory, CostEvaluator<Double> costEvaluator) Deprecated. Dijkstra should not be used with state on PathExpander See dijkstra(PathExpander, CostEvaluator). See dijkstra(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 on PathExpander See dijkstra(PathExpander, CostEvaluator). See dijkstra(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) See dijkstra(PathExpander, CostEvaluator) for documentation.
static PathFinder<WeightedPath>	dijkstra(PathExpander expander, String relationshipPropertyRepresentingCost, int numberOfWantedPaths) See dijkstra(PathExpander, CostEvaluator) for documentation Instead of finding all shortest paths with equal cost, find the top numberOfWantedPaths 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 short Path.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 short Path.length() as possible) between two nodes.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GraphAlgoFactory

public GraphAlgoFactory()

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 - the PathExpander to use for expanding Relationships for each Path.

maxDepth - the max Path.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 - the PathExpander to use for expanding Relationships for each Path.

maxDepth - the max Path.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 short Path.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). The algorithm is bi-directional breadth-first where nodes will be expanded according to the given expander.

Parameters:

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

maxDepth - the max Path.length() returned paths are allowed to have. Longer paths than that will not be examined.

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 short Path.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). The algorithm is bi-directional breadth-first where nodes will be expanded according to the given expander.

Parameters:

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

maxDepth - the max Path.length() returned paths are allowed to have. Longer paths than that will not be examined.

maxHitCount - the maximum number of Paths 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 - the PathExpander to use for expanding Relationships for each Node.

length - the Path.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 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.

dijkstra

public static PathFinder<WeightedPath> dijkstra(PathExpander expander,
                                                CostEvaluator<Double> costEvaluator)

Returns a PathFinder 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 from costEvaluator. 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 a CostEvaluator that handles negative weights. See http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm for more information.

Parameters:

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

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)

See dijkstra(PathExpander, CostEvaluator) for documentation. Uses a cost evaluator which uses the supplied property key to represent the cost (values of type double).

Parameters:

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

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)

See dijkstra(PathExpander, CostEvaluator) for documentation Instead of finding all shortest paths with equal cost, find the top numberOfWantedPaths 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 - the PathExpander to use for expanding Relationships for each Path.

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)

See dijkstra(PathExpander, CostEvaluator) for documentation Instead of finding all shortest paths with equal cost, find the top numberOfWantedPaths paths. This is usually slower than finding all shortest paths with equal cost.

Parameters:

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

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 on PathExpander See dijkstra(PathExpander, CostEvaluator). See dijkstra(PathExpander, CostEvaluator) for documentation. Uses a cost evaluator which uses the supplied property key to represent the cost (values of type double).

Parameters:

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

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 on PathExpander See dijkstra(PathExpander, CostEvaluator). See dijkstra(PathExpander, CostEvaluator) for documentation. Uses a cost evaluator which uses the supplied property key to represent the cost (values of type double).

Parameters:

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

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.