Aetherus
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! ![]()
Trending in Questions
Hi all,
I’m working on a Phoenix project where I need to make external HTTP requests and I’m trying to choose between Req and HTTPoison....
New
I’m very new to Elixir, so sorry if this is a silly question:
I am wondering what happens to the mailbox of a process when the machine i...
New
How do I tell Hologram not to escape HTML when substituting into templates?
{Textile.render(@product.long_description)}
escapes the HTM...
New
Background
When trying to execute mix release on a Windows 11 machine for a Phoenix project I get the following error:
* assembling mark...
New
I’d like to create a file with 600 permissions (rw-------), but there’s a race condition if I create it and then change the permissions. ...
New
Is there a way to import record definitions in the iex shell for pretty printing (similar to the rr command in the erl shell)? This woul...
New
When I use Mix.install with a git dependency, using git@github.com:... how do I change the SSH identity used?
I’ve got two Github accoun...
New
Other Trending Topics
Hey there,
I haven’t seen a list of useful Elixir specific skills for the popular AI tools yet so I’m starting one here with my first.
...
New
Hi everyone :waving_hand:
I wanted to share something I’ve been building — NowBlind, a random chat app designed to help people discover ...
New
I fully migrated to my own harness from Anthropic/Gemini and I think it’s time to share it. Welcome DSH, the DeepSeek Harness, fully writ...
New
(I just needed to vent somewhere and LinkedIn is full of hope, or hype, I’m not sure which exactly)
AI dream has many faces, but general...
New
Localize is the next generation localisation library for Elixir. Think of it as ex_cldr version 3.0. The first version will be released ...
New
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #library
- #deployment
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #elixirconf
- #channels
- #exunit
- #code-sync
- #discussion
- #podcasts
- #javascript
- #onsite
- #dialyzer
- #docker
- #authentication
- #ai
- #elixirconf-us
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #blog-post
- #ecto-query
- #elixir-ls
- #phoenix_html
- #iex
- #graphql
- #genstage
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #elixirconf-eu
- #processes
- #security
- #api
- #forms
- #performance










Showing Posts 1 to 10- Show Best Posts
- Show All (oldest first)
- Show All (newest first)
slouchpie
I was playing with this during lunch and came up with this:
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/2function just usesgraph.in-edgesto “get the parent” of each vertex we care about, until we have a finalMapSetof 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:
slouchpie
I took another look at this and realized my code is wrong. For the extra test cases:
it fails
Aetherus
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.
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!
Aetherus
Thank you for your advice. From that, I came up with this piece of code:
Aetherus
And after tweaking a while, a tail-recursive solution:
slouchpie
That’s pretty good! The only test case that fails is when you use
[:b, :d]. It mistakenly includes:ain the minimal subgraph.Aetherus
Yup. I’ll see what I can do to fix it.
I found that I mistakenly assumed that all the vertices in the argument
verticesare on the same level, which is definitely not the case.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.
slouchpie
well done!