defmodule BitGraphTest do
  use ExUnit.Case

  alias BitGraph.{V, Adjacency}
  alias Iter.{Iterable, Iterable.Mapper}

  describe "BitGraph" do
    test "create graph" do
      graph = BitGraph.new()
      assert graph.vertices.num_vertices == 0
    end

    test "copy graph" do
      edge_data = %{label: "a->b"}
      graph =
        BitGraph.new()
        |> BitGraph.add_vertex(:a, %{label: "a"})
        |> BitGraph.add_vertex(:b, %{label: "b"})
        |> BitGraph.add_edge(:a, :b, edge_data)
      copy = BitGraph.copy(graph)

      assert MapSet.size(BitGraph.vertices(graph)) == 2
      assert MapSet.size(BitGraph.out_edges(copy, :a)) == 1
      assert MapSet.size(BitGraph.in_edges(copy, :b)) == 1

      assert BitGraph.get_vertex(copy, :a, [:opts, :label]) == "a"
      assert BitGraph.get_vertex(copy, :b, [:opts, :label]) == "b"
      assert BitGraph.get_edge(copy, :a, :b) |> Map.get(:opts) == edge_data
    end

    test "add vertex" do
      graph = BitGraph.new()
      graph = BitGraph.add_vertex(graph, "A")
      assert graph.vertices.num_vertices == 1
      ## Adding existing vertex should not increase the number of vertices
      graph = BitGraph.add_vertex(graph, "A")
      assert  BitGraph.num_vertices(graph) == 1
      ## Adding a new vertex should increase the number of vertices
      graph = BitGraph.add_vertex(graph, "B")
      assert BitGraph.num_vertices(graph) == 2
    end

    test "get/update vertex info" do
      graph = BitGraph.new()
      vertex_data = [label: "a", weight: 1]
      graph = BitGraph.add_vertex(graph, :a, vertex_data)
      assert BitGraph.get_vertex(graph, :a, [:opts]) == vertex_data
       and BitGraph.get_vertex(graph, :a, [:opts, :weight]) == 1
       and BitGraph.get_vertex(graph, :a, [:vertex]) == :a
      refute BitGraph.get_vertex(graph, :a, [:something])

      updated_data = [label: "a2", weight: 2]
      graph = BitGraph.update_vertex(graph, :a, updated_data)
      assert BitGraph.get_vertex(graph, :a, [:opts]) == updated_data

      ## Vertex not in graph
      refute BitGraph.get_vertex(graph, :c)
      refute BitGraph.update_vertex(graph, :c, vertex_data)
    end

    test "add edge" do
      graph = BitGraph.new()
      graph = BitGraph.add_edge(graph, "A", "B")
      assert BitGraph.in_edges(graph, "A") == MapSet.new([])
      [a_b_edge] = BitGraph.in_edges(graph, "B") |> MapSet.to_list()
      assert a_b_edge.from == "A"
      assert a_b_edge.to == "B"
      graph = BitGraph.add_edge(graph, "B", "A")
      [b_a_edge] = BitGraph.out_edges(graph, "B") |> MapSet.to_list()
      assert b_a_edge.from == "B"
      assert b_a_edge.to == "A"
      assert 2 == BitGraph.edges(graph, "A") |> MapSet.size()
      assert 2 == BitGraph.edges(graph, "B") |> MapSet.size()
      assert 2 == BitGraph.num_edges(graph)
      graph = BitGraph.add_edge(graph, %BitGraph.E{from: "C", to: "A"})
      assert 3 == BitGraph.edges(graph, "A") |> MapSet.size()
      assert 1 == BitGraph.edges(graph, "C") |> MapSet.size()
    end

    test "delete edge" do
      graph = BitGraph.new() |> BitGraph.add_edge(:v1, :v2)
      assert map_size(graph.edges) == 1
      assert adjacent_vertices?(graph, :v1, :v2)
      ## Try to delete non-existing edge
      graph = BitGraph.delete_edge(graph, :v1, :v3)
      assert map_size(graph.edges) == 1
      ## Delete existing edge
      graph = BitGraph.delete_edge(graph, :v1, :v2)
      assert BitGraph.num_edges(graph) == 0
      refute adjacent_vertices?(graph, :v1, :v2)
      ## Delete BitGraph.E
      graph = BitGraph.add_edge(graph, :v3, :v4)
      edge = BitGraph.get_edge(graph, :v3, :v4)
      assert graph |> BitGraph.delete_edge(edge) |> BitGraph.num_edges() == 0
    end

    test "delete vertex" do
      graph = BitGraph.new()
      graph = BitGraph.add_edge(graph, :a, :b)
      assert BitGraph.num_vertices(graph) == 2
      assert BitGraph.vertex_indices(graph) |> Enum.sort() == [1, 2]
      assert map_size(graph.edges) == 1

      assert adjacent_vertices?(graph, :a, :b)

      graph = BitGraph.delete_vertex(graph, :a)
      assert BitGraph.num_vertices(graph) == 1
      assert BitGraph.vertex_indices(graph) == [2]
      assert map_size(graph.edges) == 0
      refute adjacent_vertices?(graph, :a, :b)

    end

    test "neighbors" do
      graph = BitGraph.new()
      graph = BitGraph.add_edge(graph, :a, :b)
      assert BitGraph.in_neighbors(graph, :a) == MapSet.new([])
      assert BitGraph.out_neighbors(graph, :a) == MapSet.new([:b])
      assert BitGraph.in_neighbors(graph, :b) == MapSet.new([:a])
      assert BitGraph.out_neighbors(graph, :b) == MapSet.new([])
      ## Vertex not in graph
      assert BitGraph.in_neighbors(graph, :c) == MapSet.new([])
      assert BitGraph.out_neighbors(graph, :c) == MapSet.new([])
      ## Add BitGraph.E
      graph = BitGraph.add_edge(graph, %BitGraph.E{from: :c, to: :a})
      assert  BitGraph.in_neighbors(graph, :a) == MapSet.new([:c])
      assert  BitGraph.out_neighbors(graph, :c) == MapSet.new([:a])
    end

    test "neighbors, transformations" do
      graph = BitGraph.new()|> BitGraph.add_edge(:a, :b) |> BitGraph.add_edge(:a, :c)
      ## Define transformation of the vertex neighbor indices back to their representation
      neighbors = BitGraph.out_neighbors(graph, :a, shape: fn _graph, _vertex, neighbors ->
        Mapper.new(neighbors, fn neighbor ->
          BitGraph.V.get_vertex(graph, neighbor)
        end)
      end)

      assert is_struct(neighbors, Mapper)

      assert {:ok, :b, iterator} = Iterable.next(neighbors)
      assert {:ok, :c, iterator} = Iterable.next(iterator)
      assert :done = Iterable.next(iterator)

      #
      neighbor_iterator = BitGraph.neighbors(graph, :a, shape: :iterator)
      assert Iterable.to_list(neighbor_iterator) == [:b, :c]
    end

    test "degrees" do
      graph = BitGraph.new()
      graph = BitGraph.add_edge(graph, :a, :b)
      assert BitGraph.in_degree(graph, :a) == 0
      assert BitGraph.out_degree(graph, :a) == 1
      assert BitGraph.in_degree(graph, :b) == 1
      assert BitGraph.out_degree(graph, :b) == 0
      ## Vertex not in graph
      assert BitGraph.in_degree(graph, :c) == 0
      assert BitGraph.out_degree(graph, :c) == 0
      refute BitGraph.isolated_vertex?(graph, :c)
      ## Isolated vertex
      graph = BitGraph.delete_edge(graph, :a, :b)
      assert BitGraph.isolated_vertex?(graph, :a) && BitGraph.isolated_vertex?(graph, :b)

    end

    defp adjacent_vertices?(graph, v1, v2) do
      graph[:adjacency]
      |> Adjacency.get(V.get_vertex_index(graph, v1),
      V.get_vertex_index(graph, v2)
      ) == 1
    end

  end

  test "subgraph (detached)" do
    graph = BitGraph.new() |> BitGraph.add_vertices([:a, :b, :c, :d]) |> BitGraph.add_edges(
      [
        {:a, :b}, {:a, :c}, {:a, :d},
        {:b, :c}, {:b, :d},
        {:c, :d}
      ])

     subgraph = BitGraph.subgraph(graph, [:a, :b, :c])
     assert_subgraph(subgraph)
     ## The parent graph is not affected
     assert BitGraph.num_vertices(graph) == 4
     assert BitGraph.num_edges(graph) == 6
     ## Removing vertex from parent graph does not affect a detached subgraph
     graph2 = BitGraph.delete_vertex(graph, :a)
     assert BitGraph.num_vertices(graph2) == 3
     assert_subgraph(subgraph)
     ## Removing vertex from subgraph does not affect the parent graph
     _subgraph2 = BitGraph.delete_vertex(subgraph, :a)
     assert BitGraph.num_vertices(graph) == 4

  end

  test "subgraph (mapped)" do
    graph = BitGraph.new() |> BitGraph.add_vertices([:a, :b, :c, :d]) |> BitGraph.add_edges(
      [
        {:a, :b}, {:a, :c}, {:a, :d},
        {:b, :c}, {:b, :d},
        {:d, :c}
      ])
    subgraph = BitGraph.subgraph(graph, [:a, :b, :c], :mapped)
    assert BitGraph.out_neighbors(subgraph, :a) == MapSet.new([:b, :c])
    assert BitGraph.in_neighbors(subgraph, :c) == MapSet.new([:a, :b])
    assert Iterable.count(BitGraph.neighbors(subgraph, :d)) == 0
  end

  test "subgraph in DFS" do
    # Two strong components, connected with a single edge
    graph = BitGraph.new() |> BitGraph.add_edges(
      [
        ##Cycle 1
        {:x1, 1}, {2, :x1},
        {:x2, 2}, {1, :x2},
        ## Connecting edge
        {:x3, 2},
        ## Cycle 2
        {:x3, 4}, {3, :x3},
        {:x4, 3}, {4, :x4}
      ]
    )

    cycle1 = [:x1, 1, :x2, 2]
    cycle2 = [:x3, 4, :x4, 3]

    ## The full graph has two strong components (cycles)
    ## It's not strongly connected (otherwise ti would have a single SCC)
    assert BitGraph.strong_components(graph) |> Enum.sort() ==
      [MapSet.new(cycle1), MapSet.new(cycle2)] |> Enum.sort()
    refute BitGraph.strongly_connected?(graph)
    ## The cycles as subgraphs are strongly connected
    assert Enum.any?([cycle1, cycle2], fn c ->
      graph
      |> BitGraph.subgraph(c, :mapped)
      |> BitGraph.strongly_connected?() end)
  end


  defp assert_subgraph(subgraph) do
    assert Enum.sort(BitGraph.vertices(subgraph)) == Enum.sort([:a, :b, :c])
    assert BitGraph.num_edges(subgraph) == 3
    assert BitGraph.out_neighbors(subgraph, :a) == MapSet.new([:c, :b])
    assert BitGraph.out_neighbors(subgraph, :b) == MapSet.new([:c])
    assert BitGraph.in_neighbors(subgraph, :b) == MapSet.new([:a])
    assert BitGraph.in_neighbors(subgraph, :c) == MapSet.new([:a, :b])
  end
end