Questiosn about design decisions

[hoijui]

Hey @pnevyk :-)
I did not read the article in discussion #72, but read your comments there. This here is somewhat related.

Disclaimer: I am not a mathematician nor am I in any way a specialist on graphs (especially regarding algorithms). I only had some basic CS classes regarding the topic, and now am tinkering with a project to visualize graphs.
First and foremost, I am an Open Source software architect and coder, rather of the engineering kind. I am not versed in rust/low-level CS engineering stuff (my coder brain was mostly shaped by Java).
I'll relate the story that led me here (with gryf), because I think it is one that might be similar to the story of others that end up here:

I wanted to write a software that visualizes graphs, using rust. I knew I want to store (graph-)data in memory, so I made a little inquiry for what is already out there. I ended up with gryf and petgraph as possible options. I could see petgraph is around much longer, has more contributors, more related crates, .. in short, it looked like a major project. I did like the philosophy of gryf more though. It sounded more engineer-ish, and less mathematician-ish: Thoughts like how to abstract and provide a good interface for the library consumer (coder) seemed to be a major ground for design goals. I started playing around with gryf, and at some point I saw the first graph, visualized. At that point I though, I'd need to layout the graph (aka apply graph drawing), as I just randomly placed the vertices on a plane until then. I came to the fdg crate, which is based on petgraph -> an issue. I saw several ways to proceed:

1. fork fdg and rewrite it using gryf instead of petgraph
2. switch my code to using petgraph
3. write a new graph related crate that serves just as an interface/API of dealing with graphs, which I then implement using both gryf and petgraph as storage backends. Then I would fork fdg and make it use this abstraction layer instead, and make my code use the new abstraction layer as well.
4. implement a storage backend for gryf based on petgraph

I went with 3. and it worked out, though I still have to implement the gryf implementation.
In the process though, I came to know petgraph and gryf a bit better. I saw a lot of similarities, which I guess .. means you started off with petgraph at some point? Either way, there are some design decisions that I do not understand, and would like to ask you about, and then document for others that come around. It revolves mostly about how Directed/Undirected are implemented, and the stuff around VertexId and EdgeId.
Once I understand why it all is as it is, and it is documented, I would have a wish: Try to mince-out these parts into a separate grate ("graph-essentials" or something like that), where you and some of the petgraph devs would have owner/maintainer status, and then switch both grates to use this crate at some point.
In general I feel, like the world would benefit more if I could spend time documenting the code/design decisions behind gryf/petgraph, including how to implement new backends or the like, instead of writing a new crate (the abstraction one), which would likely be of worse quality then either of your crates, both code- and documentation-wise. Also, having some core/essential parts in a shared crate, would allow others to build on it, it would make the two crates more compatible, and you could still publicly re-export (use) these parts under the same namespace location as where they were before. In the best case, it could also become a starting-point for CS students to build their implementations on, or to read about intricate design decisions (both for rust-coding and graph-coding), if the documentation is thorough.

In my dream, we would end up with an overall better documented field of in-memory graph crates in rust, and gryf serving as a kind of facade/abstraction layer for graphs, and new algorithms (e.g. other graph-drawing ones next to fdg) being implemented on it, and yet they could still be used on petgraph as well.

Questions

1. Why are Directed/Undirected not variants in a single enum?
2. Why is the G generic param not restricted to be a GraphBase in pub struct Graph<V, E, Ty: EdgeType, G = AdjList<V, E, Ty, DefaultId>> { ...?

I will probably come up with/remember more, but that is it for now (am a bit tired).

Sorry for the overall structure of this post; I am not used to do this.

[pnevyk]

Hi @hoijui . Thank you for the interest in gryf and writing down your thoughts.

To your questions:

Why are Directed/Undirected not variants in a single enum?

Having the direction encoded on the type level has these positive consequences:

• Avoiding invalid actions which would otherwise require a dedicated error variant or panic. For example, topological sort makes sense only on directed graphs, so gryf restricts the input graphs to be directed at compile time.
• Enabling performance optimizations. Since the values of is_directed and directions are known at compile time, the compiler can use this information to generate more efficient code, for example by eliminating branches (1, 2) or unrolling loops (1). I don't have any benchmarks though.

Why is the G generic param not restricted to be a GraphBase in pub struct Graph<V, E, Ty: EdgeType, G = AdjList<V, E, Ty, DefaultId>> { ...?

I tend to avoid specifying trait constraints on the struct definition when it's not required for the struct definition itself, and leave that for constraints in impl blocks or individual methods. It's a kind of application of this Rust API guideline. For example, HashMap in the standard library doesn't constrain K: Hash in the struct definition either.

Regarding your issue and thoughts:

If your graphs are not very big and your use case is not performance sensitive, how about creating the graph in gryf and then implement a conversion into/from petgraph types to be able to use it with fdg? If you can accept the performance hit, this seems to me as having the good parts of both (API of gryf, ecosystem of petgraph) with reasonable effort.

I could see petgraph is around much longer, has more contributors, more related crates, .. in short, it looked like a major project. I did like the philosophy of gryf more though.

Indeed, petgraph is a well-established project with active contributors and I would recommend petgraph over gryf for serious projects. gryf is an experiment in graph library API design, I wanted to try what's possible. My goal was not really to provide a real "competitor" to petgraph, I would much prefer if petgraph adopted some of the gryf's design to provide better DX to its users and remain the option 1 for graph-related code. As you can definitely see from activity on this repository, I don't have capacity to work on this project anyway.

I am not sure how likely it is that petgraph would change its public API to follow some of gryf's choices. And I didn't make effort in proposing that to petgraph maintainers. Instead, your approach 4 (implementing petgraph graphs as gryf storages) might be easier to accomplish. We discussed it in #110.

Once I understand why it all is as it is, and it is documented, I would have a wish: Try to mince-out these parts into a separate grate ("graph-essentials" or something like that), where you and some of the petgraph devs would have owner/maintainer status, and then switch both grates to use this crate at some point.

I am not sure if this would be the best way forward. Both libraries might have slightly different needs from these types and trying to figure out a common representation would mean effort and compromises with unclear benefit. Instead, some other form of integration (for example petgraph graph as gryf storage) seems easier to me.

Feel free to ask more questions. I will see what I can do about the petgraph integration.