Packages

bitgraph

0.4.8
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 mst kruskal.ex
Raw

lib/algorithms/mst/kruskal.ex 

defmodule BitGraph.Algorithm.MST.Kruskal do

  alias InPlace.UnionFind

  alias BitGraph.V



  def run(graph, opts \\ []) do

    opts = Keyword.merge(default_opts(), opts)

    dist_fun = Keyword.get(opts, :dist_fun)

    sorted_edges =

      graph

      |> BitGraph.edges()

      |> Enum.sort_by(fn %{from: from, to: to} = _edge ->

        dist_fun.(from, to)

      end, :asc)



    num_vertices = BitGraph.num_vertices(graph)

    uf = UnionFind.new(num_vertices)



    {_tree, _weight} = Enum.reduce_while(sorted_edges, {[], 0},

      fn %{from: from, to: to} = _edge, {edges_acc, weight_acc}  = acc ->

        from_idx = V.get_vertex_index(graph, from)

        to_idx = V.get_vertex_index(graph, to)



        if UnionFind.find(uf, from_idx) == UnionFind.find(uf, to_idx) do

          {:cont, acc}

        else

          acc =  {

            [{from, to} | edges_acc],

            weight_acc + dist_fun.(from, to)

          }



          UnionFind.union(uf, from_idx, to_idx)

          if UnionFind.set_size(uf, 1) == num_vertices do

            {:halt, acc}

          else

            {:cont, acc}

          end

        end

    end)

  end



  defp default_opts() do

    [

      dist_fun: fn _v1, _v2 -> 1 end

    ]

  end



end