What happened to the generics?

[U007D]

I'm puzzled, because gamma 0.5 defined the Graph trait as generic over node and edge type. StableGraph had similar generic parameters. But now in 0.8, those are all gone, and nodes seem to be hardcoded as usize, even in the Graph trait as well as in DefaultGraph.

I'm wondering what drove this change and what the recommended practice is to use gamma when the nodes are not usize?

Thanks!

[skairunner]

I am also curious -- coming from the blog post here I was expecting generics as well. And my planned data will probably not be usize, though in theory I could use an external map of data with the graph only storing indices, but that would be quite clunky.

Edit: Okay, so all nodes were instead changed to node indices (usize) in this commit: f168055 . It doesn't seem like any built-in system exists to manipulate data according to node indices. I'm personally unsure whether lifetimes is a good reason to eliminate node data entirely, but it does potentially make it much more cache-friendly to access graphs. Also it might be a good idea to add in some traits for retrieving data by index.

[rapodaca]

Good questions, and I can see how this might seem strange.

For some insight into part of the problem, see #4.

The original design forced a lifetime parameter onto the Graph trait. This complicated the code considerably and it became extremely difficult to implement non-trivial functionality. Just getting the implementation you saw was a massive undertaking.

The main problem I hit is that you can't return a trait object (e.g., Iterator) from a trait method (yet). And the old Graph trait required that because it returned Iterators. I ended up writing a blog post about the difficulties of returning iterators because I found the documentation scattered and surprisingly complex for such a simple task. I didn't want to force Boxed iterators into the Graph because the performance implications were far from clear.

I understand that work by the Rust team is in progress that could allow the return of trait objects from trait methods, and so it might be worth re-visiting when that makes it into stable.

In the meantime, the current approach eliminates the lifetime parameter from Graph. It worked well for the problem I faced, which was building and using molecular graphs. I'd be happy to consider other approaches that allow node IDs to be generic without forcing a lifetime parameter onto Graph.

Regarding what to do if nodes are not usize, I have been kicking around an idea for LabeledGraph, which would allow you to associate values of generic type to nodes and edges.

I haven't moved forward with this, partly because I'm able to avoid it without downside. See ChemCore, which is based on Gamma. It extends Graph as a Molecule trait by defining methods to query a chemically-meaningful node type (Atom). Either this approach, or one with an associated HashMap might work, depending on the application.

[skairunner]

I think a LabeledGraph could be useful.

Edit: After thinking about it for a bit, borrowing makes it so that it's definitely more convenient to have a separate HashMap that maps ids to values so that you could iterate over elements in a Graph while simultaneously modifying values.

[rapodaca]

After review, it seems clear that the benefits of generic node ids don't yet outweigh the costs. Closing.