7 ms·

Show HN: Hypergraph, a data structure library to generate directed hypergraphs

47 points by yamafaktory 5y ago

jesuslop 5y ago
What would you use it for?
- yamafaktory 5y ago
  Social media for example.
- ABeeSea 5y ago
  Not sure if “it” refers to this particular package or hyper graphs in general. Simplicial complexes are widely used in mathematics for many decades and they are simply hyper graphs where every subset of an edge is an edge. So take the tetrahedron, for example. If (x1, x2, x3) are connected by a hyperedge (technically one of the triangular faces of the tetrahedron), then (x1,x2), (x1,x3) and (x2,x3) are also hyperedges (the lines bordering the tetrahedron face). A general hypergraph removes the subsets of edges are edges property.
  - gspr 5y ago
    And for simplicial complexes there's a neat data structure: https://arxiv.org/abs/2001.02581 https://arxiv.org/abs/2001.02581 It's implemented (minus some features) in e.g. GUDHI.
    - jesuslop 5y ago
      Interesting and saved. Some time ago I wanted to say that if I can represent a graph as an adjacency matrix, then I would have liked to say that an hypergraph is given by an adjacency tensor. I searched for that but couldn't find any previous work in this line.
- mshockwave 5y ago
  The wiki page for hypergraph has some nice applications.
- taliesinb 5y ago
  I've been exploring hypergraphs a lot over the last 12 months. They are an incredibly rich way to look at a lot of existing (and new) mathematics, so much so that I think hypergraphs will have a good chance to become a signature mathematical structure over the next 100 years. Unfortunately people don't yet have a good notion (or notation) for what a hypergraph even is! The wikipedia page is a disaster area, for example. Partly this is due to a lack of careful, general groundwork on how to think about hypergraphs. I'm confident this will get done though -- and aim to play a role in that. My personal view is that you need you really need to adopt an ADT-type viewpoint to do this, but I'll have to leave it at that for now.
  - ad404b8a372f2b9 5y ago
    What's ADT stand for?
    - pdimitar 5y ago
      Not the parent commenter but I'd still presume they meant Algebraic Data Types. Not sure though.
istorical 5y ago
I can't be the only person who has wanted to try bringing the wolfram physics project style hypergraph generation rules into some 3D game engine like unity or unreal but was too intimidated to start. I've done some cool stuff with generating fractals like these ones made by Softology https://www.flickr.com/photos/39445835@N05/albums/72157691360888484 https://www.flickr.com/photos/39445835@N05/albums/7215769136... https://www.flickr.com/photos/39445835@N05/albums/72157681216191183 https://www.flickr.com/photos/39445835@N05/albums/7215768121... using visons of chaos to create .obj files and then importing them as voxels in unreal engine using voxel plugin, but hit some limits quite quickly in terms of data size / memory usage and how large of a fractal structure I could visualize (example: megastructure in this demo of a vr game I was working on https://photos.app.goo.gl/V7NrtG4bCbU3EEwy8 https://photos.app.goo.gl/V7NrtG4bCbU3EEwy8) but would love to try to create some way to visualize and interact with large hypergraph structures in 3d space like the wolfram ones: https://writings.stephenwolfram.com/data/uploads/2020/04/0414img5.png https://writings.stephenwolfram.com/data/uploads/2020/04/041... https://writings.stephenwolfram.com/data/uploads/2020/04/0414img6.png https://writings.stephenwolfram.com/data/uploads/2020/04/041... Wonder if this library could be a good place to start to look into this. you obviously need some language / format to store info about hypergraphs and build them up (what this seems like it could help with?) and then some way to render them or create procedural meshes (which in and of itself will be difficult, although I've seen some people have success with stuff like fractal procedural meshes (https://forums.unrealengine.com/t/wip-procedural-fractal-mesh-generation/29935 https://forums.unrealengine.com/t/wip-procedural-fractal-mes...). The standard noise generation algorithms (perlin, simplex, iq noise, value, voronoi, etc) and rendering algorithms like marching cubes capture all the procedural 'terrain' / structure attention/hype in games and media, but I think cinematic sets or game environments built of hypergraphs or fractals are an unmined/overloocked resource. if I could get a team of 2-5 and enough to pay them for a few years, I feel like you could combine hypergraphs and fractals 'terrain' with ue5 nanite to make the memory requirements of the huge / high fidelity meshes lower and make some really cool stuff.
- yamafaktory 5y ago
  What triggers the initial willingness to implement something with hypergraphs was indeed the Wolfram physics project! https://github.com/yamafaktory/hypergraph/discussions/11#discussioncomment-956923 https://github.com/yamafaktory/hypergraph/discussions/11#dis...
