Yog - Yet another Graph Library for Elixir

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.

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 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).

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!

I recently added digraph to an Elixir app for some in-memory data analysis. Curious to try this out.

I never directly used Martin Erwig’s functional graph library in Haskell, only the Elm library it inspired. But while respecting its purity, I found it unwieldy to use compared to, say, Cypher.

You mention experimental support for Erwig’s Functional Graph Library, but there are clearly baked-in similarities in Yog in which “All operations return new graphs”. And it is described as type-safe by which it “Leverages Elixir’s type system”. But did you not lose some type safety moving from Gleam to Elixir?

In general, what did you win/lose by changing it from an Elixir wrapper around the Gleam library to be “fully implemented in Elixir with no external runtime dependencies”. What was the big win here because I would almost want those type-safe(r) guarantees.

I guess I’d like to see a comparison between this and other options like digraph. I want the brief summary of this document extended to Elixir and Elixir alternatives. I appreciate that you have built-in graph algorithms and visualizations that digraph lacks.

Thanks for open-sourcing this.

That type system bit is a lie that i missed when I copy/pasted the documentation from the Gleam version (Which was so hard that I couldn’t even OSS it). That bit was removed, and a documentation overhaul is what I am working on right now. Thanks for calling it out.

I agree. Also, persistent graph will always perform worse than classical ones. Although Yog’s FGL being slow would be attributed to my skill issue, I think it’d be slow in general due to all those burning and building!

Yes I did! Not just FGL but the whole thing, the algorithms I open sources in Yog had been lying around my computer for ages - all in Elixir, I unified them in Gleam as I was learning it last year, but also on the side ported the Elixir version in a pretty fun (Elixir → Gleam → Elixir) flow. Tried to use LLM to port the F# version as Gleam → F# code conversion is one of the most satisfying and educational experiences I had.

Elixir wrapper guaranteed type safety (to some extent) because if you tried to add non-integer NodeID then you’d get yelled at by the underlying Gleam library (Not during author-time). That’s what made things like LabeledBuilder useful for YogEx - but now you can just add anything as Node - that led me to work extra hard when thinking about heuristics for A* or lexicographical topological sort, for example.

What I gained from it is, UX! Adding Yog on a livebook is a matter of putting just the one dependency and no surprise errors. To get the gleam wrapped version, you’d also need to include Gleam dependencies and add things like manager: rebar3. Also I’d be at Gleam’s mercy, and it’d be unwise to have some functions wrapped and not others - I did have a elixir ↔ gleam sync check but that has bugs!

Also, after moving to Elixir, I can fearlessly use things like Task.async_stream, :queue or :erlang.phash2 since there’s no JS compatibility I need to worry about - which simplified some function signature. I had a lot more Elixir artifact that I didn’t for Gleam (i.e. some community detection algorithms and greedy traversal) so I ported them immediately.

Totally! Was planning to add this today any way, what a timing :). Didn’t add it earlier because the development in Elixir and Gleam was more intertwined and had history, and the final product were more different than Gleam and F# was, so the comparison is a little more involved.

Elixir is going to be the one receiving more focus and updates from now on though.

I am currently working towards adding more test cases (Porting facts from Python’s NetworkX or adding examples of solving non-trivial real life graphs), working on documentation/wiki, and adding benchmarks. DAG and Multigraph could need some UX overhaul too (Especially multigraph).

Slightly off-topic: You mentioned Elm (and visualization), I am currently learning Lustre (Gleam’s Elm), and I implemented a Yog front-end app here. Elixir doesn’t have anything like that but the Kino smart cell was inspired by it!

These are a few Advent of Code problems solved with Yog - AoC Graph Problems

That was a perfect example, I could more or less use it as a drop-in replacing :digraph. It passes my testsuite and I will compare the runtime behaviour over the next days. But my gut says that switching to your library is worth it just for getting rid of the ETS usage of the standard library.

I tried improving the performance in yesterday’s release, and performance and documentation will remain the focus for the next few weeks. Please let me know how the runtime looks like.

Also, added this thanks to your suggestion

Got some of my old code from “Mazes for Programmers” polished an into Yog.

Just wrote this little maze solver:

# maze_solver_directional.exs
#
# Generates a maze and solves it using Dijkstra's algorithm,
# visualizing the solution path with directional arrows (^ v > <).
#
# Usage: mix run examples/maze_solver_directional.exs

alias Yog.Generator.Maze
alias Yog.Builder.GridGraph
alias Yog.Pathfinding
alias Yog.Render.ASCII

rows = 12
cols = 20

