Hacker News new | ask | show | jobs
by klyrs 646 days ago
> 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!
1 comments
samatman 646 days ago
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.

link
klyrs 645 days ago
> 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.

link
yamafaktory 645 days ago
Author here - I'm not using pointers in my implementation but indexes as you mentioned.
link