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