After my post last night (or this morning), I though a bit more about hypergraphs and started playing with a few ideas for a data structure based on incidence lists (lists of every edge incident on a particular vertex). While I've got something that works (after a fashion and in a naive and trivial sort of way), I've come to a realisation that I don't really know what a lot of the things I might want to do to such graphs actually mean.
What,if anything, do reflexivity, transitivity and symmetry mean in the context of a hypergraph? I've been trying to figure this out using the composition relation from arrow logic as an example but I'm still not sure I'm getting anywhere.
Be that as it may, I've started working on a prototype of a hypergraph package for Haskell and if I can figure out how various things ought to work and how to generalise it to relations of arbitrary arity, I'll release it separately.
1 comment:
A transitive reflexive hypergraph is, for the most part, a category. There is some work on computational category theory out there, so you may try looking to see what those guys have done. Symmetry in the case of a category means that you have what's called a "groupoid" - every arrow has an inverse.
Doing things the category theoretic way, you would store the arrows, which consist of only the domain and codomain. That is, the vertex it starts at and the vertex it ends at. You may like to keep something like a bag, where you store each arrow along with its multiplicity -- so a typical entry would be (1,2;3) which says that there are three arrows from vertex 1 to vertex 2.
Post a Comment