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

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.

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.