class TestBellmanFord

# File test/bellman_ford_test.rb, line 10
def setup
  @graph = AdjacencyGraph[1,2, 1,3, 2,3, 2,4, 3,4]

  @edge_weights = {
      [1, 2] => 10,
      [1, 3] => 1,
      [2, 3] => 1,
      [2, 4] => 1,
      [3, 4] => 10
  }

  @edge_weights_lambda = lambda { |edge| @edge_weights[edge] }
end

# File test/bellman_ford_test.rb, line 81
def test_missing_edge_weight
  @edge_weights.delete([2, 3])
  assert_raises(ArgumentError, 'weight of edge (2, 3) is not defined') { shortest_paths(1) }
end

# File test/bellman_ford_test.rb, line 86
def test_negative_cycles
  @graph = DirectedAdjacencyGraph[1,2, 1,3, 2,3, 2,4, 3,4, 4,2]
  @edge_weights[[4, 2]] = 1
  @edge_weights[[3, 4]] = -3 # cycle 2-3-4-2 has negative weight

  assert_raises(ArgumentError, 'there is a negative-weight cycle including edge (3, 4)') { shortest_paths(1) }
end

# File test/bellman_ford_test.rb, line 24
def test_shortest_paths_search
  assert_equal(
      {
          1 => [1],
          2 => [1, 3, 2],
          3 => [1, 3],
          4 => [1, 3, 2, 4]
      },
      shortest_paths(1)
  )
end

# File test/bellman_ford_test.rb, line 36
def test_shortest_paths_search_with_lambda
  assert_equal(
      {
          1 => [1],
          2 => [1, 3, 2],
          3 => [1, 3],
          4 => [1, 3, 2, 4]
      },
      shortest_paths(1, @edge_weights_lambda)
  )
end

# File test/bellman_ford_test.rb, line 48
def test_shortest_paths_search_with_unreachable_vertex
  @graph.add_vertex(5)

  assert_equal(
      {
          1 => [1],
          2 => [1, 3, 2],
          3 => [1, 3],
          4 => [1, 3, 2, 4],
          5 => nil
      },
      shortest_paths(1)
  )
end

# File test/bellman_ford_test.rb, line 63
def test_shortest_paths_with_negative_weights
  # can't use an undirected graph with a negative weighted edge here, because a negative weighted undirected edge is
  # already a negative weighted cycle and therefore Bellman-Ford can't be applied for such graph
  @graph = DirectedAdjacencyGraph[1,2, 1,3, 2,3, 2,4, 3,2, 3,4]
  @edge_weights[[3, 2]] = 1
  @edge_weights[[3, 4]] = -1

  assert_equal(
      {
          1 => [1],
          2 => [1, 3, 2],
          3 => [1, 3],
          4 => [1, 3, 4]
      },
      shortest_paths(1)
  )
end

# File test/bellman_ford_test.rb, line 94
def test_visitor
  visitor = BellmanFordVisitor.new(@graph)

  events = []

  %w[examine_edge edge_relaxed edge_not_relaxed edge_minimized edge_not_minimized].each do |event|
    visitor.send("set_#{event}_event_handler") { |*args| events << { event.to_sym => args } }
  end

  @graph.bellman_ford_shortest_paths(@edge_weights, 1, visitor)

  assert_equal(
      [
          # first iteration
          { :examine_edge     => [1, 2] },
          { :edge_relaxed     => [1, 2] },
          { :examine_edge     => [2, 1] },
          { :edge_not_relaxed => [2, 1] },
          { :examine_edge     => [1, 3] },
          { :edge_relaxed     => [1, 3] },
          { :examine_edge     => [3, 1] },
          { :edge_not_relaxed => [3, 1] },
          { :examine_edge     => [2, 3] },
          { :edge_not_relaxed => [2, 3] },
          { :examine_edge     => [3, 2] },
          { :edge_relaxed     => [3, 2] },
          { :examine_edge     => [2, 4] },
          { :edge_relaxed     => [2, 4] },
          { :examine_edge     => [4, 2] },
          { :edge_not_relaxed => [4, 2] },
          { :examine_edge     => [3, 4] },
          { :edge_not_relaxed => [3, 4] },
          { :examine_edge     => [4, 3] },
          { :edge_not_relaxed => [4, 3] },
          # second iteration
          { :examine_edge     => [1, 2] },
          { :edge_not_relaxed => [1, 2] },
          { :examine_edge     => [2, 1] },
          { :edge_not_relaxed => [2, 1] },
          { :examine_edge     => [1, 3] },
          { :edge_not_relaxed => [1, 3] },
          { :examine_edge     => [3, 1] },
          { :edge_not_relaxed => [3, 1] },
          { :examine_edge     => [2, 3] },
          { :edge_not_relaxed => [2, 3] },
          { :examine_edge     => [3, 2] },
          { :edge_not_relaxed => [3, 2] },
          { :examine_edge     => [2, 4] },
          { :edge_not_relaxed => [2, 4] },
          { :examine_edge     => [4, 2] },
          { :edge_not_relaxed => [4, 2] },
          { :examine_edge     => [3, 4] },
          { :edge_not_relaxed => [3, 4] },
          { :examine_edge     => [4, 3] },
          { :edge_not_relaxed => [4, 3] },
          # thirds iteration
          { :examine_edge     => [1, 2] },
          { :edge_not_relaxed => [1, 2] },
          { :examine_edge     => [2, 1] },
          { :edge_not_relaxed => [2, 1] },
          { :examine_edge     => [1, 3] },
          { :edge_not_relaxed => [1, 3] },
          { :examine_edge     => [3, 1] },
          { :edge_not_relaxed => [3, 1] },
          { :examine_edge     => [2, 3] },
          { :edge_not_relaxed => [2, 3] },
          { :examine_edge     => [3, 2] },
          { :edge_not_relaxed => [3, 2] },
          { :examine_edge     => [2, 4] },
          { :edge_not_relaxed => [2, 4] },
          { :examine_edge     => [4, 2] },
          { :edge_not_relaxed => [4, 2] },
          { :examine_edge     => [3, 4] },
          { :edge_not_relaxed => [3, 4] },
          { :examine_edge     => [4, 3] },
          { :edge_not_relaxed => [4, 3] },
          # post-iteration check
          { :edge_minimized   => [1, 2] },
          { :edge_minimized   => [1, 3] },
          { :edge_minimized   => [2, 3] },
          { :edge_minimized   => [2, 4] },
          { :edge_minimized   => [3, 4] }
      ],
      events
  )
end