Class: Neo4j::Algo

Inherits:
Object
  • Object
show all
Includes:
Enumerable, Core::ToJava
Defined in:
lib/neo4j/algo.rb

Overview

A wrapper for the Neo4j Algo org.neo4j.graphalgo.GraphAlgoFactory class.

Examples:

the length of the first path found between two nodes

Neo4j::Algo.all_paths(a,b).outgoing(:friends).depth(1).first.length

the nodes in the shortest path between two nodes

Neo4j::Algo.shortest_path(a,b).outgoing(:friends).outgoing(:knows).to_a #=> [node1, node2, node3 ...]

the relationships in the shortest path between two nodes

Neo4j::Algo.shortest_path(a,b).outgoing(:friends).outgoing(:knows).rels.to_a #=> [rel1, rel2, rel3 ...]

The Dijkstra algorithm using a cost evaluator

Neo4j::Algo.dijkstra_path(a,b).cost_evaluator{|rel,direction| rel[:weight]}

Defined Under Namespace

Classes: CostEvaluator, EstimateEvaluator

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Core::ToJava

dir_from_java, dir_to_java, type_to_java, types_to_java

Constructor Details

#initialize(from, to, &factory_proc) ⇒ Algo

:nodoc:



59
60
61
62
63
64
65
 
# File 'lib/neo4j/algo.rb', line 59

def initialize(from, to, &factory_proc) #:nodoc:
  @from          = from
  @to            = to
  @factory_proc  = factory_proc
  @type_and_dirs = []

end

Dynamic Method Handling

This class handles dynamic methods through the method_missing method

#method_missing(m, *args, &block) ⇒ Object

So that one can call directly method on the PathFinder result from an executed algorithm.



187
188
189
 
# File 'lib/neo4j/algo.rb', line 187

def method_missing(m, *args, &block)
  execute_algo.send(m, *args)
end

Class Method Details

.a_star_path(from, to) ⇒ Object

See #a_star_paths, returns the first path found



277
278
279
 
# File 'lib/neo4j/algo.rb', line 277

def self.a_star_path(from, to)
  Algo.new(from, to) { org.neo4j.graphalgo.GraphAlgoFactory.a_star(_expander, _cost_evaluator, _estimate_evaluator) }.single
end

.a_star_paths(from, to) ⇒ Object

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 en.wikipedia.org/wiki/A*_search_algorithm for more information.

Expacts an cost evaluator and estimate evaluator, see Algo#cost_evaluator and Algo#estimate_evaluator

Example:

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



271
272
273
 
# File 'lib/neo4j/algo.rb', line 271

def self.a_star_paths(from, to)
  Algo.new(from, to) { org.neo4j.graphalgo.GraphAlgoFactory.a_star(_expander, _cost_evaluator, _estimate_evaluator) }
end

.all_path(from, to) ⇒ Object

See #all_paths, returns the first path found



216
217
218
 
# File 'lib/neo4j/algo.rb', line 216

def self.all_path(from, to)
  Algo.new(from, to) { org.neo4j.graphalgo.GraphAlgoFactory.all_paths(_expander, _depth) }.single
end

.all_paths(from, to) ⇒ Object

Returns an instance of Neo4j::Algo 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).



211
212
213
 
# File 'lib/neo4j/algo.rb', line 211

def self.all_paths(from, to)
  Algo.new(from, to) { org.neo4j.graphalgo.GraphAlgoFactory.all_paths(_expander, _depth) }
end

.all_simple_path(from, to) ⇒ Object

See #all_simple_paths, returns the first path found



227
228
229
 
# File 'lib/neo4j/algo.rb', line 227

def self.all_simple_path(from, to)
  Algo.new(from, to) { org.neo4j.graphalgo.GraphAlgoFactory.all_simple_paths(_expander, _depth) }.single
end

.all_simple_paths(from, to) ⇒ Object

Returns an instance of Neo4j::Algo 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).



222
223
224
 
# File 'lib/neo4j/algo.rb', line 222

def self.all_simple_paths(from, to)
  Algo.new(from, to) { org.neo4j.graphalgo.GraphAlgoFactory.all_simple_paths(_expander, _depth) }
end

