Module: GRATR::Graph::Search
 Included in:
 Digraph, UndirectedGraph
 Defined in:
 lib/gratr/search.rb
Defined Under Namespace
Classes: LexicographicQueue
Instance Method Summary (collapse)

 (Boolean) acyclic?
Returns true if a graph contains no cycles, false otherwise.

 (Object) astar(start, goal, func, options, &block)
A* Heuristic best first search.

 (Object) best_first(start, goal, options, zero = 0, &block)
Best first has all the same options as astar with func set to h(v) = 0.

 (Object) bfs(options = {}, &block)
Options are mostly callbacks passed in as a hash.

 (Object) bfs_spanning_forest(start)
Return the bfs spanning forest for the given start node, see spanning_forest.

 (Object) bfs_tree_from_vertex(start)
Returns a hash of predecessors for the depth first search tree rooted at the given node.

 (Boolean) cyclic?
Returns false if a graph contains no cycles, true otherwise.

 (Object) dfs(options = {}, &block)
See options for bfs method.

 (Object) dfs_spanning_forest(start)
Return the dfs spanning forest for the given start node, see spanning_forest.

 (Object) dfs_tree_from_vertex(start)
Returns a hash of predecessors for the depth first search tree rooted at the given node.

 (Object) lexicograph_bfs(&block)
Lexicographic breadthfirst search, the usual queue of vertices is replaced by a queue of unordered subsets of the vertices, which is sometimes refined but never reordered.

 (Object) method_missing(sym, *args, &block)
:nodoc:.

 (Object) pre_search_method_missing
:nodoc:.

 (Object) spanning_forest(start, routine)
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.

 (Object) topsort(start = nil, &block)
Topological Sort Iterator.

 (Object) tree_from_vertex(start, routine)
Returns a hash of predecessors in a tree rooted at the start node.
Dynamic Method Handling
This class handles dynamic methods through the method_missing method
 (Object) method_missing(sym, *args, &block)
: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
 (Boolean) acyclic?
Returns true if a graph contains no cycles, false otherwise
414 
# File 'lib/gratr/search.rb', line 414 def acyclic?() topsort.size == size; end 
 (Object) astar(start, goal, func, options, &block)
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 outedge 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 readded 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.
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, , &block) .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 .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 .handle_callback(:examine_edge, e) w = cost(e, [:weight]) raise ArgumentError unless w if d[v].nil? or (w + d[u]) < d[v] .handle_callback(:edge_relaxed, e) d[v] = w + d[u] f[v] = d[v] + func.call(v) parent[v] = u unless color[v] == :gray .handle_callback(:black_target, v) if color[v] == :black color[v] = :gray .handle_callback(:discover_vertex, v) queue.push v, f[v] block.call(v) if block end else .handle_callback(:edge_not_relaxed, e) end end # adjacent(u) color[u] = :black .handle_callback(:finish_vertex,u) end # queue.empty? nil # failure, on fall through end 
 (Object) best_first(start, goal, options, zero = 0, &block)
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, , zero=0, &block) func = Proc.new {v zero} astar(start, goal, func, , &block) end 
 (Object) bfs(options = {}, &block)
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(={}, &block) gratr_search_helper(:shift, , &block); end 
 (Object) bfs_spanning_forest(start)
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 
 (Object) bfs_tree_from_vertex(start)
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 
 (Boolean) cyclic?
Returns false if a graph contains no cycles, true otherwise
417 
# File 'lib/gratr/search.rb', line 417 def cyclic?() not acyclic?; end 
 (Object) dfs(options = {}, &block)
See options for bfs method
95 
# File 'lib/gratr/search.rb', line 95 def dfs(={}, &block) gratr_search_helper(:pop, , &block); end 
 (Object) dfs_spanning_forest(start)
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 
 (Object) dfs_tree_from_vertex(start)
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 
 (Object) lexicograph_bfs(&block)
Lexicographic breadthfirst 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, 266283 MR53 #12077
Implementation taken from Golumbic's, “Algorithmic Graph Theory and Perfect Graphs” pg, 8490
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 
 (Object) pre_search_method_missing
:nodoc:
317 
# File 'lib/gratr/search.rb', line 317 alias_method :pre_search_method_missing, :method_missing 
 (Object) spanning_forest(start, routine)
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 
 (Object) topsort(start = nil, &block)
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 
 (Object) tree_from_vertex(start, routine)
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 