#
# test/bio/tc_pathway.rb - Unit test for Bio::Pathway
#
# Copyright::  Copyright (C) 2004
#              Moses Hohman <mmhohman@northwestern.edu>
# License::    The Ruby License
#
#  $Id:$
#

# loading helper routine for testing bioruby
require 'pathname'
load Pathname.new(File.join(File.dirname(__FILE__), ['..'] * 2,
                            'bioruby_test_helper.rb')).cleanpath.to_s

# libraries needed for the tests
require 'test/unit'
require 'bio/pathway'

module Bio
  class TestMyGraph < Test::Unit::TestCase
    def test_cliquishness
      graph = Pathway.new([
                            Relation.new(1, 3, 1),
                            Relation.new(2, 3, 1),
                            Relation.new(1, 5, 1),
                            Relation.new(2, 6, 1),
                            Relation.new(3, 6, 1),
                            Relation.new(4, 6, 1),
                            Relation.new(5, 6, 1)
                          ], true)
      assert_equal(0, graph.cliquishness(1), "1's cliquishness wrong")
      assert_equal(1, graph.cliquishness(2), "2's cliquishness wrong")
      assert_in_delta(0.33, graph.cliquishness(3), 0.01, "3's cliquishness wrong")
      # Because cliquishness (clustering coefficient) for a node
      # that has only one neighbor node is undefined, test for
      # node 4 is commented out.
      # assert_equal(1, graph.cliquishness(4), "4's cliquishness wrong")
      assert_equal(0, graph.cliquishness(5), "5's cliquishness wrong")
      assert_in_delta(0.16, graph.cliquishness(6), 0.01, "6's cliquishness wrong")
    end
  end

  class TestRelation < Test::Unit::TestCase
    def setup
      @r1 = Relation.new('a', 'b', 1)
      @r2 = Relation.new('b', 'a', 1)
      @r3 = Relation.new('b', 'a', 2)
      @r4 = Relation.new('a', 'b', 1)
    end

    def test_comparison_operator
      assert(@r1 === @r2, '@r1 === @r2 not true, === not symmetric wrt nodes')
      assert(!(@r1 === @r3), '@r1 === @r3 not false, === does not take edge into account')
      assert(@r1 === @r4, '@r1 === @r4 not true, === is not reflexive wrt nodes')
      assert(@r1.eql?(@r2), '@r1 not eql @r2')
      assert(!@r3.eql?(@r2), '@r3 eql to @r2')
    end

    def test_uniq
      a = [@r1, @r2, @r3, @r4].uniq
      # Array#uniq does not guarantee that the first value is always
      # chosen, though the "bug" is fixed.
      # (https://bugs.ruby-lang.org/issues/9340 )
      # (https://github.com/bioruby/bioruby/issues/92 )
      # #assert_equal([@r1, @r3], a, "uniq did not have expected effect")
      assert_equal(2, a.size)
      assert(@r1 === a[0])
      assert(@r3 === a[1])
    end
  end

  class TestSampleGraph < Test::Unit::TestCase
    TheInfinity = 1 / 0.0

    # Sample Graph :
    #                  +----------------+
    #                  |                |
    #                  v                |
    #       +---------(q)-->(t)------->(y)<----(r)
    #       |          |     |          ^       |
    #       v          |     v          |       |
    #   +--(s)<--+     |    (x)<---+   (u)<-----+
    #   |        |     |     |     |
    #   v        |     |     v     |
    #  (v)----->(w)<---+    (z)----+

    def setup
      @data = [
        ['q', 's', 1],
        ['q', 't', 1],
        ['q', 'w', 1],
        ['r', 'u', 1],
        ['r', 'y', 1],
        ['s', 'v', 1],
        ['t', 'x', 1],
        ['t', 'y', 1],
        ['u', 'y', 1],
        ['v', 'w', 1],
        ['w', 's', 1],
        ['x', 'z', 1],
        ['y', 'q', 1],
        ['z', 'x', 1]
      ]

      @graph = Pathway.new(@data.collect { |x| Relation.new(*x) })
    end

    def test_to_matrix
      matrix = @graph.to_matrix(0)
      index = @graph.index
      # expected values
      source_matrix =
        [
          # v  w  x  y  z  q  r  s  t  u
          [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], # v
          [0, 0, 0, 0, 0, 0, 0, 1, 0, 0], # w
          [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], # x
          [0, 0, 0, 0, 0, 1, 0, 0, 0, 0], # y
          [0, 0, 1, 0, 0, 0, 0, 0, 0, 0], # z
          [0, 1, 0, 0, 0, 0, 0, 1, 1, 0], # q
          [0, 0, 0, 1, 0, 0, 0, 0, 0, 1], # r
          [1, 0, 0, 0, 0, 0, 0, 0, 0, 0], # s
          [0, 0, 1, 1, 0, 0, 0, 0, 0, 0], # t
          [0, 0, 0, 1, 0, 0, 0, 0, 0, 0]  # u
        ]
      source_index = {
        'v' => 0, 'w' => 1, 'x' => 2, 'y' => 3, 'z' => 4,
        'q' => 5, 'r' => 6, 's' => 7, 't' => 8, 'u' => 9
      }
      # test index size
      assert_equal(10, source_index.size)
      # test index keys
      assert_equal(source_index.keys.sort, index.keys.sort)
      # test index values
      assert_equal(source_index.values.sort, index.values.sort)
      # prepare expected matrix
      ary = Array.new(index.size)
      ary.collect! { |_a| Array.new(index.size) }
      index.each do |row_k, row_v|
        src_row = source_index[row_k]
        index.each do |col_k, col_v|
          src_col = source_index[col_k]
          ary[row_v][col_v] = source_matrix[src_row][src_col]
        end
      end
      expected_matrix = Matrix.rows(ary)
      # test the matrix
      assert_equal(expected_matrix, matrix, 'matrix wrong')
    end

    def test_to_matrix_fixed_index
      # begin workaround removing depencency to order of Hash#each
      %w[v w x y z q r s t u].each_with_index do |x, i|
        @graph.index[x] = i
      end
      # end workaround removing depencency to order of Hash#each
      assert_equal(Matrix[
        [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
        [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0, 0, 1, 1, 0],
        [0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
    ], @graph.to_matrix(0), 'matrix wrong')
      assert_equal({ 'v' => 0, 'w' => 1, 'x' => 2, 'y' => 3, 'z' => 4, 'q' => 5, 'r' => 6, 's' => 7, 't' => 8, 'u' => 9 }, @graph.index,
                   'node --> matrix index order wrong')
    end

    def test_dump_matrix
      # begin workaround removing depencency to order of Hash#each
      %w[v w x y z q r s t u].each_with_index do |x, i|
        @graph.index[x] = i
      end
      # end workaround removing depencency to order of Hash#each
      dumped = '[' +
               "# v, w, x, y, z, q, r, s, t, u\n" +
               " [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],\n" + # v
               " [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],\n" + # w
               " [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n" + # x
               " [0, 0, 0, 0, 0, 1, 0, 0, 0, 0],\n" + # y
               " [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],\n" + # z
               " [0, 1, 0, 0, 0, 0, 0, 1, 1, 0],\n" + # q
               " [0, 0, 0, 1, 0, 0, 0, 0, 0, 1],\n" + # r
               " [1, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n" + # s
               " [0, 0, 1, 1, 0, 0, 0, 0, 0, 0],\n" + # t
               " [0, 0, 0, 1, 0, 0, 0, 0, 0, 0]\n]"   # u
      assert_equal(dumped, @graph.dump_matrix(0))
    end

    def test_dump_list
      # begin workaround removing depencency to order of Hash#each
      %w[v w x y z q r s t u].each_with_index do |x, i|
        @graph.index[x] = i
      end
      # end workaround removing depencency to order of Hash#each
      dumped = "v => w (1)\n" +
               "w => s (1)\n" +
               "x => z (1)\n" +
               "y => q (1)\n" +
               "z => x (1)\n" +
               "q => w (1), s (1), t (1)\n" +
               "r => y (1), u (1)\n" +
               "s => v (1)\n" +
               "t => x (1), y (1)\n" +
               "u => y (1)\n"
      assert_equal(dumped, @graph.dump_list)
    end

    def test_extract_subgraph_by_label
      hash = { 'q' => 'L1', 's' => 'L2', 'v' => 'L3', 'w' => 'L4' }
      @graph.label = hash
      subgraph = @graph.subgraph
      # begin workaround removing depencency to order of Hash#each
      %w[v w q s].each_with_index do |x, i|
        subgraph.index[x] = i
      end
      # end workaround removing depencency to order of Hash#each
      dumped =
        "v => w (1)\n" +
        "w => s (1)\n" +
        "q => w (1), s (1)\n" +
        "s => v (1)\n"
      assert_equal(dumped, subgraph.dump_list)
    end

    def test_extract_subgraph_by_list
      subgraph = @graph.subgraph(%w[q t x y z])
      # begin workaround removing depencency to order of Hash#each
      %w[x y z q t].each_with_index do |x, i|
        subgraph.index[x] = i
      end
      # end workaround removing depencency to order of Hash#each
      dumped =
        "x => z (1)\n" +
        "y => q (1)\n" +
        "z => x (1)\n" +
        "q => t (1)\n" +
        "t => x (1), y (1)\n"
      assert_equal(dumped, subgraph.dump_list)
    end

    def test_extract_subgraph_retains_disconnected_nodes
      assert_equal(4, @graph.subgraph(%w[r s v w]).nodes, 'wrong number of nodes')
    end

    # Sample Graph :
    #                  +----------------+
    #                  |                |
    #                  v                |
    #       +---------(q)-->(t)------->(y)<----(r)
    #       |          |     |          ^       |
    #       v          |     v          |       |
    #   +--(s)<--+     |    (x)<---+   (u)<-----+
    #   |        |     |     |     |
    #   v        |     |     v     |
    #  (v)----->(w)<---+    (z)----+

    def test_undirected_cliquishness
      @graph.undirected
      assert_in_delta(0.33, @graph.cliquishness('q'), 0.01)
    end

    def test_small_world_aka_node_degree_histogram
      expected = { 1 => 7, 2 => 2, 3 => 1 }
      expected.default = 0
      assert_equal(expected, @graph.small_world)
    end

    # Sample Graph :
    #                  +----------------+
    #                  |                |
    #                  v                |
    #       +---------(q)-->(t)------->(y)<----(r)
    #       |          |     |          ^       |
    #       v          |     v          |       |
    #   +--(s)<--+     |    (x)<---+   (u)<-----+
    #   |        |     |     |     |
    #   v        |     |     v     |
    #  (v)----->(w)<---+    (z)----+

    def test_breadth_first_search
      distances, predecessors = @graph.breadth_first_search('q')
      assert_equal({
                     'v' => 2,
                     'w' => 1,
                     'x' => 2,
                     'y' => 2,
                     'z' => 3,
                     'q' => 0,
                     's' => 1,
                     't' => 1
                   }, distances, 'distances wrong')
      assert_equal({
                     'v' => 's',
                     'w' => 'q',
                     'x' => 't',
                     'y' => 't',
                     'z' => 'x',
                     'q' => nil,
                     's' => 'q',
                     't' => 'q'
                   }, predecessors, 'predecessors wrong')
    end

    def test_bfs_shortest_path
      step, path = @graph.bfs_shortest_path('y', 'w')
      assert_equal(2, step, 'wrong # of steps')
      assert_equal(%w[y q w], path, 'wrong path')
    end

    def test_depth_first_search
      # fixing node order to aviod dependency of Hash#each_key
      %w[v w x y z q r s t u].each_with_index do |x, i|
        @graph.index[x] = i
      end
      # exec dfs
      timestamp, tree, back, cross, forward =
        @graph.depth_first_search
      assert_equal({
                     'v' => [1, 6],
                     'w' => [2, 5],
                     'x' => [7, 10],
                     'y' => [11, 16],
                     'z' => [8, 9],
                     'q' => [12, 15],
                     'r' => [17, 20],
                     's' => [3, 4],
                     't' => [13, 14],
                     'u' => [18, 19]
                   }, timestamp, 'timestamps wrong')
      assert_equal({
                     'w' => 'v',
                     'z' => 'x',
                     'q' => 'y',
                     's' => 'w',
                     't' => 'q',
                     'u' => 'r'
                   }, tree, 'tree edges wrong')
      assert_equal({
                     'z' => 'x',
                     's' => 'v',
                     't' => 'y'
                   }, back, 'back edges wrong')
      assert_equal({
                     'q' => 's',
                     'r' => 'y',
                     't' => 'x',
                     'u' => 'y'
                   }, cross, 'cross edges wrong')
      assert_equal({}, forward, 'forward edges wrong')
    end

    # Sample Graph :
    #                  +----------------+
    #                  |                |
    #                  v                |
    #       +---------(q)-->(t)------->(y)<----(r)
    #       |          |     |          ^       |
    #       v          |     v          |       |
    #   +--(s)<--+     |    (x)<---+   (u)<-----+
    #   |        |     |     |     |
    #   v        |     |     v     |
    #  (v)----->(w)<---+    (z)----+

    def test_dijkstra
      distances, predecessors = @graph.dijkstra('q')
      assert_equal({
                     'v' => 2,
                     'w' => 1,
                     'x' => 2,
                     'y' => 2,
                     'z' => 3,
                     'q' => 0,
                     'r' => TheInfinity,
                     's' => 1,
                     't' => 1,
                     'u' => TheInfinity
                   }, distances, 'distances wrong')
      assert_equal({
                     'v' => 's',
                     'w' => 'q',
                     'x' => 't',
                     'y' => 't',
                     'z' => 'x',
                     'q' => nil,
                     'r' => nil,
                     's' => 'q',
                     't' => 'q',
                     'u' => nil
                   }, predecessors, 'predecessors wrong')
    end

    def test_bellman_ford
      distances, predecessors = @graph.bellman_ford('q')
      assert_equal({
                     'v' => 2,
                     'w' => 1,
                     'x' => 2,
                     'y' => 2,
                     'z' => 3,
                     'q' => 0,
                     'r' => TheInfinity,
                     's' => 1,
                     't' => 1,
                     'u' => TheInfinity
                   }, distances, 'distances wrong')
      assert_equal({
                     'v' => 's',
                     'w' => 'q',
                     'x' => 't',
                     'y' => 't',
                     'z' => 'x',
                     'q' => nil,
                     'r' => nil,
                     's' => 'q',
                     't' => 'q',
                     'u' => nil
                   }, predecessors, 'predecessors wrong')
    end
  end

  class TestTopologicalSort < Test::Unit::TestCase
    #
    # Professor Bumstead topologically sorts his clothing when getting dressed.
    #
    #  "undershorts"       "socks"
    #     |      |            |
    #     v      |            v           "watch"
    #  "pants" --+-------> "shoes"
    #     |
    #     v
    #  "belt" <----- "shirt" ----> "tie" ----> "jacket"
    #     |                                       ^
    #     `---------------------------------------'
    #

    def test_dfs_topological_sort
      dag = Pathway.new([
                          Relation.new('undershorts', 'pants', true),
                          Relation.new('undershorts', 'shoes', true),
                          Relation.new('socks', 'shoes', true),
                          Relation.new('watch', 'watch', true),
                          Relation.new('pants', 'belt', true),
                          Relation.new('pants', 'shoes', true),
                          Relation.new('shirt', 'belt', true),
                          Relation.new('shirt', 'tie', true),
                          Relation.new('tie', 'jacket', true),
                          Relation.new('belt', 'jacket', true)
                        ])
      sorted = dag.dfs_topological_sort
      assert(sorted.index('socks') < sorted.index('shoes'), 'socks >= shoes')
      assert(sorted.index('undershorts') < sorted.index('pants'), 'undershorts >= pants')
      assert(sorted.index('undershorts') < sorted.index('shoes'), 'undershorts >= shoes')
      assert(sorted.index('pants') < sorted.index('shoes'), 'pants >= shoes')
      assert(sorted.index('pants') < sorted.index('belt'), 'pants >= belt')
      assert(sorted.index('shirt') < sorted.index('belt'), 'shirt >= belt')
      assert(sorted.index('shirt') < sorted.index('tie'), 'shirt >= tie')
      assert(sorted.index('belt') < sorted.index('jacket'), 'belt >= jacket')
      assert(sorted.index('tie') < sorted.index('jacket'), 'tie >= jacket')
    end
  end

  # TODO: verify the below
  class TestWeightedGraph < Test::Unit::TestCase
    #  'a' --> 'b'
    #   |   1   | 3
    #   |5      v
    #   `----> 'c'

    def setup
      r1 = Relation.new('a', 'b', 1)
      r2 = Relation.new('a', 'c', 5)
      r3 = Relation.new('b', 'c', 3)
      @w_graph = Pathway.new([r1, r2, r3])
    end

    def test_dijkstra_on_weighted_graph
      distances, predecessors = @w_graph.dijkstra('a')
      assert_equal({
                     'a' => 0,
                     'b' => 1,
                     'c' => 4
                   }, distances, 'distances wrong')
      assert_equal({
                     'a' => nil,
                     'b' => 'a',
                     'c' => 'b'
                   }, predecessors, 'predecessors wrong')
    end

    def test_bellman_ford_on_negative_weighted_graph
      #  ,-- 'a' --> 'b'
      #  |    |   1   | 3
      #  |    |5      v
      #  |    `----> 'c'
      #  |            ^
      #  |2           | -5
      #  `--> 'd' ----'

      r4 = Relation.new('a', 'd', 2)
      r5 = Relation.new('d', 'c', -5)
      @w_graph.append(r4)
      @w_graph.append(r5)
      distances, predecessors = @w_graph.bellman_ford('a')
      assert_equal({
                     'a' => 0,
                     'b' => 1,
                     'c' => -3,
                     'd' => 2
                   }, distances, 'distances wrong')
      assert_equal({
                     'a' => nil,
                     'b' => 'a',
                     'c' => 'd',
                     'd' => 'a'
                   }, predecessors, 'predecessors wrong')
    end
  end
end
