Module: Pacer::Transform::PathFinder

Includes:
Neo4j2::Algo
Defined in:
lib/pacer-neo4j2/algo.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Instance Attribute Details

#both_labels ⇒ Object

specify one or many edge labels that the path may take in the given direction



238
239
240
 
# File 'lib/pacer-neo4j2/algo.rb', line 238

def both_labels
  @both_labels
end

#cost ⇒ Object

use dijkstra unless the below estimate properties are set

note that cost proc must return a Numeric unless cost_default is set

cost yields: { |edge, direction| [:in, :out, :both].include? direction }



250
251
252
 
# File 'lib/pacer-neo4j2/algo.rb', line 250

def cost
  @cost
end

#cost_default ⇒ Object

use dijkstra unless the below estimate properties are set

note that cost proc must return a Numeric unless cost_default is set

cost yields: { |edge, direction| [:in, :out, :both].include? direction }



250
251
252
 
# File 'lib/pacer-neo4j2/algo.rb', line 250

def cost_default
  @cost_default
end

#cost_property ⇒ Object

use dijkstra unless the below estimate properties are set

note that cost proc must return a Numeric unless cost_default is set

cost yields: { |edge, direction| [:in, :out, :both].include? direction }



250
251
252
 
# File 'lib/pacer-neo4j2/algo.rb', line 250

def cost_property
  @cost_property
end

#cyclical ⇒ Object

Returns the value of attribute cyclical.



289
290
291
 
# File 'lib/pacer-neo4j2/algo.rb', line 289

def cyclical
  @cyclical
end

#estimate ⇒ Object

use the aStar algorithm

note that estimate proc must return a Numeric unless estimate_default is set

estimate yields: { |vertex, goal_vertex| }



264
265
266
 
# File 'lib/pacer-neo4j2/algo.rb', line 264

def estimate
  @estimate
end

#estimate_default ⇒ Object

use the aStar algorithm

note that estimate proc must return a Numeric unless estimate_default is set

estimate yields: { |vertex, goal_vertex| }



264
265
266
 
# File 'lib/pacer-neo4j2/algo.rb', line 264

def estimate_default
  @estimate_default
end

#expander ⇒ Object

note that expander procs must return edge(s) that are connected to the end_v of the given path

expander yields: { |path, state| path.is_a? Pacer::Neo4j2::Algo::PathWrapper }



243
244
245
 
# File 'lib/pacer-neo4j2/algo.rb', line 243

def expander
  @expander
end

#find_all ⇒ Object

Possible values:



288
289
290
 
# File 'lib/pacer-neo4j2/algo.rb', line 288

def find_all
  @find_all
end

#forward ⇒ Object

note that expander procs must return edge(s) that are connected to the end_v of the given path

expander yields: { |path, state| path.is_a? Pacer::Neo4j2::Algo::PathWrapper }



243
244
245
 
# File 'lib/pacer-neo4j2/algo.rb', line 243

def forward
  @forward
end

#in_labels ⇒ Object

specify one or many edge labels that the path may take in the given direction



238
239
240
 
# File 'lib/pacer-neo4j2/algo.rb', line 238

def in_labels
  @in_labels
end

#lat_property ⇒ Object

use the aStar algorithm

note that estimate proc must return a Numeric unless estimate_default is set

estimate yields: { |vertex, goal_vertex| }



264
265
266
 
# File 'lib/pacer-neo4j2/algo.rb', line 264

def lat_property
  @lat_property
end

#length ⇒ Object

use pathsWithLength

Return only paths of the given length



276
277
278
 
# File 'lib/pacer-neo4j2/algo.rb', line 276

def length
  @length
end

#long_property ⇒ Object

use the aStar algorithm

note that estimate proc must return a Numeric unless estimate_default is set

estimate yields: { |vertex, goal_vertex| }



264
265
266
 
# File 'lib/pacer-neo4j2/algo.rb', line 264

def long_property
  @long_property
end

#max_depth ⇒ Object 



280
281
282
 
# File 'lib/pacer-neo4j2/algo.rb', line 280

def max_depth
  @max_depth || 5
end

#max_hits ⇒ Object

use shortestPath



285
286
287
 
# File 'lib/pacer-neo4j2/algo.rb', line 285

def max_hits
  @max_hits
end

#out_labels ⇒ Object

specify one or many edge labels that the path may take in the given direction



238
239
240
 
# File 'lib/pacer-neo4j2/algo.rb', line 238

def out_labels
  @out_labels
end

#reverse ⇒ Object

note that expander procs must return edge(s) that are connected to the end_v of the given path

expander yields: { |path, state| path.is_a? Pacer::Neo4j2::Algo::PathWrapper }



243
244
245
 
# File 'lib/pacer-neo4j2/algo.rb', line 243

def reverse
  @reverse
end

#target ⇒ Object

Returns the value of attribute target.



235
236
237
 
# File 'lib/pacer-neo4j2/algo.rb', line 235

def target
  @target
end

Instance Method Details

#after_initialize ⇒ Object 



34
35
36
 
# File 'lib/pacer-neo4j2/algo.rb', line 34

def after_initialize
  fail Pacer::ClientError, 'graph must be neo4j' unless graph.vendor == 'neo4j'
end

#help(opt = nil) ⇒ Object 



38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
 
# File 'lib/pacer-neo4j2/algo.rb', line 38

def help(opt = nil)
  case opt
when nil
  puts <<HELP
Finds paths between pairs of vertices. The algorithm used depends on the
options specified. All supported path finding algorithms including in Neo4j 1.8
are included, and all of their documented usages are possible.

