Minimal sub arborescence

Questions & Help Questions
,
1

Hi, all,

I’m trying to solve a problem with an arborescence (a fancy name for a directed acyclic graph which has a single “root” that has a unique path to every other vertex).

Now I’m trying to find the minimal sub arborescence given an arborescence and a list of vertices that must appear in the sub arborescence.

For example, given an arborescence

    a
   / \
  b   c
 /|\   \
d e f   g

and a list of vertices

[c, d, e]

The algorithm should return

    a
   / \
  b   c
 / \   
d   e

and when given the same arborescence but the vertices list [d, f], it should return

  b
 / \
d   f

I’m using libgraph now, but it’s okay to switch to Erlang’s digraph if needed.

Here’s my code for now:

defmodule Arborescences do

  @doc """
  Finds the closest common ancestor vertex of the vertices `v1` and `v2` in the given arborescence `graph`.
  """
  @spec closest_common_ancestor(Graph.t(), Graph.vertex(), Graph.vertex()) :: nil | Graph.vertex()
  def closest_common_ancestor(graph, v1, v2) do
    with root when not is_nil(root) <- Graph.arborescence_root(graph) do
      case {v1, v2} do
        {^root, _v2} -> root
        {_v1, ^root} -> root
        _ ->
          path1 = Graph.dijkstra(graph, root, v1)
          path2 = Graph.dijkstra(graph, root, v2)

          # Meh!
          List.last(path1 -- (path1 -- path2))
      end
    end
  end

  @doc """
  Finds the closest common ancestor vertex of all the vertices in `vertices` in an arborescence `graph`.
  """
  @spec closest_common_ancestor(Graph.t(), [Graph.vertex()]) :: nil | Graph.vertex()
  def closest_common_ancestor(_graph, []), do: nil

  def closest_common_ancestor(graph, [vertex]) do
    if Graph.has_vertex?(graph, vertex), do: vertex, else: nil
  end

  def closest_common_ancestor(graph, [v1, v2 | rest]) do
    ancestor = closest_common_ancestor(graph, v1, v2)
    closest_common_ancestor(graph, [ancestor | rest])
  end

  @doc """
  Finds the minimal sub arborescence containing all the vertices in `vertices` of the given arborescence `graph`.
  """
  @spec minimal_sub_arborscence(Graph.t(), [Graph.vertex()]) :: Graph.t()
  def minimal_sub_arborscence(graph, vertices) do
    do_minimal_sub_arborscence(graph, Enum.uniq(vertices))
  end

  defp do_minimal_sub_arborscence(_graph, []) do
    Graph.new(type: :directed)
  end

  defp do_minimal_sub_arborscence(graph, [vertex]) do
    if Graph.has_vertex?(graph, vertex) do
      Graph.new(type: :directed) |> Graph.add_vertex(vertex)
    else
      Graph.new(type: :directed)
    end
  end

  defp do_minimal_sub_arborscence(graph, vertices) do
    subroot = closest_common_ancestor(graph, vertices)
    for dist <- vertices, reduce: Graph.new(type: :directed) do
      subgraph ->
        graph
        |> Graph.dijkstra(subroot, dist)
        |> Kernel.||([subroot])
        |> Enum.chunk_every(2, 1, :discard)
        |> Enum.reduce(subgraph, fn [v1, v2], subgraph ->
          Graph.add_edges(subgraph, Graph.edges(graph, v1, v2))
        end)
    end
  end
end

This code is far from optimal because it’s doing Dijkstra pathfinding too many times. How can I optimize such algorithm?

Thanks! :smiley: