Packages

bitgraph

0.2.9
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
3 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



  import BitGraph.Algorithms.SCC.Utils



  ## Kozaraju's SCC algorithm

  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.run(opts)

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

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

      state =

        Dfs.run(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



  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