IO.puts("╔════════════════════════════════════════════════════════════╗")
IO.puts("║     MAZE SOLVER WITH DIRECTIONAL ARROWS (^ v > <)          ║")
IO.puts("╚════════════════════════════════════════════════════════════╝")

maze = Maze.recursive_backtracker(rows, cols, seed: 42)
graph = GridGraph.to_graph(maze)

start = 0
goal = rows * cols - 1

IO.puts("\nGenerating #{rows}×#{cols} maze...")
IO.puts("Start: node #{start} (top-left)")
IO.puts("Goal:  node #{goal} (bottom-right)")

case Pathfinding.shortest_path(in: graph, from: start, to: goal) do
  {:ok, path} ->
    IO.puts("\nPath found! Length: #{length(path.nodes)} nodes")

    occupants =
      path.nodes
      |> Enum.chunk_every(2, 1, :discard)
      |> Enum.map(fn [current, next] ->
        direction =
          cond do
            next == current + 1 -> ">"
            next == current - 1 -> "<"
            next == current + cols -> "v"
            next == current - cols -> "^"
            true -> "·"
          end

        {current, direction}
      end)
      |> Map.new()
      |> Map.put(start, "S")
      |> Map.put(goal, "G")

    IO.puts("\nSolution with Directional Arrows:")
    IO.puts("   S = Start, G = Goal, >v<^ = Path direction")
    IO.puts("")
    IO.puts(ASCII.grid_to_string_unicode(maze, occupants))

  {:error, reason} ->
    IO.puts("No path found: #{inspect(reason)}")
end

And get this output:

╔════════════════════════════════════════════════════════════╗
║     MAZE SOLVER WITH DIRECTIONAL ARROWS (^ v > <)          ║
╚════════════════════════════════════════════════════════════╝

Generating 12×20 maze...
Start: node 0 (top-left)
Goal:  node 239 (bottom-right)

Path found! Length: 67 nodes

Solution with Directional Arrows:
   S = Start, G = Goal, >v<^ = Path direction

┌───────┬───────────────────┬───────────────────────────────────────────────────┐
│ S   v │                   │                                                   │
├────   │   ────────┐   ────┘   ┌───────────┬───────────────────────┐   ────┐   │
│ v   < │           │           │           │                       │       │   │
│   │   └───┬───┐   └───────┬───┘   ┌───────┘   ┌───────────────┐   └───┐   │   │
│ v │       │   │           │       │           │               │       │   │   │
│   └───┐   │   ├───────┐   │   ┌───┘   ┌───────┴────────   ┌───┴────   │   │   │
│ >   v │       │       │   │   │       │                   │           │   │   │
├────   ├────   │   │   │   │   │   ┌───┤   ┌───┐   ┌───────┤   ────────┴───┘   │
│ v   < │           │   │   │       │   │   │   │   │       │                   │
│   ────┴───┬───────┤   │   └───┬───┘   │   │   │   │   │   └───────┬───────────┤
│ >   >   v │       │   │       │               │       │           │           │
│   ┌───┐   ├────   │   ├───┐   └───────┬───────┤   ────┴───┐   ────┘   │   ────┤
│   │   │ v │       │   │   │           │ >   v │           │           │       │
│   │   │   │   ────┘   │   └───┬────   │   │   ├────────   ├───────┬───┴────   │
│   │   │ v │           │       │       │ ^ │ v │           │ >   v │           │
│   │   │   └───┐   ────┴────   │   ┌───┘   │   └───────────┘   │   │   ────────┤
│       │ >   v │               │   │     ^ │ >   >   >   >   ^ │ v │           │
├───┐   └───┐   ├───────┬───────┤   │   │   ├───────┬───────────┘   ├───────┐   │
│   │       │ v │ >   v │       │   │   │ ^ │ v   < │ v   <   <   < │ >   v │   │
│   └────   │   │   │   │   │   │   ├───┘   │   │   │   ┌───────┬───┘   │   │   │
│           │ >   ^ │ v │   │       │ >   ^ │ v │ ^   < │ >   v │ >   ^ │ v │   │
│   ────────┴───────┤   │   └───────┘   ┌───┘   └───────┘   │   │   ┌───┘   │   │
│                   │ >   >   >   >   ^ │     >   >   >   ^ │ >   ^ │     >   G │
└───────────────────┴───────────────────┴───────────────────┴───────┴───────────┘

Been writing a NetworkX inspired tutorial.

Created a smart-cell - kino_vizjs to render DOT content to aid in visualizations.

One thing I like about NetworkX is its layout system, and how they rendered graphs with Matplotlib. That’s something I’d like to look into.