I've found that Zig is an excellent tool for implementing data-structure-oriented libraries. Comptime genericity is simple to understand and use, providing a C interface is very easy, and libraries take an allocator, so any memory-safety issues are the consumer's problem. If you want to use it from a memory-safe language, well, all of those have C FFIs so far as I know, Rust very much included, so you can.
A hypergraph is clearly a data structure which demands a lot of cyclic references, no getting around that, so I'm curious: can you compare and contrast the experience of implementing this in Rust vs. Zig?
Thanks for the feedback! Developing/prototyping is a very pleasant experience in Zig compared to Rust. It's obviously a different approach and some might find the tooling less mature but I quickly realized that the build system (as per 0.13.0) is very solid. You can build the docs, run the tests, etc. I'm a Neovim user and honestly the LSP (ZLS) is stable and you can additionally get the compilation errors (you need to create a check step in your build file). In tests, using with the testing allocator to catch memory leaks guides you while prototyping.
This is a well put description of my experience when implementing the same data structures in both Rust and Zig. it probably would not be a good idea, but sometimes I wish I had some kind of 'inline Zig' macro in Rust to pull out when doing that type of work
> A hypergraph is clearly a data structure which demands a lot of cyclic references...
Does it? The easiest data structure is a 2d array with rows corresponding to nodes and columns corresponding to edges. If nodes aren't allowed to touch an edge more than once, it's just a matrix of bools. No references needed!
An index into a common data structure is a sort of reference. It's one which Rust strongly encourages. There are other ways to do it as well, including references in the classic pointer sense.
But yes, a hypergraph will have a lot of vertices referencing each other along (hyper)edges, however you choose to implement it. These can, and often do, form cycles, so again, no matter how the implementation is constructed, it has to handle that.
You'll have to check out the source for details on how this one is implemented, I wouldn't dream of spoiling the fun.
> But yes, a hypergraph will have a lot of vertices referencing each other along (hyper)edges, however you choose to implement it.
No, this is simply not true. A pair of integers indexing into a matrix does not require a reference to anything except for one to the container. Hypergraphs are equivalent to bipartite graphs through the incidence matrix construction. Vertices simply do not need to reference one another.
I'm speaking as a seasoned graph theorist who has been using zig and rust for about as long as zig has existed. Your implementation has some nice features but it is far from the only way of doing things.
Internally both the hyperedges and the vertices are stored as an AutoArrayHashmap with the associated data and the relations (
https://github.com/yamafaktory/hypergraphz/blob/9f87e705afd7...). Then the implementation diverge since a given hyperedge can hold zero to n vertices, with self-loops (ArrayList). For vertices, we just need to keep track of the hyperedges (AutoArrayHashmap).
I've found that Zig is an excellent tool for implementing data-structure-oriented libraries. Comptime genericity is simple to understand and use, providing a C interface is very easy, and libraries take an allocator, so any memory-safety issues are the consumer's problem. If you want to use it from a memory-safe language, well, all of those have C FFIs so far as I know, Rust very much included, so you can.
A hypergraph is clearly a data structure which demands a lot of cyclic references, no getting around that, so I'm curious: can you compare and contrast the experience of implementing this in Rust vs. Zig?
Does it? The easiest data structure is a 2d array with rows corresponding to nodes and columns corresponding to edges. If nodes aren't allowed to touch an edge more than once, it's just a matrix of bools. No references needed!
But yes, a hypergraph will have a lot of vertices referencing each other along (hyper)edges, however you choose to implement it. These can, and often do, form cycles, so again, no matter how the implementation is constructed, it has to handle that.
You'll have to check out the source for details on how this one is implemented, I wouldn't dream of spoiling the fun.
No, this is simply not true. A pair of integers indexing into a matrix does not require a reference to anything except for one to the container. Hypergraphs are equivalent to bipartite graphs through the incidence matrix construction. Vertices simply do not need to reference one another.
I'm speaking as a seasoned graph theorist who has been using zig and rust for about as long as zig has existed. Your implementation has some nice features but it is far from the only way of doing things.