Mixins. Example of Dfs mixin

Simple implementation

Mixin Dfs needs methods each_node(&block) and each_child(node,&block) to be defined in the host class.

Method dfs receives block which is called for each graph node. If block returns false (or nil) then dfs stops.

module Dfs
  def dfs(&block)
    block ||= lambda { true}
    @visited = Hash.new(:white)
    each_node do |n|
      (dfs_visit(n, &block) or return false) if @visited[n] == :white
    end
    return true
  end
  
  def dfs_visit(node, &block)
    return :done if @visited[node] != :white
    return false unless block[node]
    @visited[node] = :grey
    each_child(node) do |n|
      return false unless dfs_visit(n, &block)
    end
    @visited[node] = :black
  end
end

Graph as hash of hashes

class Hash
  alias :each_node :each_key
  def each_child(node, &block)
    (self[node]||{}).each do |n, weight|
      block[n]
    end
  end

  include Dfs
end

t = {
  1=>{2=>true, 5=>true},
  2=>{},
  5=>{4=>true},
  4=>{3=>true}
}

puts t.dfs {|node| puts "I'am in node #{node}"; true }

Implementation with callbacks

But for different dfs applications we need execute code chunks before and after visiting a node. Let's add sequences of callbacks. Each (before|after)_visit block returns true if everything is OK and walk should be continued. Otherwise dfs stops.

module Dfs
  def dfs(&block)
    block ||= lambda { true}
    @visited = Hash.new(:white)
    @before_visit ||= []
    @after_visit ||= []
    each_node do |n|
      (dfs_visit(n, &block) or return false) if @visited[n] == :white
    end
    return true
  end
  
  def before_visit(&block)
    ( @before_visit ||= [] ) << block
  end
  
  def after_visit(&block)
    ( @after_visit ||= [] ) << block
  end

  def clear_callbacks
    (@after_visit||=[]).clear
    (@before_visit||=[]).clear
  end
  
  def dfs_visit(node, &block)
    return false unless @before_visit.all?{|b| b[node]}     
    return :done if @visited[node] != :white
    @visited[node] = :grey
    return false unless block[node]
    each_child(node) do |n|
      return false unless  dfs_visit(n, &block)
    end
    @visited[node] = :black
    @after_visit.all?{|b| b[node]}
  end
  
  def cycle?
    @before_visit << lambda {|n| @visited[n] != :grey}
    res = ! dfs
    @before_visit.pop
    res
  end
end

class Hash
  alias :each_node :each_key
  def each_child(node, &block)
    (self[node]||{}).each do |n, weight|
      block[n]
    end
  end

  include Dfs
end


t = {
  1=>{2=>true, 5=>true},
  2=>{},
  5=>{4=>true},
  4=>{3=>true}
}

t.before_visit {|n| puts "step  into  node #{n}"; true}
t.after_visit  {|n| puts "step out of node #{n}"; true}

puts t.dfs {|n| puts "in node #{n}"; true}
puts
puts t.cycle?

It outputs

step  into  node 5
in node 5
step  into  node 4
in node 4
step  into  node 3
in node 3
step out of node 3
step out of node 4
step out of node 5
step  into  node 1
in node 1
step  into  node 5
step  into  node 2
in node 2
step out of node 2
step out of node 1
true

step  into  node 5
step  into  node 4
step  into  node 3
step out of node 3
step out of node 4
step out of node 5
step  into  node 1
step  into  node 5
step  into  node 2
step out of node 2
step out of node 1
false