monora/rgl

# implicit.rb
#
# This file contains the definition of the class RGL::ImplicitGraph, which
# defines vertex and edge iterators using blocks (which again call blocks).
#

require 'rgl/base'

module RGL

  # An ImplicitGraph provides a handy way to define graphs on the fly, using two
  # blocks for the two iterators defining a graph. Other examples are given by the
  # methods {#vertices_filtered_by} and {#edges_filtered_by}, which can be
  # applied to any graph.
  #
  # @example
  #   # A directed cyclic graph, with five vertices can be created as follows:
  #   g = RGL::ImplicitGraph.new do |g|
  #     g.vertex_iterator { |b| 0.upto(4,&b) }
  #     g.adjacent_iterator { |x, b| b.call((x+1)%5) }
  #     g.directed = true
  #   end
  #
  #   g.to_s # => "(0-1)(1-2)(2-3)(3-4)(4-0)"
  #
  class ImplicitGraph

    include Graph

    attr_writer :directed

    EMPTY_VERTEX_ITERATOR   = proc { |b| }
    EMPTY_NEIGHBOR_ITERATOR = proc { |x, b| }

    # Create a new {ImplicitGraph}, which is empty by default. The caller should
    # configure the graph using vertex and neighbor iterators. If the graph is
    # directed, the client should set +@directed+ to true. The default value
    # for +@directed+ is false.
    #
    def initialize
      @directed          = false
      @vertex_iterator   = EMPTY_VERTEX_ITERATOR
      @adjacent_iterator = EMPTY_NEIGHBOR_ITERATOR
      yield self if block_given? # Let client overwrite defaults.
    end

    # Returns the value of +@directed+.
    #
    def directed?
      @directed
    end

    def each_vertex(&block)
      @vertex_iterator.call(block)
    end

    def each_adjacent(v, &block)
      @adjacent_iterator.call(v, block)
    end

    def each_edge(&block)
      if defined? @edge_iterator
        @edge_iterator.call(block)
      else
        super # use default implementation
      end
    end

    # Sets the vertex_iterator to _block_,
    # which must be a block of one parameter
    # which again is the block called by {#each_vertex}.
    #
    def vertex_iterator(&block)
      @vertex_iterator = block
    end

    # Sets the adjacent_iterator to _block_,
    # which must be a block of two parameters:
    #
    #   The first parameter is the vertex the neighbors of which are to be
    #   traversed.
    #
    #   The second is the block which will be called for each neighbor
    #   of this vertex.
    #
    def adjacent_iterator(&block)
      @adjacent_iterator = block
    end

    # Sets the edge_iterator to _block_, which must be a block of two
    # parameters: The first parameter is the source of the edges; the
    # second is the target of the edge.
    #
    def edge_iterator(&block)
      @edge_iterator = block
    end

  end # class ImplicitGraph


  module Graph

    # Returns a new {ImplicitGraph} which has as vertices all vertices of the
    # receiver which satisfy the predicate _filter_.
    #
    # The methods provides similar functionality as
    # {https://www.boost.org/doc/libs/1_36_0/libs/graph/doc/filtered_graph.html
    # BGLs Filtered Graph}
    #
    # @example
    #
    #   def complete (n)
    #     set = n.integer? ? (1..n) : n
    #     RGL::ImplicitGraph.new do |g|
    #       g.vertex_iterator { |b| set.each(&b) }
    #       g.adjacent_iterator do |x, b|
    #         set.each { |y| b.call(y) unless x == y }
    #       end
    #     end
    #   end
    #
    #   complete(4).to_s # => "(1=2)(1=3)(1=4)(2=3)(2=4)(3=4)"
    #   complete(4).vertices_filtered_by { |v| v != 4 }.to_s # => "(1=2)(1=3)(2=3)"
    # @return [ImplicitGraph]
    def vertices_filtered_by(&filter)
      implicit_graph do |g|
        g.vertex_iterator do |b|
          self.each_vertex { |v| b.call(v) if filter.call(v) }
        end

        g.adjacent_iterator do |v, b|
          self.each_adjacent(v) { |u| b.call(u) if filter.call(u) }
        end
      end
    end

    # Returns a new {ImplicitGraph} which has as edges all edges of the receiver
    # which satisfy the predicate _filter_ (a block with two parameters).
    #
    # @example
    #
    #       g = complete(7).edges_filtered_by { |u,v| u+v == 7 }
    #       g.to_s     => "(1=6)(2=5)(3=4)"
    #       g.vertices => [1, 2, 3, 4, 5, 6, 7]
    # @return [ImplicitGraph]
    def edges_filtered_by(&filter)
      implicit_graph do |g|
        g.adjacent_iterator do |v, b|
          self.each_adjacent(v) do |u|
            b.call(u) if filter.call(v, u)
          end
        end

        g.edge_iterator do |b|
          self.each_edge { |u, v| b.call(u, v) if filter.call(u, v) }
        end
      end
    end

    # Return a new {ImplicitGraph} which is isomorphic (i.e. has same edges and
    # vertices) to the receiver. It is a shortcut, also used by
    # {#edges_filtered_by} and {#vertices_filtered_by}.
    # @return [ImplicitGraph]
    def implicit_graph
      result = ImplicitGraph.new do |g|
        g.vertex_iterator { |b| self.each_vertex(&b) }
        g.adjacent_iterator { |v, b| self.each_adjacent(v, &b) }
        g.directed = self.directed?
      end

      yield result if block_given? # let client overwrite defaults
      result
    end

  end # module Graph

end # module RGL