Module: Plexus::Search

Included in:
DirectedGraphBuilder::Algorithms, UndirectedGraphBuilder::Algorithms
Defined in:
lib/plexus/search.rb

Overview

**Search/traversal algorithms.**

This module defines a collection of search/traversal algorithms, in a unified API. Read through the doc to get familiar with the calling pattern.

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 is the 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` which, 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` instead of an option hash is specified, it defines `:enter_vertex`.

Each search algorithm 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
=> [1, 2, 3, 4]

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 



363
364
365
366
367
368
369
 
# File 'lib/plexus/search.rb', line 363

def method_missing(sym, *args, &block)
  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) 


499
500
501
 
# File 'lib/plexus/search.rb', line 499

def acyclic?
  topsort.size == size
end

#astar(start, goal, func, options, &block) ⇒ Array(vertices), ...

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

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`.

See also: [A* search algorithm](en.wikipedia.org/wiki/A*_search_algorithm) on Wikipedia.

Parameters:

  • start (vertex) —

    the starting vertex for the search

  • goal (vertex) —

    the vertex to reach

  • func (Proc) —

    heuristic weight computing process

  • options (Hash)

Returns:

  • (Array(vertices), call, nil) —

    an array of nodes in path, or calls block on all nodes, upon failure returns ‘nil`



288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
 
# File 'lib/plexus/search.rb', line 288

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 the 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) ⇒ Array(vertices), ...

‘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 as the zero element for the `+` operation performed on the objects used in the computation of cost.

Parameters:

  • start (vertex) —

    the starting vertex for the search

  • goal (vertex) —

    the vertex to reach

  • func (Proc) —

    heuristic weight computing process

  • options (Hash)
  • zero (Integer) (defaults to: 0) —

    (0)

Returns:

  • (Array(vertices), call, nil) —

    an array of nodes in path, or calls block on all nodes, upon failure returns ‘nil`



356
357
358
359
 
# File 'lib/plexus/search.rb', line 356

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 Also known as: bread_first_search

Performs a breadth-first search.

Parameters:

  • options (Hash) (defaults to: {}) 


72
73
74
 
# File 'lib/plexus/search.rb', line 72

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

#bfs_spanning_forest(start) ⇒ Array

Returns the bfs spanning forest for the given start node, see spanning_forest.

Parameters:

  • start (vertex)

Returns:

  • (Array) —

    predecessors and root nodes



112
113
114
 
# File 'lib/plexus/search.rb', line 112

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

#bfs_tree_from_vertex(start) ⇒ Hash

Returns a hash of predecessors for the breadth-first search tree rooted at the given node.

Parameters:

  • start (Proc)

Returns:

  • (Hash) —

    predecessors vertices



145
146
147
 
# File 'lib/plexus/search.rb', line 145

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) 


506
507
508
 
# File 'lib/plexus/search.rb', line 506

def cyclic?
  not acyclic?
end

#dfs(options = {}, &block) ⇒ Object Also known as: depth_first_search

Performs a depth-first search.

Parameters:

  • options (Hash) (defaults to: {}) 


80
81
82
 
# File 'lib/plexus/search.rb', line 80

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

#dfs_spanning_forest(start) ⇒ Array

Returns the dfs spanning forest for the given start node, see spanning_forest.

Parameters:

  • start (vertex)

Returns:

  • (Array) —

    predecessors and root nodes



104
105
106
 
# File 'lib/plexus/search.rb', line 104

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

#dfs_tree_from_vertex(start) ⇒ Hash

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

Parameters:

  • start (vertex)

Returns:

  • (Hash) —

    predecessors vertices



137
138
139
 
# File 'lib/plexus/search.rb', line 137

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

#lexicograph_bfs(&block) ⇒ vertex

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.

Returns:

  • (vertex) 


226
227
228
229
230
231
232
233
234
235
236
 
# File 'lib/plexus/search.rb', line 226

def lexicograph_bfs(&block)
  lex_q = Plexus::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 



362
 
# File 'lib/plexus/search.rb', line 362

alias_method :pre_search_method_missing, :method_missing

#sort(start = nil, &block) ⇒ Array

Does a top sort, but trudges forward if a cycle occurs. Use with caution.

Parameters:

  • start (vertex) (defaults to: nil) —

    (nil) the start vertex (nil will fallback on the first vertex inserted within the graph)

Returns:

  • (Array) —

    a linear representation of the sorted graph



487
488
489
490
491
492
493
494
 
# File 'lib/plexus/search.rb', line 487

def sort(start = nil, &block)
  result  = []
  push    = Proc.new { |v| result.unshift(v) }
  start ||= vertices[0]
  dfs({ :exit_vertex => push, :start => start })
  result.each { |v| block.call(v) } if block
  result
end

#spanning_forest(start, routine) ⇒ Array

Routine which computes a spanning forest for the given search method. Returns two values: a hash of predecessors and an array of root nodes.

Parameters:

  • start (vertex)
  • routine (Symbol) —

    the search method (‘:dfs`, `:bfs`)

Returns:

  • (Array) —

    predecessors and root nodes



91
92
93
94
95
96
97
98
 
# File 'lib/plexus/search.rb', line 91

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) ⇒ Array

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 can be used directly as it will return the result as an Array.

Parameters:

  • start (vertex) (defaults to: nil) —

    (nil) the start vertex (nil will fallback on the first vertex inserted within the graph)

Returns:

  • (Array) —

    a linear representation of the sorted graph



471
472
473
474
475
476
477
478
479
480
 
# File 'lib/plexus/search.rb', line 471

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) ⇒ Hash

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 containing 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.

Parameters:

  • start (vertex)
  • routine (Symbol) —

    the search method (‘:dfs`, `:bfs`)

Returns:

  • (Hash) —

    predecessors vertices



124
125
126
127
128
129
130
131
 
# File 'lib/plexus/search.rb', line 124

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