Yog - Yet another Graph Library for Elixir

Your Libraries & OS Mentoring Libraries
,
1

I packed a collection of Graph algorithms into a package.

I intend to nurture this library and battle-test it, it’s still not where I want it to be, but will share updates here, along with blog posts or interesting graph massaging I find along the way.

I had been doing algorithms with Elixir in an older, almost abandoned repo ex_algo and then I had a lot of Advent of Code lessons learned implemented in random folders, last year I had a good time playing with Gleam and that’s when I came up with the idea of Yog.

I am grateful to our very own libgraph <3, Clojure’s Loom, and F#’s FGL - where I collected inspirations from.

Some Kino smart-cell and a blog post is WIP :slight_smile:

11 Likes
2

Thanks for your contribution. I have a more or less trivial game use-case for some path finding on graphs and so far relied on the Erlang standard library. With that it was surprisingly annoying to fetch the metadata of the edges on the path that has been found.

Looking at Path type it seems that this library also returns nothing but nodes on the path. I only skimmed the documentation, but from what I am seeing there is no direct way to associate edges with other data than weights? And there does not seem to be a way to obtain something like an edge ID so I can’t store the metadata myself? So there is no way for me to find out which edges are part of the path?

I hope this doesn’t come along as ungrateful. In my case the edges contain more detailed data on how to visualize the movement and I need to know which edges have been used. The fact that most graph libraries do not cater to my design might be more of an issue on my side. But it still puzzles me that so many libraries gloss over the actual elements that connect the nodes when returning paths.

1 Like
3

Thank you so much for coming to me with a real-life issue you encountered. I am glad that you pointed this out and gave me a chance to make Yog better.

Okay, so let me give an example and see if I understood your issue better :slight_smile: please call me out if there’s a gap in my understanding.

Let’s say you have the following graph:

graph =
  Yog.undirected()
  |> Yog.add_node(1, "Home")
  |> Yog.add_node(2, "Office")
  |> Yog.add_node(3, "Mall")
  |> Yog.add_node(4, "backyard")
  |> Yog.add_edge!(from: 1, to: 2, with: %{distance: 10, by: "Car"})
  |> Yog.add_edge!(from: 2, to: 3, with: %{distance: 5, by: "Walk"})
  |> Yog.add_edge!(from: 1, to: 3, with: %{distance: 10, by: "Bus"})
  |> Yog.add_edge!(from: 1, to: 4, with: %{distance: 0.1, by: "Foot"})
  |> Yog.add_edge!(from: 2, to: 1, with: %{distance: 8, by: "Train"})
  |> Yog.add_edge!(from: 2, to: 4, with: %{distance: 11, by: "Train"})

Now, I made the with (i.e. the Edge metadata) non-numeric, so we have some edge specific data. So, the shortest path, let’s use Dijkstra would be (with custom zero, add, compare configuration so the algorithm knows the math behind our edge data):

Dijkstra.shortest_path(
  graph,
  2,
  4,
  0,
  fn total, b ->
   total + b.distance
    end,
  &Yog.Utils.compare/2
)

Which would give us the Path %Yog.Pathfinding.Path{nodes: [2, 1, 4], weight: 8.1, algorithm: :dijkstra, metadata: %{}}

Which I don’t want. Because I want to draw “Icon” based on “Car”, “Bus”, “Foot” etc.

I’m surprised I didn’t put a convenience function on Path for this! And I thank you for calling it out!

For NOW, how I’d do this is:

edges =
  path.nodes
  |> Enum.chunk_every(2, 1, :discard)
  |> Enum.map(fn [u, v] -> 
    # O(1) because `out_edges` is a map.
    {u, v, graph.out_edges[u][v]}
  end)

And you’d get something like: [{2, 1, %{distance: 8, by: "Train"}}, {1, 4, %{distance: 0.1, by: "Foot"}}]

Now, I would not expect the client of this function to write this, I’d rather add a function, hydrate_path on Path that is like:

def hydrate_path(graph, node_ids) do
  node_ids
  |> Enum.chunk_every(2, 1, :discard)
  |> Enum.map(fn [u, v] -> 
       {u, v, graph.out_edges[u][v]}
     end)
end

I hope I understood your problem right, and could help out. Sorry for not having this as a function already.

Also, this works on simple graphs, multi-graphs are work in progress for now (and it does have edge_id).

4

Most of the Pathfinding functions have a triplet zero, with_add, with_compare functions - I called the semiring but my OCaml friend frowned at me for calling them that.

These are for letting the underlying algorithms know now to calculate distances for edges with non-numerical weight. In fact, the triplet you see in an edge is from, to, with, instead of weight because those are meant to be data structure. Could be [{1, 2, "Friend"}, {2, 1, "Enemy"}] where it’s not a weight (but I guess, a burden) at all.

So the type for add is usually f(type_of(zero), type_of(edge) - like a reducer.

Anyways, I would request anyone to suggest any kind of API improvements here. I got some valuable suggestions in the past that led me to design “Graph Builders” especially- Live Builder and I learned a lot in doing so!

1 Like