trentnelson 5y ago
Hypergraphs are neat; I used them to implement a perfect hash library in C: https://github.com/tpn/perfecthash https://github.com/tpn/perfecthash.
- neeeeees 5y ago
  Neat! Forgive my ignorance, but what does a perfect hash table (which I came across by skimming your project) buy the user? Even with distinct hashes, is there a way to enable random access to the element without an arbitrarily large array?
junon 5y ago
Something missing from the readme that would be interesting: operation complexity as the number of per-edge vertices rises. Or really, any sort of performance characteristics.
- domnomnom 5y ago
  Coordinate free
keeganpoppen 5y ago
this feels like the best place to ask if anyone has ever messed with hypergraphdb (http://www.hypergraphdb.org/ http://www.hypergraphdb.org/). i've never had the chance, but the model has always intrigued me, and it seems to have a bunch of other ambitious diversions, like its agent-y p2p framework, ontology (OWL) -related stuff, and the prolog-y stuff...
sterlinm 5y ago
For others who also had no idea what a hypergraph is: https://www.quantamagazine.org/how-big-data-carried-graph-theory-into-new-dimensions-20210819/ https://www.quantamagazine.org/how-big-data-carried-graph-th...

47 points by yamafaktory 5y ago

jesuslop 5y ago

What would you use it for?

yamafaktory 5y ago
Social media for example.
ABeeSea 5y ago
Not sure if “it” refers to this particular package or hyper graphs in general. Simplicial complexes are widely used in mathematics for many decades and they are simply hyper graphs where every subset of an edge is an edge. So take the tetrahedron, for example. If (x1, x2, x3) are connected by a hyperedge (technically one of the triangular faces of the tetrahedron), then (x1,x2), (x1,x3) and (x2,x3) are also hyperedges (the lines bordering the tetrahedron face). A general hypergraph removes the subsets of edges are edges property.
- gspr 5y ago
  And for simplicial complexes there's a neat data structure: https://arxiv.org/abs/2001.02581 https://arxiv.org/abs/2001.02581 It's implemented (minus some features) in e.g. GUDHI.
  - jesuslop 5y ago
    Interesting and saved. Some time ago I wanted to say that if I can represent a graph as an adjacency matrix, then I would have liked to say that an hypergraph is given by an adjacency tensor. I searched for that but couldn't find any previous work in this line.
mshockwave 5y ago
The wiki page for hypergraph has some nice applications.
taliesinb 5y ago
I've been exploring hypergraphs a lot over the last 12 months. They are an incredibly rich way to look at a lot of existing (and new) mathematics, so much so that I think hypergraphs will have a good chance to become a signature mathematical structure over the next 100 years. Unfortunately people don't yet have a good notion (or notation) for what a hypergraph even is! The wikipedia page is a disaster area, for example. Partly this is due to a lack of careful, general groundwork on how to think about hypergraphs. I'm confident this will get done though -- and aim to play a role in that. My personal view is that you need you really need to adopt an ADT-type viewpoint to do this, but I'll have to leave it at that for now.
- ad404b8a372f2b9 5y ago
  What's ADT stand for?
  - pdimitar 5y ago
    Not the parent commenter but I'd still presume they meant Algebraic Data Types. Not sure though.

istorical 5y ago

I can't be the only person who has wanted to try bringing the wolfram physics project style hypergraph generation rules into some 3D game engine like unity or unreal but was too intimidated to start. I've done some cool stuff with generating fractals like these ones made by Softology https://www.flickr.com/photos/39445835@N05/albums/72157691360888484 https://www.flickr.com/photos/39445835@N05/albums/7215769136... https://www.flickr.com/photos/39445835@N05/albums/72157681216191183 https://www.flickr.com/photos/39445835@N05/albums/7215768121... using visons of chaos to create .obj files and then importing them as voxels in unreal engine using voxel plugin, but hit some limits quite quickly in terms of data size / memory usage and how large of a fractal structure I could visualize (example: megastructure in this demo of a vr game I was working on https://photos.app.goo.gl/V7NrtG4bCbU3EEwy8 https://photos.app.goo.gl/V7NrtG4bCbU3EEwy8) but would love to try to create some way to visualize and interact with large hypergraph structures in 3d space like the wolfram ones: https://writings.stephenwolfram.com/data/uploads/2020/04/0414img5.png https://writings.stephenwolfram.com/data/uploads/2020/04/041... https://writings.stephenwolfram.com/data/uploads/2020/04/0414img6.png https://writings.stephenwolfram.com/data/uploads/2020/04/041... Wonder if this library could be a good place to start to look into this. you obviously need some language / format to store info about hypergraphs and build them up (what this seems like it could help with?) and then some way to render them or create procedural meshes (which in and of itself will be difficult, although I've seen some people have success with stuff like fractal procedural meshes (https://forums.unrealengine.com/t/wip-procedural-fractal-mesh-generation/29935 https://forums.unrealengine.com/t/wip-procedural-fractal-mes...). The standard noise generation algorithms (perlin, simplex, iq noise, value, voronoi, etc) and rendering algorithms like marching cubes capture all the procedural 'terrain' / structure attention/hype in games and media, but I think cinematic sets or game environments built of hypergraphs or fractals are an unmined/overloocked resource. if I could get a team of 2-5 and enough to pay them for a few years, I feel like you could combine hypergraphs and fractals 'terrain' with ue5 nanite to make the memory requirements of the huge / high fidelity meshes lower and make some really cool stuff.

yamafaktory 5y ago
What triggers the initial willingness to implement something with hypergraphs was indeed the Wolfram physics project! https://github.com/yamafaktory/hypergraph/discussions/11#discussioncomment-956923 https://github.com/yamafaktory/hypergraph/discussions/11#dis...

trentnelson 5y ago

Hypergraphs are neat; I used them to implement a perfect hash library in C: https://github.com/tpn/perfecthash https://github.com/tpn/perfecthash.

neeeeees 5y ago
Neat! Forgive my ignorance, but what does a perfect hash table (which I came across by skimming your project) buy the user? Even with distinct hashes, is there a way to enable random access to the element without an arbitrarily large array?

junon 5y ago

Something missing from the readme that would be interesting: operation complexity as the number of per-edge vertices rises. Or really, any sort of performance characteristics.

domnomnom 5y ago
Coordinate free

keeganpoppen 5y ago

this feels like the best place to ask if anyone has ever messed with hypergraphdb (http://www.hypergraphdb.org/ http://www.hypergraphdb.org/). i've never had the chance, but the model has always intrigued me, and it seems to have a bunch of other ambitious diversions, like its agent-y p2p framework, ontology (OWL) -related stuff, and the prolog-y stuff...

sterlinm 5y ago

For others who also had no idea what a hypergraph is: https://www.quantamagazine.org/how-big-data-carried-graph-theory-into-new-dimensions-20210819/ https://www.quantamagazine.org/how-big-data-carried-graph-th...