test/traversal_test.rb
require 'test_helper'
require 'rgl/adjacency'
require 'rgl/traversal'
require 'rgl/topsort'
require 'rgl/implicit'
include RGL
class TestTraversal < Test::Unit::TestCase
def setup
@dg = DirectedAdjacencyGraph.new(Array)
edges = [[1, 2], [1, 6], [2, 3], [2, 4], [4, 5], [6, 4]]
edges.each do |(src, target)|
@dg.add_edge(src, target)
end
@bfs = @dg.bfs_iterator(1)
@dfs = @dg.dfs_iterator(1)
@ug = AdjacencyGraph.new(Array)
@ug.add_edges(*edges)
end
def test_bfs_iterator_creation
assert(@bfs.at_beginning?)
assert(!@bfs.at_end?)
assert_equal(1, @bfs.start_vertex)
assert_equal(@dg, @bfs.graph)
end
def test_bfs_visiting
expected = [1, 2, 6, 3, 4, 5]
assert_equal(expected, @bfs.to_a)
assert_equal(expected, @ug.bfs_iterator(1).to_a)
assert_equal([2, 1, 3, 4, 6, 5], @ug.bfs_iterator(2).to_a)
end
def test_bfs_event_handlers
expected = <<END
tree_edge : -1
examine_vertex : 1
examine_edge : 1-2
tree_edge : 1-2
examine_edge : 1-6
tree_edge : 1-6
finished_vertex: 1
examine_vertex : 2
examine_edge : 2-3
tree_edge : 2-3
examine_edge : 2-4
tree_edge : 2-4
finished_vertex: 2
examine_vertex : 6
examine_edge : 6-4
back_edge : 6-4
finished_vertex: 6
examine_vertex : 3
finished_vertex: 3
examine_vertex : 4
examine_edge : 4-5
tree_edge : 4-5
finished_vertex: 4
examine_vertex : 5
examine_edge : 5-3
forward_edge : 5-3
finished_vertex: 5
END
s = ''
@dg.add_edge 5, 3 # for the forward_edge 5-3
@bfs.set_examine_vertex_event_handler { |v| s << "examine_vertex : #{v}\n" }
@bfs.set_examine_edge_event_handler { |u, v| s << "examine_edge : #{u}-#{v}\n" }
@bfs.set_tree_edge_event_handler { |u, v| s << "tree_edge : #{u}-#{v}\n" }
@bfs.set_back_edge_event_handler { |u, v| s << "back_edge : #{u}-#{v}\n" }
@bfs.set_forward_edge_event_handler { |u, v| s << "forward_edge : #{u}-#{v}\n" }
@bfs.each { |v| s << "finished_vertex: #{v}\n" }
puts "BFS: ", s if $DEBUG
assert_equal(expected, s)
end
def test_dfs_visiting
assert_equal([1, 6, 4, 5, 2, 3], @dg.dfs_iterator(1).to_a)
assert_equal([2, 4, 5, 3], @dg.dfs_iterator(2).to_a)
end
def test_dfs_event_handlers
expected = <<END
tree_edge : -1
examine_vertex : 1
examine_edge : 1-2
tree_edge : 1-2
examine_edge : 1-6
tree_edge : 1-6
finished_vertex: 1
examine_vertex : 6
examine_edge : 6-4
tree_edge : 6-4
finished_vertex: 6
examine_vertex : 4
examine_edge : 4-5
tree_edge : 4-5
finished_vertex: 4
examine_vertex : 5
examine_edge : 5-3
tree_edge : 5-3
finished_vertex: 5
examine_vertex : 3
finished_vertex: 3
examine_vertex : 2
examine_edge : 2-3
forward_edge : 2-3
examine_edge : 2-4
forward_edge : 2-4
finished_vertex: 2
END
s = ''
@dg.add_edge 5, 3
@dfs.set_examine_vertex_event_handler { |v| s << "examine_vertex : #{v}\n" }
@dfs.set_examine_edge_event_handler { |u, v| s << "examine_edge : #{u}-#{v}\n" }
@dfs.set_tree_edge_event_handler { |u, v| s << "tree_edge : #{u}-#{v}\n" }
@dfs.set_back_edge_event_handler { |u, v| s << "back_edge : #{u}-#{v}\n" }
@dfs.set_forward_edge_event_handler { |u, v| s << "forward_edge : #{u}-#{v}\n" }
@dfs.each { |v| s << "finished_vertex: #{v}\n" }
puts "DFS: ", s if $DEBUG
assert_equal(expected, s)
end
def test_bfs_search_tree
assert_equal("(1-2)(1-6)(2-3)(2-4)(4-5)", @dg.bfs_search_tree_from(1).edges.sort.join)
end
def aux(it)
it.attach_distance_map
it.set_to_end
it.graph.vertices.sort.collect { |v|
"#{v}-#{it.distance_to_root(v)}"
}.join(', ')
end
def test_distance_map
assert_equal("1-0, 2-1, 3-2, 4-2, 5-3, 6-1", aux(@bfs))
@dg.add_edge 5, 3
assert_equal("1-0, 2-1, 3-4, 4-2, 5-3, 6-1", aux(@dfs))
end
def test_topsort
ts_it = @dg.topsort_iterator
assert(ts_it.at_beginning?)
assert_equal(@dg, ts_it.graph)
assert(!ts_it.at_end?)
ts_order = ts_it.to_a # do the traversal
assert_equal(@dg.num_vertices, ts_order.size)
# Check topsort constraint:
@dg.each_edge { |u, v|
assert(ts_order.index(u) < ts_order.index(v))
}
ts_it.set_to_begin
assert(ts_it.at_beginning?)
# Topsort on undirected graphs is empty
assert(@ug.topsort_iterator.at_end?)
end
# depth_first_search can also be used to compute a topsort!
def test_dfs_search_as_topsort
ts_order = []
@dg.depth_first_search { |v| ts_order << v }
ts_order = ts_order.reverse
@dg.each_edge { |u, v|
assert(ts_order.index(u) < ts_order.index(v))
}
end
def test_acyclic
assert(@dg.acyclic?)
@dg.add_edge 5, 2 # add cycle
assert(!@dg.acyclic?)
end
def test_dfs_visit
a = []
@dg.depth_first_visit(1) { |x| a << x }
assert_equal([3, 5, 4, 2, 6, 1], a)
a = []
@dg.add_edge 10, 11
@dg.depth_first_visit(10) { |x| a << x }
assert_equal([11, 10], a)
end
def test_dfs_visit_with_parens
a = ""
vis = DFSVisitor.new(@dg)
vis.set_examine_vertex_event_handler { |v| a << "(#{v} " }
vis.set_finish_vertex_event_handler { |v| a << " #{v})" }
@dg.depth_first_visit(1, vis) { |x| }
assert_equal("(1 (2 (3 3)(4 (5 5) 4) 2)(6 6) 1)", a)
end
def test_depth_first_search_with_parens
@dg.add_edge 10, 11
# We must ensure, that the order of the traversal is not dependent on the
# order of the each iterator in the hash map of the adjacency graph. Therefor we
# wrap the graph with an implicit graph that simply ensures a sort order on
# the vertices.
dg = @dg.implicit_graph { |g|
g.vertex_iterator { |b| @dg.vertices.sort.each(&b) }
}
a = ""
vis = DFSVisitor.new(dg)
vis.set_examine_vertex_event_handler { |v| a << "(#{v} " }
vis.set_finish_vertex_event_handler { |v| a << " #{v})" }
dg.depth_first_search(vis) { |x| }
assert_equal("(1 (2 (3 3)(4 (5 5) 4) 2)(6 6) 1)(10 (11 11) 10)", a)
end
def test_bfs_stream_protocol
it = @dg.bfs_iterator(1)
assert_true(it.at_beginning?)
it.set_to_end()
assert_true(it.at_end?)
it.set_to_begin()
assert_true(it.at_beginning?)
assert_equal(it.to_a(), [1, 2, 6, 3, 4, 5])
end
def test_dfs_stream_protocol
it = @dg.dfs_iterator(1)
assert_true(it.at_beginning?)
it.set_to_end()
assert_true(it.at_end?)
it.set_to_begin()
assert_true(it.at_beginning?)
assert_equal(it.to_a(), [1, 6, 4, 5, 2, 3])
end
end