class TestTraversal

# File test/traversal_test.rb, line 136
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

# File test/traversal_test.rb, line 12
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

# File test/traversal_test.rb, line 179
def test_acyclic
  assert(@dg.acyclic?)
  @dg.add_edge 5, 2 # add cycle
  assert(!@dg.acyclic?)
end

# File test/traversal_test.rb, line 39
  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

# File test/traversal_test.rb, line 25
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

# File test/traversal_test.rb, line 132
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

# File test/traversal_test.rb, line 32
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

# File test/traversal_test.rb, line 205
def test_depth_first_search_with_parens
  @dg.add_edge 10, 11
  # We must ensure, that the order of the traversal is not dependend 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

# File test/traversal_test.rb, line 88
  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

# File test/traversal_test.rb, line 170
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

# File test/traversal_test.rb, line 185
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

# File test/traversal_test.rb, line 196
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

# File test/traversal_test.rb, line 83
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

# File test/traversal_test.rb, line 144
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

# File test/traversal_test.rb, line 150
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