Module: GRATR::Graph::Search

Included in:
Digraph, UndirectedGraph
Defined in:
lib/gratr/search.rb

Defined Under Namespace

Classes: LexicographicQueue

Instance Method Summary collapse

Dynamic Method Handling

This class handles dynamic methods through the method_missing method

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

:nodoc:



318
319
320
321
322
323
324
 
# File 'lib/gratr/search.rb', line 318

def method_missing(sym,*args, &block) # :nodoc:
  m1=/^dfs_(\w+)$/.match(sym.to_s)
  dfs((args[0] || {}).merge({m1.captures[0].to_sym => block})) if m1
  m2=/^bfs_(\w+)$/.match(sym.to_s)
  bfs((args[0] || {}).merge({m2.captures[0].to_sym => block})) if m2
  pre_search_method_missing(sym, *args, &block) unless m1 or m2
end

Instance Method Details

#acyclic? ⇒ Boolean

Returns true if a graph contains no cycles, false otherwise

Returns:

  • (Boolean) 


414
 
# File 'lib/gratr/search.rb', line 414

def acyclic?() topsort.size == size; end

#astar(start, goal, func, options, &block) ⇒ Object

A* Heuristic best first search

start is the starting vertex for the search

func is a Proc that when passed a vertex returns the heuristic 

weight of sending the path through that node. It must always
be equal to or less than the true cost

options are mostly callbacks passed in as a hash, the default block is :discover_vertex and weight is assumed to be the label for the Arc. The following options are valid, anything else is ignored.

  • :weight => can be a Proc, or anything else is accessed using the [] for the

    the label or it defaults to using
the value stored in the label for the Arc. If it is a Proc it will 
pass the edge to the proc and use the resulting value.

  • :discover_vertex => Proc invoked when a vertex is first discovered and is added to the open list.

  • :examine_vertex => Proc invoked when a vertex is popped from the queue (i.e., it has the lowest cost on the open list).

  • :examine_edge => Proc invoked on each out-edge of a vertex immediately after it is examined.

  • :edge_relaxed => Proc invoked on edge (u,v) if d + w(u,v) < d.

  • :edge_not_relaxed=> Proc invoked if the edge is not relaxed (see above).

  • :black_target => Proc invoked when a vertex that is on the closed 

    list is "rediscovered" via a more efficient path, and is re-added
to the OPEN list.

  • :finish_vertex => Proc invoked on a vertex when it is added to the 

    closed list, which happens after all of its out edges have been
examined.

Returns array of nodes in path, or calls block on all nodes, upon failure returns nil

Can also be called like astar_examine_edge {|e| … } or astar_edge_relaxed {|e| … } for any of the callbacks

The criteria for expanding a vertex on the open list is that it has the lowest f(v) = g(v) + h(v) value of all vertices on open.

The time complexity of A* depends on the heuristic. It is exponential in the worst case, but is polynomial when the heuristic function h meets the following condition: |h(x) - h*(x)| < O(log h*(x)) where h*

is the optimal heuristic, i.e. the exact cost to get from x to the goal.

Also see: en.wikipedia.org/wiki/A-star_search_algorithm



253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
 
# File 'lib/gratr/search.rb', line 253

def astar(start, goal, func, options, &block)
  options.instance_eval "def handle_callback(sym,u) self[sym].call(u) if self[sym]; end"
   
  # Initialize
  d = { start => 0 }
  
  color = {start => :gray} # Open is :gray, Closed is :black
  parent = Hash.new {|k| parent[k] = k}
  f = {start => func.call(start)}
  queue = PriorityQueue.new.push(start,f[start])
  block.call(start) if block
  
  # Process queue
  until queue.empty?
    u,dummy = queue.delete_min
    options.handle_callback(:examine_vertex, u)

    # Unravel solution if goal is reached.
    if u == goal
      solution = [goal]
      while u != start
        solution << parent[u]; u = parent[u]
      end
      return solution.reverse
    end

    adjacent(u, :type => :edges).each do |e|
      v = e.source == u ? e.target : e.source
      options.handle_callback(:examine_edge, e)
      w = cost(e, options[:weight])
      raise ArgumentError unless w
      if d[v].nil? or (w + d[u]) < d[v] 
        options.handle_callback(:edge_relaxed, e)
        d[v] = w + d[u]
        f[v] = d[v] + func.call(v)
        parent[v] = u
        unless color[v] == :gray
          options.handle_callback(:black_target, v) if color[v] == :black
          color[v] = :gray 
          options.handle_callback(:discover_vertex, v)
          queue.push v, f[v] 
          block.call(v) if block
        end
      else
        options.handle_callback(:edge_not_relaxed, e)
      end
    end # adjacent(u)
    color[u] = :black
    options.handle_callback(:finish_vertex,u)
  end # queue.empty?
          
  nil # failure, on fall through