.dijkstra_path(from, to) ⇒ Object

See #dijkstra_paths, returns the first path found



257
258
259
 
# File 'lib/neo4j/algo.rb', line 257

def self.dijkstra_path(from, to)
  Algo.new(from, to) { org.neo4j.graphalgo.GraphAlgoFactory.dijkstra(_expander, _cost_evaluator) }.single
end

.dijkstra_paths(from, to) ⇒ Object

Returns an instance of Neo4j::Algo 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). See en.wikipedia.org/wiki/Dijkstra%27s_algorithm for more information.

Example

Neo4j::Algo.dijkstra_path(node_a,node_b).cost_evaluator{|rel,*| rel[:weight]}.rels



251
252
253
 
# File 'lib/neo4j/algo.rb', line 251

def self.dijkstra_paths(from, to)
  Algo.new(from, to) { org.neo4j.graphalgo.GraphAlgoFactory.dijkstra(_expander, _cost_evaluator) }
end

.shortest_path(from, to) ⇒ Object

See #shortest_paths, returns the first path found



238
239
240
 
# File 'lib/neo4j/algo.rb', line 238

def self.shortest_path(from, to)
  Algo.new(from, to) { org.neo4j.graphalgo.GraphAlgoFactory.shortest_path(_expander, _depth) }.single
end

.shortest_paths(from, to) ⇒ Object

Returns an instance of Neo4j::Algo 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).



233
234
235
 
# File 'lib/neo4j/algo.rb', line 233

def self.shortest_paths(from, to)
  Algo.new(from, to) { org.neo4j.graphalgo.GraphAlgoFactory.shortest_path(_expander, _depth) }
end

.with_length_path(from, to) ⇒ Object

See #with_length_paths, returns the first path found



295
296
297
 
# File 'lib/neo4j/algo.rb', line 295

def self.with_length_path(from,to)
  Algo.new(from, to) { org.neo4j.graphalgo.GraphAlgoFactory.paths_with_length(_expander, _depth) }.single
end

.with_length_paths(from, to) ⇒ Object

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.

Example:

Neo4j::Algo.with_length_paths(node_a,node_b).depth(2).each {|x| puts "Node #{x}"}



289
290
291
 
# File 'lib/neo4j/algo.rb', line 289

def self.with_length_paths(from,to)
  Algo.new(from, to) { org.neo4j.graphalgo.GraphAlgoFactory.paths_with_length(_expander, _depth) }
end

Instance Method Details

#_cost_evaluator ⇒ Object

:nodoc:



77
78
79
80
 
# File 'lib/neo4j/algo.rb', line 77

def _cost_evaluator #:nodoc:
  raise "Algorithm requeries a cost evalulator, use the cost_evaluator to provide one" unless @cost_evaluator
  @cost_evaluator
end

#_depth ⇒ Object

:nodoc:



67
68
69
 
# File 'lib/neo4j/algo.rb', line 67

def _depth #:nodoc:
  @depth || java.lang.Integer::MAX_VALUE
end

#_estimate_evaluator ⇒ Object

:nodoc:



82
83
84
85
 
# File 'lib/neo4j/algo.rb', line 82

def _estimate_evaluator #:nodoc:
  raise "Algorithm requeries a estimate evaluator, use the estimate_evaluator to provide one" unless @estimate_evaluator
  @estimate_evaluator
end

#_expander ⇒ Object

:nodoc:



71
72
73
74
75
 
# File 'lib/neo4j/algo.rb', line 71

def _expander #:nodoc:
  expander = @expander
  expander ||= @type_and_dirs.empty? ? org.neo4j.kernel.Traversal.expanderForAllTypes() : org.neo4j.kernel.Traversal.expanderForTypes(*@type_and_dirs)
  expander
end

#cost_evaluator(&cost_evaluator_proc) ⇒ Object

Specifies a cost evaluator for the algorithm. Only available for the aStar and dijkstra algorithms.

Examples:

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


148
149
150
151
 
# File 'lib/neo4j/algo.rb', line 148

def cost_evaluator(&cost_evaluator_proc)
  @cost_evaluator = CostEvaluator.new(&cost_evaluator_proc)
  self
end

#depth(depth) ⇒ Object

