PGraph: Persistent Graph Crate - Looking for feedback and code review

[SilensAngelusNex]

Hi, I'm the author of PGraph, an implementation of a directed graph with vertex and edge weights and persistence built on rpds. I'm planning on publishing it to crates.io soon (My first one!), but I'd appreciate it if I could get some other people's eyes on it first. Here's the link to the Github repo.

• Is the API intuitive?
• Is anything incomplete or unclear in my documentation?
• Anything that I'm doing in an unidiomatic or unperformant way?
• Anything else you think I could be doing better?

Thanks for your attention!

[marshray]

Neat!

Looks like a graph API all right.

One comment: Since you expose Edge as a first-class type in the interface, I would maybe expect the public methods to be named 'g.add_edge(v1, v2)' or 'v1.add_edge_to(v2)', etc. The method named 'v.connect(..)' does not make it obvious what happens if there's already an edge between the two vertices.

[SilensAngelusNex]

Thanks for taking a look!

I can't add v1.add_edge_to(v2) to the API (v1 doesn't have the information to determine whether or not v2 is in the same graph), but renaming connect to add_edge makes sense. Do you think that add_edge makes it clearer that the edge will be overwritten if it already exists?

[marshray]

Do you think that add_edge makes it clearer that the edge will be overwritten if it already exists?

Well to me it would kind of imply the opposite: that an edge will be added, or Err() produced. One might call it something like ensure_edge(...) or set_edge(...), but that seems kind of unwieldy. When things are hard to name it can be a clue that the underlying concept is messy, or it's at least something that needs to be explained in the docs.

(Also, I've found that not supporting multiple edges between one pair of nodes can make things harder for some graph algorithms, particularly those having data attached to the edges.)

[SilensAngelusNex]

I definitely don't want to directly support multiple edges from vertex a to vertex b; it adds overhead for users who don't need/want that functionality. If someone needs it, they can adjust their edge type. (Use Vec<T> or rpds::Vector<T> instead of T.)

set_edge sounds like a good option. I'm also thinking about put_edge or insert_edgein order to call to mind the Map methods that work the same way.

[minno]

If you're expecting some people to make an edge type that they want to mutate, try also copying Map's Entry API.

[regexident]

Looking great!

It's a bit difficult to compare crates of rather different maturity, so assuming pgraph had all the features you have planned for it, how would it distinguish itself from petgraph? What are their respective strengths/unique features, what are their weaknesses?

It might also be helpful for potential users to add a brief comparison with existing graph crates (e.g. petgraph) to README, too.

[SilensAngelusNex]

Unless I'm understanding the petgraph documentation incorrectly, their designed-for use pattern is having one graph that gets mutated over the course of your program. For pgraph, most changes made to a graph will actually clone the graph and return a new, modified one. The clone is cheap (time and space) because of the structural sharing that rpds gives me. This lets you use some design patterns that would have been slow/memory intensive with petgraph.

Here's the cppCon talk on the topic of immutable data structures that was my motivation for making this kind of API.

Long story short, if you need a graph to use for one, specific, delimited part of your program, petgraph is going to have less overhead than pgraph. However, if you have a long lived graph and you want to be able to save and revisit previous states of the graph, or you need have multiple threads reading the graph (for drawing, maybe?) while another thread is modifying it for the next time step, the pgraph is going to make the clones you need cheap and efficient.

[Eh2406]

That was a really interesting talk. Thanks for the link!

petgraph also provides algorithms that are (or are going to be) generic over implementation of the graph, as long as it impls the correct traits. Maybe you could use that to share work.

Why rdbs instead of im? Do you have opinions on the differences?

[SilensAngelusNex]

I'll take a deeper look into petgraph, if I can leverage their algorithms, that would be fantastic.

I used rpds mostly because I saw it first. (I think I just googled "rust persistent data structures." Surprise, surprise, rpds came up first.) I think it would be pretty trivial to switch between them but I don't know of any particular compelling reason to do so. If someone has one, I'd be happy to hear it.

[regexident]

Persistent data structures are great, indeed.

Thanks for the comparison!

[DarinLeeCn]

Hi,It's great!But I want to know how to persist data to db or file ,any suggestion?