Bellman-Ford implementation using ETS

bellman_ford.ex

defmodule BellmanFord2 do
  @moduledoc """
  The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single
  source vertex to all of the other vertices in a weighted digraph.
  It is capable of handling graphs in which some of the edge weights are negative numbers
  Time complexity: O(VLogV)
  """

  @type distance :: %{Graph.vertex_id() => integer}

  @doc """
  Returns nil when graph has negative cycle.
  """
  @spec call(Graph.t(), Graph.vertex()) :: [Graph.vertex()] | nil
  def call(%Graph{vertices: vs, edges: meta} = g, a) do
    distances = a |> Graph.Utils.vertex_id() |> init_distances(vs)

    weights = Enum.map(meta, &edge_weight/1)

    for _ <- 1..map_size(vs),
        edge <- weights do
      update_distance(edge, distances)
    end

    if has_negative_cycle?(distances, weights) do
      nil
    else
      distances
      |> :ets.tab2list()
      |> Map.new(fn {k, v} -> {Map.fetch!(g.vertices, k), v} end)
    end
  end

  @spec init_distances(Graph.vertex(), Graph.vertices()) :: distance
  defp init_distances(vertex_id, vertices) do
    tab = :ets.new(:distances, [:set, :private, :compressed])

    init =
      Enum.map(vertices, fn
        {id, _vertex} when id == vertex_id -> {id, 0}
        {id, _} -> {id, :infinity}
      end)

    :ets.insert_new(tab, init)

    tab
  end

  @spec update_distance(term, distance) :: distance
  defp update_distance({{u, v}, weight}, distances) do
    [{_, du}] = :ets.lookup(distances, u)
    [{_, dv}] = :ets.lookup(distances, v)

    if du != :infinity and du + weight < dv do
      :ets.update_element(distances, v, {2, du + weight})
    else
      distances
    end
  end

  @spec edge_weight(term) :: float
  defp edge_weight({e, edge_value}), do: {e, edge_value |> Map.values() |> List.first()}

  defp has_negative_cycle?(distances, meta) do
    Enum.any?(meta, fn {{u, v}, weight} ->
      [{_, du}] = :ets.lookup(distances, u)
      [{_, dv}] = :ets.lookup(distances, v)

      du != :infinity and du + weight < dv
    end)
  end
end