Minimal sub arborescence

I was playing with this during lunch and came up with this:

defmodule Arby do
  @doc """
  Finds the minimal sub arborescence containing all the vertices in `vertices` of the given arborescence `graph`.
  """
  @spec minimal_sub_arborscence(Graph.t(), Graph.label()) :: Graph.t()
  def minimal_sub_arborscence(graph, vertices) do
    if Graph.is_arborescence?(graph) do
      do_minimal_sub_arborscence(graph, vertices)
    else
      raise("Graph should be arborescence!")
    end
  end

  defp do_minimal_sub_arborscence(graph, vertices) do
    vertices
    |> Enum.map(&Graph.Utils.vertex_id/1)
    |> then(&fully_connected_vertex_ids(graph, &1))
    |> MapSet.to_list()
    |> then(&Map.take(graph.vertices, &1))
    |> Map.values()
    |> then(&Graph.subgraph(graph, &1))
  end

  @doc """
  Considers the given arborescence `graph` and the given list of vertex_ids,
  returning a MapSet of vertex_ids representing the minimal set
  required for all vertexes to be connected.
  """
  @spec fully_connected_vertex_ids(Graph.t(), [Graph.vertex_id()]) :: MapSet.t()
  def fully_connected_vertex_ids(graph, vertex_ids) do
    fully_connected_vertex_ids(graph, vertex_ids, MapSet.new(vertex_ids))
  end

  @spec fully_connected_vertex_ids(Graph.t(), [Graph.vertex_id()], MapSet.t()) :: MapSet.t()
  def fully_connected_vertex_ids(_graph, [], accumulated_vertex_ids) do
    accumulated_vertex_ids
  end

  def fully_connected_vertex_ids(
        graph,
        [vertex_id | remaining_vertex_ids],
        accumulated_vertex_ids
      ) do
    fully_connected_vertex_ids(
      graph,
      remaining_vertex_ids,
      MapSet.union(accumulated_vertex_ids, Map.get(graph.in_edges, vertex_id))
    )
  end
end

I think it’s better because I am fully exploiting the arborescence structure. In such a structure, every “vertex” has exactly 1 parent. So the fully_connected_vertex_ids/2 function just uses graph.in-edges to “get the parent” of each vertex we care about, until we have a final MapSet of vertex_ids representing a fully connected set of vertexes.

Once you have this, it’s a simple matter of making a subgraph.

Here’s my test module for that code:

defmodule ArbyTest do
  use ExUnit.Case
  doctest Arby

  @doc """
  It looks like this:

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

  """
  def example_graph() do
    Graph.new()
    |> Graph.add_edge(:a, :b)
    |> Graph.add_edge(:b, :d)
    |> Graph.add_edge(:b, :e)
    |> Graph.add_edge(:b, :f)
    |> Graph.add_edge(:a, :c)
    |> Graph.add_edge(:c, :g)
  end

  describe "minimal_sub_arborscence/2" do
    test "gets minimal_graph with reduced set of vetices" do
      graph = example_graph()

      for {input, expected_output} <- [
            {[:c, :d, :e], [:a, :b, :c, :d, :e]},
            {[:d, :f], [:b, :d, :f]}
          ] do
        assert graph
               |> Arby.minimal_sub_arborscence(input)
               |> Map.get(:vertices)
               |> Map.values() == expected_output
      end
    end
  end

  describe "arborescence assumptions" do
    test "arborescent graphs permit only 1 parent per vertex" do
      graph =
        example_graph()
        |> Graph.add_edge(:z, :b)

      refute Graph.is_arborescence?(graph)
    end
  end
end

I took another look at this and realized my code is wrong. For the extra test cases:

            {[:b, :d, :g], [:a, :b, :c, :d, :g]},
            {[:b, :d], [:b, :d]},

it fails

Thank you so much for answering my question. I really appreciate that.

I’m thinking maybe it’s easier to solve the problem by converting the arborescence to an inverted tree then finding the minimal sub inverted tree. Just find the path of each given vertex to the root, then eliminate the common part of all the paths except for the first vertex in it.

Building an inverted tree can be done in O(|V|), and the worst case of finding the sub inverted tree can be O(|V|^2), which is not a big deal considering each of my graphs can have at most several tens of vertices. I’ll try this idea tomorrow.

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!

Thank you for your advice. From that, I came up with this piece of code:

defmodule Arborescences 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, [root]) do
    Graph.new(type: :directed)
    |> Graph.add_vertex(root)
  end

  defp do_minimal_sub_arborescence(graph, vertices) do
    in_edges = Enum.flat_map(vertices, &Graph.in_edges(graph, &1))

    parents =
      in_edges
      |> Stream.map(&Map.get(&1, :v1))
      |> Enum.uniq()

    parent_arborescence = do_minimal_sub_arborescence(graph, parents)
    Graph.add_edges(parent_arborescence, in_edges)
  end
end

And after tweaking a while, a tail-recursive solution:

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

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

  defp do_minimal_sub_arborescence(graph, vertices, continuation) do
    in_edges = Enum.flat_map(vertices, &Graph.in_edges(graph, &1))

    parent_vertices =
      in_edges
      |> Stream.map(&Map.get(&1, :v1))
      |> Enum.uniq()

    do_minimal_sub_arborescence(graph, parent_vertices, fn acc_arborescence ->
      acc_arborescence
      |> Graph.add_edges(in_edges)
      |> continuation.()
    end)
  end
end

That’s pretty good! The only test case that fails is when you use [:b, :d]. It mistakenly includes :a in the minimal subgraph.

Yup. I’ll see what I can do to fix it.

I found that I mistakenly assumed that all the vertices in the argument vertices are on the same level, which is definitely not the case.

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

well done!