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