Aetherus

Minimal sub arborescence

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!

11 comments

#graphs #algorithm

2 1407 11

2021-11-09 00:11:36 UTC

Most Liked

Aetherus

I finally made it.

I eventually went back to the approach of finding all paths from the root to each given vertex and eliminating the common part of the paths, only this time I didn’t use Dijkstra.

defmodule G do
  def minimal_sub_arborescence(graph, vertices) do
    if Graph.is_arborescence?(graph) do
      do_minimal_sub_arborescence(graph, vertices)
    else
      raise "Not an arborescence"
    end
  end

  defp do_minimal_sub_arborescence(_graph, [vertex]) do
    Graph.new(type: :directed)
    |> Graph.add_vertex(vertex)
  end

  defp do_minimal_sub_arborescence(graph, vertices) do
    paths = Enum.map(vertices, &path_from_root(graph, &1))

    edges = Stream.unfold(paths, fn paths ->
      {
        Enum.map(paths, fn
          [] -> nil
          [h|_] -> h
        end),
        Enum.map(paths, fn
          [] -> []
          [_|t] -> t
        end)
      }
    end)
    |> Stream.drop_while(&all_the_same?/1)
    |> Stream.take_while(&Enum.any?/1)
    |> Stream.flat_map(& &1)
    |> Stream.reject(&is_nil/1)

    Graph.new(type: :directed)
    |> Graph.add_edges(edges)
  end

  defp all_the_same?([_]), do: false
  defp all_the_same?([a, a]), do: true
  defp all_the_same?([a, a | t]), do: all_the_same?([a | t])
  defp all_the_same?([_, _ | _]), do: false

  defp path_from_root(graph, vertex) do
    Stream.unfold(Graph.in_edges(graph, vertex), fn
      [] -> nil
      [edge] -> {edge, Graph.in_edges(graph, edge.v1)}
    end)
    |> Enum.take_while(&not is_nil(&1))
    |> Enum.reverse()
  end
end

Post #11

slouchpie

In a way, you kind of already have the inverted tree in the in_edges. That maps vertexes to their parent vertex.

No need to thank me! I was using the Graph lib recently anyway and I found the question interesting and fun to play with. Post any more solutions here!

Post #6