defmodule BitGraph.Algorithm.SCC.Kozaraju do
  alias BitGraph.{Dfs, Algorithm}

  import BitGraph.Algorithm.SCC.Utils
  import BitGraph.Algorithm

  @behaviour Algorithm

  ## Kozaraju's SCC algorithm
  @impl true
  def run(graph,
      opts \\ []
    ) do
      BitGraph.num_vertices(graph) == 0 && [] ||
    (
    component_handler =
      opts
      |> Keyword.get(:component_handler, {fn component, acc -> [component | acc] end, []})
      |> wrap_component_handler()

    graph
    |> dfs(opts)
    |> Dfs.order(:out, :desc)
    |> Enum.reduce({nil, nil}, fn v, {state_acc, components_acc} ->
      state =
        dfs(graph, vertices: v,
          direction: :reverse,
          state: state_acc,
          process_vertex_fun: fn %{acc: acc} = _state, vertex ->
            MapSet.put(acc || MapSet.new(), vertex)
          end
        )

      component = state[:acc]


      {Map.put(state, :acc, nil),
        component && component_handler.(component, components_acc) || components_acc
      }
    end)
    |> elem(1))
  end

  @impl true
  def preprocess(graph, opts) do
    Dfs.preprocess(graph, opts)
  end

  @impl true
  def postprocess(_graph, res) do
    res
  end

  def strongly_connected?(graph, opts \\ []) do
    try do
      component_handler =  fn component, _acc ->
        throw({:single_scc?, component && (MapSet.size(component) == BitGraph.num_vertices(graph))})
      end

      run(graph,

        Keyword.merge(opts,
        component_handler: component_handler,
        process_vertex_fun: fn(state, vertex, event) ->
          event == :processed && state.dag && throw({:error, :dag, vertex}) || state[:acc] end)
      )
    catch
      {:single_scc?, res} -> res
      {:error, :dag, _vertex} -> false
    end

  end

end