search

bitwalker / libgraph

A graph data structure library for Elixir projects
MIT License
524 stars 75 forks source link

add leaf_vertices function #69

Closed mmmries closed 1 year ago

mmmries commented 1 year ago

This is a rough draft to address https://github.com/bitwalker/libgraph/issues/68

I don't have a lot of experience with graph theory, so I wasn't sure if the idea of leaf_vertices usually includes root nodes? This current implementation only includes vertices that have an edge pointing to them, and no outgoing edges. In my application code I have a recursive process that scans for leaf vertices that need to be resolved and when there are no leaf vertices left it just grabs all remaining vertices to finish it's work.

mmmries commented 1 year ago

Let's hold of on this change. I was doing some testing and I found that in some cases the edge indices contain a key, but with an empty MapSet. This seems to happen when we add and then later remove vertices.

mmmries commented 1 year ago

it looks like my project is going to take another direction for managing a set of dependencies, so I'll close this PR.

One thing I thought I would mention is that in ran into the fact that delete_vertex has a cost proportional to the size of the overall graph because the code enumerates through the entire in_edges and out_edges map for each vertex delete. I think this could be improved by only checking the edges that are incoming to or outgoing from the vertex being deleted.

This performance may not matter for many or most use-cases of a graph, but in my use case where I'm iteratively discovering and pruning the leaf vertices, it was a performance bottleneck.

Thanks again for the awesome library among all your other community contributions @bitwalker ❤️ 💛 💙 💚 💜