#-- # Copyright (c) 2006 Shawn Patrick Garbett # Copyright (c) 2002,2004,2005 by Horst Duchene # # Redistribution and use in source and binary forms, with or without modification, # are permitted provided that the following conditions are met: # # * Redistributions of source code must retain the above copyright notice(s), # this list of conditions and the following disclaimer. # * Redistributions in binary form must reproduce the above copyright notice, # this list of conditions and the following disclaimer in the documentation # and/or other materials provided with the distribution. # * Neither the name of the Shawn Garbett nor the names of its contributors # may be used to endorse or promote products derived from this software # without specific prior written permission. # # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND # ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED # WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE # DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE # FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL # DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR # SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER # CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, # OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #++ module GRATR module Graph module Search # 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 def bfs(options={}, &block) gratr_search_helper(:shift, options, &block); end # See options for bfs method def dfs(options={}, &block) gratr_search_helper(:pop, options, &block); end # 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 def spanning_forest(start, routine) predecessor = {} roots = [] te = Proc.new {|e| predecessor[e.target] = e.source} rv = Proc.new {|v| roots << v} method(routine).call :start => start, :tree_edge => te, :root_vertex => rv [predecessor, roots] end # Return the dfs spanning forest for the given start node, see spanning_forest def dfs_spanning_forest(start) spanning_forest(start, :dfs); end # Return the bfs spanning forest for the given start node, see spanning_forest def bfs_spanning_forest(start) spanning_forest(start, :bfs); end # 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. 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)} method(routine).call :start => start, :tree_edge => te, :root_vertex => rv predecessor end # Returns a hash of predecessors for the depth first search tree rooted at the given node def dfs_tree_from_vertex(start) tree_from_vertex(start, :dfs); end # Returns a hash of predecessors for the depth first search tree rooted at the given node def bfs_tree_from_vertex(start) tree_from_vertex(start, :bfs); end # An inner class used for greater efficiency in lexicograph_bfs # # Original desgn taken from Golumbic's, "Algorithmic Graph Theory and # Perfect Graphs" pg, 87-89 class LexicographicQueue # Called with the initial values (array) def initialize(values) @node = Struct.new(:back, :forward, :data) @node.class_eval { def hash() @hash; end; @@cnt=0 } @set = {} @tail = @node.new(nil, nil, Array.new(values)) @tail.instance_eval { @hash = (@@cnt+=1) } values.each {|a| @set[a] = @tail} end # Pop an entry with maximum lexical value from queue def pop() return nil unless @tail value = @tail[:data].pop @tail = @tail[:forward] while @tail and @tail[:data].size == 0 @set.delete(value); value end # Increase lexical value of given values (array) def add_lexeme(values) fix = {} values.select {|v| @set[v]}.each do |w| sw = @set[w] if fix[sw] s_prime = sw[:back] else s_prime = @node.new(sw[:back], sw, []) s_prime.instance_eval { @hash = (@@cnt+=1) } @tail = s_prime if @tail == sw sw[:back][:forward] = s_prime if sw[:back] sw[:back] = s_prime fix[sw] = true end s_prime[:data] << w sw[:data].delete(w) @set[w] = s_prime end fix.keys.select {|n| n[:data].size == 0}.each do |e| e[:forward][:back] = e[:back] if e[:forward] e[:back][:forward] = e[:forward] if e[:back] end end end # 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 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 # 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[u] + w(u,v) < d[v]. # * :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: http://en.wikipedia.org/wiki/A-star_search_algorithm # def astar(start, goal, func, options, &block) options.instance_eval "def handle_vertex(sym,u) self[sym].call(u) if self[sym]; end" options.instance_eval "def handle_edge(sym,u,v) self[sym].call(#{edge_class}[u,v]) if self[sym]; end" d = { start => 0 } f = { start => func.call(start) } color = {start => :gray} p = Hash.new {|k| p[k] = k} queue = [start] block.call(start) if block until queue.empty? u = queue.pop options.handle_vertex(:examine_vertex, u) adjacent(u).each do |v| e = edge_class[u,v] options.handle_edge(:examine_edge, u, v) w = cost(e, options[:weight]) raise ArgumentError unless w if d[v].nil? or (w + d[u]) < d[v] options.handle_edge(:edge_relaxed, u, v) d[v] = w + d[u] f[v] = d[v] + func.call(u) p[v] = u unless color[v] == :gray options.handle_vertex(:black_target, v) if color[v] == :black color[v] = :gray options.handle_vertex(:discover_vertex, v) queue << v block.call(v) if block return [start]+queue if v == goal end else options.handle_edge(:edge_not_relaxed, u, v) end end # adjacent(u) color[u] = :black options.handle_vertex(:finish_vertex,u) end # queue.empty? nil # failure, on fall through end # astar # 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. def best_first(start, goal, options, zero=0, &block) func = Proc.new {|v| zero} astar(start, goal, func, options, &block) end alias_method :pre_search_method_missing, :method_missing # :nodoc: 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 private def gratr_search_helper(op, options={}, &block) # :nodoc: return nil if size == 0 result = [] # Create options hash that handles callbacks options = {:enter_vertex => block, :start => to_a[0]}.merge(options) options.instance_eval "def handle_vertex(sym,u) self[sym].call(u) if self[sym]; end" options.instance_eval "def handle_edge(sym,e) self[sym].call(e) if self[sym]; end" # Create waiting list that is a queue or stack depending on op specified. # First entry is the start vertex. waiting = [options[:start]] waiting.instance_eval "def next() #{op.to_s}; end" # Create color map with all set to unvisited except for start vertex # will be set to waiting color_map = vertices.inject({}) {|a,v| a[v] = :unvisited; a} color_map.merge!(waiting[0] => :waiting) options.handle_vertex(:start_vertex, waiting[0]) options.handle_vertex(:root_vertex, waiting[0]) # Perform the actual search until nothing is waiting until waiting.empty? # Loop till the search iterator exhausts the waiting list visited_edges={} # This prevents retraversing edges in undirected graphs until waiting.empty? gratr_search_iteration(options, waiting, color_map, visited_edges, result, op == :pop) end # Waiting list is exhausted, see if a new root vertex is available u=color_map.detect {|key,value| value == :unvisited} waiting.push(u[0]) if u options.handle_vertex(:root_vertex, u[0]) if u end; result end def gratr_search_iteration(options, waiting, color_map, visited_edges, result, recursive=false) # :nodoc: # Get the next waiting vertex in the list u = waiting.next options.handle_vertex(:enter_vertex,u) result << u # Examine all adjacent outgoing edges, not previously traversed adj_proc = options[:adjacent] || self.method(:adjacent).to_proc adj_proc.call(u,:type => :edges, :direction => :out).reject {|w| visited_edges[w]}.each do |e| e = e.reverse unless directed? or e.source == u # Preserves directionality where required v = e.target options.handle_edge(:examine_edge, e) visited_edges[e]=true case color_map[v] # If it's unvisited it goes into the waiting list when :unvisited options.handle_edge(:tree_edge, e) color_map[v] = :waiting waiting.push(v) # If it's recursive (i.e. dfs) then call self gratr_search_iteration(options, waiting, color_map, visited_edges, result, true) if recursive when :waiting options.handle_edge(:back_edge, e) else options.handle_edge(:forward_edge, e) end end # Finished with this vertex options.handle_vertex(:exit_vertex, u) color_map[u] = :visited end public # 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 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 # Returns true if a graph contains no cycles, false otherwise def acyclic?() topsort.size == size; end # Returns false if a graph contains no cycles, true otherwise def cyclic?() not acyclic?; end end # Search end # Graph end # GRATR