USAGE:

vertices.path_to(targets, options = {})
    Find the first path from each vertex to each target vertex

vertices.paths_to(targets, options = {})
    Find multiple paths from each vertex to each target vertex

paths.expand(options = {})
    Find multiple paths from the first vertex in each path to the last vertex
    in each path.

All options are optional!

These methods only work on Neo4j graphs.

More details:

help :options      for simple path algorithms and other options
  find_all, cyclical, length, max_depth, max_hits

help :cost         for Dijkstra and aStar
  cost, cost_property, cost_default

help :estimate     for aStar
  estimate, estimate_default, lat_property, long_property

help :expansion    customize how any path is expanded
  in_labels, out_labels, both_labels, expander, forward, reverse

HELP
when :path
  puts <<HELP
Details for path:         expander: proc { |path, state| edges }

#end_v        Returns the end vertex of this path.
#start_v      Returns the start vertex of this path.
#length       Returns the length of this path.
#path         Iterates through both the vertices and edges of this path in
        order.
#end_e        Returns the last edge in this path.
#v            Returns all the vertices in this path starting from the start
        vertex going forward towards the end vertex.
#e            Returns all the edges in between the vertices which this path
        consists of.
#reverse_v    Like #v but reversed.
#reverse_e    Like #e but reversed.

The following methods all proxy to the vertex returned by #end_v: and behave
exactly like standard Pacer Vertex methods.

The iterators can be combined with the + operator.

Fast edge iterators:
  #out_edges(*args)
  #in_edges(*args)
  #both_edges(*args)

Fast vertex iterators:
  #out_vertices(*args)
  #in_vertices(*args)
  #both_vertices(*args)

Edge routes:
  #out_e(*args)
  #in_e(*args)
  #both_e(*args)

Vertex routes:
  #out(*args)
  #in(*args)
  #both(*args)

HELP
when :expansion
  puts <<HELP
Path expansion options:

  By default, all edges will be followed. By specifying expansion rules you can
  limit which paths are attempted. All algorithms use the same expanders so
  these options do not effect the algorithm selection.

  in_labels: label | [labels]    only follow : in edges  : with the given label(s)
  out_labels:                                : out edges :
  both_labels:                               : edges     :
These options can be combined.

  Expanders search forward from the start vertex and backwards from the target
  vertex. Either expander

  expander: Proc | PathExpander   Custom rule for forward search
If no reverse is specified, will be used for reverse too.
  forward:                        synonym for the expander option
  reverse:  Proc | PathExpander   Custom rule for the reverse search

proc { |path, state| edges }:
  path is a Pacer::Neo4j2::Algo::PathWrapper - help(:path) for details
  The proc must simply return an Enumerable of edges that the

HELP
when :options
  puts <<HELP
Simple options:

  find_all: Boolean    Find all non-cyclical paths.
Algorithm: allSimplePaths

  cyclical: Boolean    Find all paths including cyclical ones.
Algorithm: allPaths

  length: Number       Number of edges that the path contains.
Algorithm: pathsWithLength
Returns only paths of the specified length.

  max_depth: Number    Number of edges to search in a potential path.
Default: 5
Limits how many edges will be traversed searching for a path. Higher
numbers can take exponentially longer, I think.  Does not apply to aStar,
Dijkstra, or pathsWithLength algorithms.

Required for find_all, cyclical, and shortest path algorithms.

  max_hits: Number     Maximum number of paths to find for each pair of vertices.
#path_to defaults this to 1. All algorithms use this but only
some support it natively in Neo4j's implementations.


HELP
when :cost
  puts <<HELP
Cost options:

  Specifying these chooses the Dijkstra algorithm unless an estimate is also
  specified.

  cost: Proc | CostEvaluator   Calculate the cost for this edge.
Must return a Numeric unless cost_default is set.
proc { |edge, direction| Float }:
  direction is either :in or :out.

  cost_property: String        get the cost from the given edge property
  cost_default: Float          default if the property isn't there

HELP
when :estimate
  puts <<HELP
Estimate options
  Specifying these together with cost chooses the a* / aStar algorithm.

  estimate:
Must return a Numeric unless estimate_default is set.
proc { |vertex, goal_vertex| Float }

  estimate_default: Float   only works with the proc estimate

  lat_property: String      latitude property name
  long_property: String     longitude property name
Use latitude and longitude if all estimated vertices have the necessary
properties.

HELP
else
  super
end
  description
end

#method ⇒ Object 



213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
 
# File 'lib/pacer-neo4j2/algo.rb', line 213

def method
  if has_cost?
    if has_estimate?
      :aStar
    else
      :dijkstra
    end
  elsif cyclical and max_depth
    :all
  elsif find_all and max_depth
    :all_simple
  elsif length
    :with_length
  elsif max_depth
    if max_hits
      :shortest_with_max_hits
    else
      :shortest
    end
  end
end

#set_cost(property = nil, default = nil, &block) ⇒ Object 



252
253
254
255
256
257
 
# File 'lib/pacer-neo4j2/algo.rb', line 252

def set_cost(property = nil, default = nil, &block)
  self.cost_property = property
  self.cost_default = default
  self.cost = block
  self
end

#set_estimate(lat = nil, long = nil, &block) ⇒ Object 



266
267
268
269
270
271
 
# File 'lib/pacer-neo4j2/algo.rb', line 266

def set_estimate(lat = nil, long = nil, &block)
  self.lat_property = lat
  self.long_property = long
  self.estimate = block
  self
end