Repository navigation
Add support for serde #28
Description
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?
Activity
octavonce commentedon May 22, 2019
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 theVertexIds 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 toVertexIds?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 commentedon May 22, 2019
My prototyped approach does serialise the
VertexIds.If
VertexIds 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 serialisingVertexIds.octavonce commentedon May 22, 2019
I was thinking of adding a trait bound on Vertices for
PartialOrd. This would allow custom sorting while removing theVertexIdproblem.Another problem with serialization is that VertexIds are deterministically generated by incrementing a local nonce. So if you serialize a graph on machine
Awhich has the local nonce8and you send it to machineBwhich has the nonce4, if machineBadds a new vertex, the next nonce will be5which will result in a collision.garyanaplan commentedon May 22, 2019
Ok. I hadn't looked at how
VertexIdis implemented. A quick look convinces me that you don't want to serialiseVertexIds.Perhaps we can leave this open for a while and mark it as an enhancement for 0.5?
octavonce commentedon May 22, 2019
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 commentedon May 22, 2019
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 commentedon May 26, 2019
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.