end

#best_first(start, goal, options, zero = 0, &block) ⇒ Object

Best first has all the same options as astar with func set to h(v) = 0. There is an additional option zero which should be defined to zero for the operation ‘+’ on the objects used in the computation of cost. The parameter zero defaults to 0.



312
313
314
315
 
# File 'lib/gratr/search.rb', line 312

def best_first(start, goal, options, zero=0, &block)
  func = Proc.new {|v| zero}   
  astar(start, goal, func, options, &block)
end

#bfs(options = {}, &block) ⇒ Object

Options are mostly callbacks passed in as a hash. The following are valid, anything else is ignored :enter_vertex => Proc Called upon entry of a vertex :exit_vertex => Proc Called upon exit of a vertex :root_vertex => Proc Called when a vertex the a root of a tree :start_vertex => Proc Called for the first vertex of the search :examine_edge => Proc Called when an edge is examined :tree_edge => Proc Called when the edge is a member of the tree :back_edge => Proc Called when the edge is a back edge :forward_edge => Proc Called when the edge is a forward edge :adjacent => Proc that given a vertex returns adjacent nodes, defaults to adjacent call of graph useful for changing the definition of adjacent in some algorithms

:start => Vertex Specifies the vertex to start search from

If a &block is specified it defaults to :enter_vertex

Returns the list of vertexes as reached by enter_vertex This allows for calls like, g.bfs.each {|v| …}

Can also be called like bfs_examine_edge {|e| … } or dfs_back_edge {|e| … } for any of the callbacks

A full example usage is as follows:

ev = Proc.new {|x| puts "Enter Vertex #{x}"}
xv = Proc.new {|x| puts "Exit Vertex #{x}"}
sv = Proc.new {|x| puts "Start Vertex #{x}"}
ee = Proc.new {|x| puts "Examine Arc #{x}"}
te = Proc.new {|x| puts "Tree Arc #{x}"}
be = Proc.new {|x| puts "Back Arc #{x}"}
fe = Proc.new {|x| puts "Forward Arc #{x}"}
Digraph[1,2,2,3,3,4].dfs({ 
      :enter_vertex => ev, 
      :exit_vertex  => xv,
      :start_vertex => sv,
      :examine_edge => ee,
      :tree_edge    => te,
      :back_edge    => be,
      :forward_edge => fe })

Which outputs:

Start Vertex 1 Enter Vertex 1 Examine Arc (1=2) Tree Arc (1=2) Enter Vertex 2 Examine Arc (2=3) Tree Arc (2=3) Enter Vertex 3 Examine Arc (3=4) Tree Arc (3=4) Enter Vertex 4 Examine Arc (1=4) Back Arc (1=4) Exit Vertex 4 Exit Vertex 3 Exit Vertex 2 Exit Vertex 1



92
 
# File 'lib/gratr/search.rb', line 92

def bfs(options={}, &block) gratr_search_helper(:shift, options, &block); end

#bfs_spanning_forest(start) ⇒ Object

Return the bfs spanning forest for the given start node, see spanning_forest



112
 
# File 'lib/gratr/search.rb', line 112

def bfs_spanning_forest(start) spanning_forest(start, :bfs); end

#bfs_tree_from_vertex(start) ⇒ Object

Returns a hash of predecessors for the depth first search tree rooted at the given node



130
 
# File 'lib/gratr/search.rb', line 130

def bfs_tree_from_vertex(start) tree_from_vertex(start, :bfs); end

#cyclic? ⇒ Boolean

Returns false if a graph contains no cycles, true otherwise

Returns:

  • (Boolean) 


