algo

Graph Algorithms

• Neo4j comes included with some graph algorithms. Since Neo4j.rb simply wraps algorithms implemented in Java they should have good performence.
• All the Neo4j::Algo methods comes in two versions: some_algorithm_paths and some_algorithm_path. The first one returns all paths found, the second one returns only the first path found.
• The Neo4j::Algo methods behaves like the Neo4j::Node.outgoing traversal methods. That means you can combine outgoing, expand and incoming method
  to specify which relationship should be traversed using the algorithm.
  endprologue.

All Paths

The Neo4j::Algo.all_paths and Neo4j::Algo.all_path methods 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).

Example: nodes in the first path with relationship friends found between node_a and node_b:

Neo4j::Algo.all_paths(node_a, node_b).outgoing(:friends).first.nodes
# same as (notice paths and path !)
Neo4j::Algo.all_path(node_a, node_b).outgoing(:friends).nodes

Example: nodes in the first path with relationship friends and depth 1 found between node_a and node_b:

Neo4j::Algo.all_paths(node_a,node_b).outgoing(:friends).depth(1).first

Example: return the length of the first path of relationship :friends found between node_a and node_b:

Neo4j::Algo.all_paths(node_a,node_b).outgoing(:friends).first.length

Example: return the relationships of the first path of any relationship found between node_a and node_b:

# singular: all_path - return the first path found
Neo4j::Algo.all_path(node_a,node_b).rels

All Simple Paths

The Neo4j::Algo#all_simple_paths and Neo4j::Algo#all_simple_path methods 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).

Shortest Paths

The Neo4j::Algo.shortest_paths and Neo4j::Algo.shortest_path methods 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).

Example, using the expand method just for fun

Neo4j::Algo.shortest_path(node_a,node_b).expand{|node| node._rels(:outgoing, :friends)}
# same as
Neo4j::Algo.shortest_path(node_a,node_b).outgoing(:friends)

Example, shortest path with two relationships:

 Neo4j::Algo.shortest_path(node_a,node_b).outgoing(:friends).outgoing(:knows)

Dijkstra Paths

The Neo4j::Algo.dijkstra_paths and Neo4j::Algo.dijkstra_path methods returns 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 cost_evaluator.
These returned paths cannot contain loops (i.e. a node cannot occur more than once in any returned path).
See here for more information.

Example:

Neo4j::Algo.dijkstra_path(@x,@y).cost_evaluator{|rel,*| rel[:weight]}

With Length Paths

The Neo4j::Algo.with_length_paths and Neo4j::Algo.with_length_path methods returns an instance of Neo4j::Algo can find all paths of a certain length(depth) between two nodes.
These returned paths cannot contain loops (i.e. a node cannot occur more than once in any returned path).
Expects setting the depth parameter (the lenghto of the path) by the Algo#depth method.

Neo4j::Relationship.new(:friends, @x, @y)  # length 1
Neo4j::Relationship.new(:friends, @x, @b)  # length 3 x->b->c->y
Neo4j::Relationship.new(:friends, @b, @c)  # length 2 x->b-y
Neo4j::Relationship.new(:friends, @b, @y)
Neo4j::Relationship.new(:friends, @c, @y)
Neo4j::Algo.with_length_paths(@x,@y).depth(1).size #=> 1
Neo4j::Algo.with_length_paths(@x,@y).depth(2).size #=> 1
Neo4j::Algo.with_length_paths(@x,@y).depth(3).size #=> 1
Neo4j::Algo.with_length_paths(@x,@y).depth(4).size.#=> 0
Neo4j::Algo.with_length_path(@x,@y).depth(1) # include(@y)
Neo4j::Algo.with_length_path(@x,@y).depth(2) # include(@b,@y)
Neo4j::Algo.with_length_path(@x,@y).depth(3) # include(@b,@c,@y)

A* Paths

The Neo4j::Algo.a_star_paths and Neo4j::Algo.a_star_path returns an instance of Neo4j::Algo 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 here for more information.

The algorithm expacts an cost evaluator and estimate evaluator, see Neo4j::Algo#cost_evaluator and Neo4j::Algo#estimate_evaluator

Example:

  Neo4j::Algo.a_star_path(@x,@y).cost_evaluator{|rel,*| rel[:weight]}.estimate_evaluator{|node,goal| returns a float value}

The estimate_evaluator proc estimates the weight of the remaining path from one node to another.