The depth of the traversal Notice not all algorithm uses this argument (aStar and dijkstra)



137
138
139
140
 
# File 'lib/neo4j/algo.rb', line 137

def depth(depth)
  @depth = depth
  self
end

#each(&block) ⇒ Object

:nodoc:



191
192
193
194
195
196
197
198
 
# File 'lib/neo4j/algo.rb', line 191

def each(&block) #:nodoc:
  if @single && @path_finder_method
    execute_algo.send(@path_finder_method).each &block
  else
    traversal = execute_algo
    traversal.each &block if traversal
  end
end

#estimate_evaluator(&estimate_evaluator_proc) ⇒ Object

Specifies an evaluator that returns an (optimistic) estimation of the cost to get from the current node (in the traversal) to the end node. Only available for the aStar algorithm.

The provided proc estimate the weight of the remaining path from one node to another. The proc takes two parameters:

  • node

    the node to estimate the weight from.

  • goal

    the node to estimate the weight to.

The proc should return an estimation of the weight of the path from the first node to the second.

Examples:

Neo4j::Algo.a_star(@x,@y).cost_evaluator{...}.estimate_evaluator{|node,goal| some calculation returning a Float}


166
167
168
169
 
# File 'lib/neo4j/algo.rb', line 166

def estimate_evaluator(&estimate_evaluator_proc)
  @estimate_evaluator = EstimateEvaluator.new(&estimate_evaluator_proc)
  self
end

#execute_algo ⇒ Object

:nodoc:



200
201
202
203
204
205
206
207
 
# File 'lib/neo4j/algo.rb', line 200

def execute_algo #:nodoc:
  instance = self.instance_eval(&@factory_proc)
  if @single
    instance.find_single_path(@from._java_node, @to._java_node)
  else
    instance.find_all_paths(@from._java_node, @to._java_node)
  end
end

#expand(&expander_proc) ⇒ Object

Specifies which relationship should be traversed for the graph algorithm

Examples:

Neo4j::Algo.shortest_path(@x,@y).expand{|node| node._rels(:outgoing, :friends)}

the above is same as:

Neo4j::Algo.shortest_path(@x,@y).outgoing(:friends)

Parameters:

  • expander_proc (Proc) —

    a proc relationship type (symbol)

Returns:

  • self



117
118
119
120
 
# File 'lib/neo4j/algo.rb', line 117

def expand(&expander_proc)
  @expander = (Neo4j::Core::Traversal::RelExpander.create_pair(&expander_proc))
  self
end

#incoming(rel) ⇒ Object

Specifies which incoming relationship should be traversed for the graph algorithm

Parameters:

  • rel (String, Symbol) —

    the relationship type

Returns:

  • self



101
102
103
104
105
 
# File 'lib/neo4j/algo.rb', line 101

def incoming(rel)
  @type_and_dirs << type_to_java(rel)
  @type_and_dirs << dir_to_java(:incoming)
  self
end

#many ⇒ Object

See #single Not sure if this method is useful



131
132
133
 
# File 'lib/neo4j/algo.rb', line 131

def many
  @single = false
end

#nodes ⇒ Object

Specifies that nodes should be returned from as result

See Also:



173
174
175
176
 
# File 'lib/neo4j/algo.rb', line 173

def nodes
  @path_finder_method = :nodes
  self
end

#outgoing(rel) ⇒ Object

Specifies which outgoing relationship should be traversed for the graph algorithm

Parameters:

  • rel (String, Symbol) —

    the relationship type

Returns:

  • self



91
92
93
94
95
 
# File 'lib/neo4j/algo.rb', line 91

def outgoing(rel)
  @type_and_dirs << type_to_java(rel)
  @type_and_dirs << dir_to_java(:outgoing)
  self
end

#rels ⇒ Object

Specifies that relationships should be returned from as result

See Also:



180
181
182
183
 
# File 'lib/neo4j/algo.rb', line 180

def rels
  @path_finder_method = :relationships
  self
end

#single ⇒ Object

If only a single path should be returned, default for some algorithms, like shortest_path



124
125
126
127
 
# File 'lib/neo4j/algo.rb', line 124

def single
  @single = true
  self
end