417
 
# File 'lib/gratr/search.rb', line 417

def cyclic?()  not acyclic?; end

#dfs(options = {}, &block) ⇒ Object

See options for bfs method



95
 
# File 'lib/gratr/search.rb', line 95

def dfs(options={}, &block) gratr_search_helper(:pop,   options, &block); end

#dfs_spanning_forest(start) ⇒ Object

Return the dfs spanning forest for the given start node, see spanning_forest



109
 
# File 'lib/gratr/search.rb', line 109

def dfs_spanning_forest(start) spanning_forest(start, :dfs); end

#dfs_tree_from_vertex(start) ⇒ Object

Returns a hash of predecessors for the depth first search tree rooted at the given node



127
 
# File 'lib/gratr/search.rb', line 127

def dfs_tree_from_vertex(start) tree_from_vertex(start, :dfs); end

#lexicograph_bfs(&block) ⇒ Object

Lexicographic breadth-first search, the usual queue of vertices is replaced by a queue of unordered subsets of the vertices, which is sometimes refined but never reordered.

Originally developed by Rose, Tarjan, and Leuker, “Algorithmic aspects of vertex elimination on graphs”, SIAM J. Comput. 5, 266-283 MR53 #12077

Implementation taken from Golumbic’s, “Algorithmic Graph Theory and Perfect Graphs” pg, 84-90



193
194
195
196
197
198
199
200
201
202
203
 
# File 'lib/gratr/search.rb', line 193

def lexicograph_bfs(&block)
  lex_q = GRATR::Graph::Search::LexicographicQueue.new(vertices)
  result = []
  num_vertices.times do               
    v = lex_q.pop
    result.unshift(v)
    lex_q.add_lexeme(adjacent(v))            
  end
  result.each {|r| block.call(r)} if block
  result
end

#pre_search_method_missing ⇒ Object

:nodoc:



317
 
# File 'lib/gratr/search.rb', line 317

alias_method :pre_search_method_missing, :method_missing

#spanning_forest(start, routine) ⇒ Object

Routine to compute a spanning forest for the given search method Returns two values, first is a hash of predecessors and second an array of root nodes



99
100
101
102
103
104
105
106
 
# File 'lib/gratr/search.rb', line 99

def spanning_forest(start, routine)
  predecessor = {}
  roots       = []
  te = Proc.new {|e| predecessor[e.target] = e.source}
  rv = Proc.new {|v| roots << v}
  send routine, :start => start, :tree_edge => te, :root_vertex => rv
  [predecessor, roots]
end

#topsort(start = nil, &block) ⇒ Object

Topological Sort Iterator

The topological sort algorithm creates a linear ordering of the vertices such that if edge (u,v) appears in the graph, then u comes before v in the ordering. The graph must be a directed acyclic graph (DAG).

The iterator can also be applied to undirected graph or to a DG graph which contains a cycle. In this case, the Iterator does not reach all vertices. The implementation of acyclic? and cyclic? uses this fact.

Can be called with a block as a standard Ruby iterator, or it can be used directly as it will return the result as an Array



403
404
405
406
407
408
409
410
411
 
# File 'lib/gratr/search.rb', line 403

def topsort(start = nil, &block)
  result  = []
  go      = true 
  back    = Proc.new {|e| go = false } 
  push    = Proc.new {|v| result.unshift(v) if go}
  start   ||= vertices[0]
  dfs({:exit_vertex => push, :back_edge => back, :start => start})
  result.each {|v| block.call(v)} if block; result
end

#tree_from_vertex(start, routine) ⇒ Object

Returns a hash of predecessors in a tree rooted at the start node. If this is a connected graph then it will be a spanning tree and contain all vertices. An easier way to tell if it’s a spanning tree is to use a spanning_forest call and check if there is a single root node.



117
118
119
120
121
122
123
124
 
# File 'lib/gratr/search.rb', line 117

def tree_from_vertex(start, routine)
  predecessor={}
  correct_tree = false
  te = Proc.new {|e| predecessor[e.target] = e.source if correct_tree}
  rv = Proc.new {|v| correct_tree = (v == start)}
  send routine, :start => start, :tree_edge => te, :root_vertex => rv
  predecessor       
end