monora/rgl

require 'rgl/graph_wrapper'

module RGL

  # Module GraphVisitor defines the
  # {https://www.boost.org/libs/graph/doc/visitor_concepts.html BGL Visitor Concepts}.
  #
  # Visitors provide a mechanism for extending an algorithm (i.e., for
  # customizing what is done at each step of the algorithm). They allow users
  # to insert their own operations at various steps within a graph algorithm.
  #
  # Graph algorithms typically have multiple event points where one may want to
  # insert a call-back. Therefore, visitors have several methods that
  # correspond to the various event points. Each algorithm has a different
  # set of event points. The following are common to both DFS and BFS search:
  #
  #  * examine_vertex
  #  * examine_edge
  #  * tree_edge
  #  * back_edge
  #  * forward_edge
  #  * finish_vertex
  #
  # These methods are all named +handle_*+ and can be set to appropriate blocks,
  # using the methods +set_*_event_handler+, which are defined for each event
  # mentioned above.
  #
  # As an alternative, you can also override the +handle_*+ methods in a
  # subclass, to configure the algorithm (as an example, see TarjanSccVisitor).
  #
  # During a graph traversal, vertices are *colored* using the colors :GRAY
  # (when waiting) and :BLACK when finished. All other vertices are :WHITE.
  # The +color_map+ is also maintained in the visitor.
  #
  module GraphVisitor

    include GraphWrapper

    # @return [Hash] a map which store the colors for each vertex
    attr_reader :color_map

    # Create a new GraphVisitor on _graph_.
    # @param [Graph] graph
    def initialize(graph)
      super(graph)
      reset
    end

    # Mark each vertex unvisited (i.e. :WHITE)
    #
    def reset
      @color_map = Hash.new(:WHITE)
    end

    # Returns true if vertex _v_ is colored :BLACK (i.e. finished).
    #
    def finished_vertex?(v)
      @color_map[v] == :BLACK
    end

    # Shall we follow the edge (u,v); i.e. v has color :WHITE
    #
    def follow_edge?(u, v)
      @color_map[v] == :WHITE
    end

    # Attach a map to the visitor which records the distance of a visited
    # vertex to the start vertex.
    #
    # This is similar to BGLs
    # {https://www.boost.org/libs/graph/doc/distance_recorder.html distance_recorder}.
    #
    # After the +distance_map+ is attached, the visitor has a new method
    # +distance_to_root+, which answers the distance to the start vertex.
    #
    def attach_distance_map(map = Hash.new(0))
      @distance_map = map

      # add distance map support to the current visitor instance
      extend(DistanceMapSupport)
    end

    module DistanceMapSupport

      def handle_tree_edge(u, v)
        super
        @distance_map[v] = @distance_map[u] + 1
      end

      # Answer the distance to the start vertex.

      def distance_to_root(v)
        @distance_map[v]
      end

    end # module DistanceMapSupport

    module ClassMethods

      # Defines an event handler.
      #
      def def_event_handlers(*events)
        events.each do |event|
          params = event.to_s.include?('edge') ? 'u, v' : 'u'

          handler = "@#{event}_event_handler"

          class_eval <<-END
            def handle_#{event}(#{params})
              #{handler}.call(#{params}) if defined? #{handler}
            end

            def set_#{event}_event_handler(&block)
              #{handler} = block
            end
          END
        end
      end

      alias def_event_handler def_event_handlers

    end # module ClassMethods

    extend ClassMethods # add class methods to GraphVisitor class itself

    def self.included(base)
      # when GraphVisitor is included into a class/module, add class methods as well
      base.extend ClassMethods
    end

    def_event_handlers :examine_vertex,
                       :examine_edge,
                       :tree_edge,
                       :back_edge,
                       :forward_edge,
                       :finish_vertex

  end # module GraphVisitor

end # module RGL