Packages

bitgraph

0.1.7
0.4.8 0.4.7 0.4.6 0.4.5 0.4.4 0.4.3 0.4.2 0.4.1 0.3.4 0.3.3 0.3.2 0.3.1 0.2.9 0.2.8 0.2.7 0.2.6 0.2.5 0.2.4 0.2.3 0.2.2 0.2.1 0.1.23 0.1.22 0.1.21 0.1.20 0.1.19 0.1.18 0.1.17 0.1.16 0.1.15 0.1.14 0.1.13 0.1.12 0.1.11 0.1.10 0.1.9 0.1.8 0.1.7 0.1.6 0.1.5 0.1.4 0.1.3 0.1.2 0.1.1 0.1.0

Mutable directed graph

HexDocs

Current section

Files

Jump to
Readme
45 Versions
2 Dependencies
Dependants
Files
Activity
bitgraph lib algorithms scc kozaraju.ex
Raw

lib/algorithms/scc/kozaraju.ex 

defmodule BitGraph.Algorithms.SCC.Kozaraju do

  alias BitGraph.Dfs



  ## Kozaraju's SCC algorithm

  def run(graph,

    component_handler \\ fn component, _state -> component end,

      first_pass_opts \\ []

    ) do

      BitGraph.num_vertices(graph) == 0 && [] ||

      

    graph

    |> Dfs.run(first_pass_opts)

    |> Dfs.order(:out, :desc)

    |> Enum.reduce({nil, []}, fn v, {state_acc, components_acc} ->

      state =

        Dfs.run(graph, 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, state) | components_acc]) || components_acc}

    end)

    |> elem(1)

  end



  def strongly_connected?(graph) do

    try do

      run(graph,

      fn component, _dfs_state ->

        throw({:single_scc?, component && (MapSet.size(component) == BitGraph.num_vertices(graph))})

        end,



        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