Add support for serde

[garyanaplan]

I'd like to be able to serialise/deserialise my graphs.

I've taken a look at it and the work to add naive support is fairly trivial. Enabling hash brown serialize/deserialize support, adding serde support to the lib and specifying some derives is pretty much all that's required.

If we want to implement it as a feature for (similar to the existing "dot" feature), I think that would also be fairly straightforward.

This would then tie in the library to a long term serialisation format that exposes details about implementation and that might not be desirable. It might be better to have a discussion about the implications of this before going ahead and adding support. One solution could be to provide an implementation that checks for incompatibilities (perhaps version based) and fails if incompatible. That would be more work than just using the derive macros.

What do you think?

[octavonce]

The only problem that I see with this now is how we can maintain determinism across serialization.

Currently, if edges have the default weight, they are sorted lexicographically based on their VertexIds. If I serialize a graph and I send it to another node and it has default edge weights, if the VertexIds are not serialized as well then they will be generated locally on the receiving node, which will yield a different lexicographic ordering.

My question is the following: Would we also serialize VertexIds in order to maintain determinism across serialization, which seems redundant at first glance, or we find another way to maintain determinism across serialization which is not tied to VertexIds?

I know this isn't important in most cases but there are those cases in distributed systems where you must maintain determinism, and a thing like this can potentially break a whole system silently.

[garyanaplan]

My prototyped approach does serialise the VertexIds.

If VertexId s already represent a reliable mechanism for uniquely identifying a vertex, why introduce a new technique? I imagine that any alternative technique would introduce either significant complexity or the same amount of redundancy as just serialising VertexIds.

[octavonce]

I was thinking of adding a trait bound on Vertices for PartialOrd. This would allow custom sorting while removing the VertexId problem.

Another problem with serialization is that VertexIds are deterministically generated by incrementing a local nonce. So if you serialize a graph on machine A which has the local nonce 8 and you send it to machine B which has the nonce 4, if machine B adds a new vertex, the next nonce will be 5 which will result in a collision.

[garyanaplan]

Ok. I hadn't looked at how VertexId is implemented. A quick look convinces me that you don't want to serialise VertexIds.

Perhaps we can leave this open for a while and mark it as an enhancement for 0.5?

[octavonce]

We can go that route as well since it would be simpler and with less complexity for users. However, this would require changing the implementation to generate universally unique ids in order to avoid collisions.

So yeah, I'm good with it, we can do it this way.

[garyanaplan]

One other thing to consider... serde and "no-std" is not straightforward: https://serde.rs/no-std.html

I imagine that anyone using serde and graphlib would want std as well, but, just in case, we'd need to specify something like:

serde = { version = "1.0", default-features = false, features = ["derive"] }

for no-std configurations.

[octavonce]

Yes, and also with the alloc feature since we are already using the alloc crate. This enables back all of the functionality of serde so it should work well with no_std.