Algebraic Hypergraph

[jmatsushita]

Hi there,

I was reading your blog post which mention the possibility of a decomposition for k-edges which could be applied to (IIUC) hypergraphs of with hyperedges of a fixed order k. Have you considered this type, using the (hyper)edge-labelled data type and considering e as a Monoid as you suggest?

data HyperGraph e a = Empty
                    | Vertex a
                    | Connect e (Set (HyperGraph e a))

The more basic type seems like it would also make sense:

data HyperGraph a = Empty
                  | Vertex a 
                  | Overlay (Set (HyperGraph a))
                  | Connect (Set (HyperGraph a))

Would you anticipate difficulties pursuing this further?

Cheers,

Jun

[snowleopard]

@jmatsushita Yes, I've been thinking about such representations to support hyperedges, however, I used lists in my experiments because with Set you essentially force the algebra to be commutative with respect to Connect, i.e. you won't be able to express both 1*2 and 2*1. Perhaps, this is fine for your application.

Another subtlety is that with Set you seem to lose the ability to create single vertices that have self-loops, e.g. 1*1. Strangely you can still create more complex graphs with self-loops such as 1*(1+2): here 1 has a self-loop.

So, Set seems a bit awkward. I'd probably use the following data type as a starting point:

data HyperGraph e a = Vertex a
                    | Connect e [HyperGraph e a]

empty :: Monoid e => HyperGraph e a
empty = Connect mempty []

I haven't done much with representation, so please let me know if you come up with anything interesting!

[snowleopard]

I suggest we keep this PR open, since hypergraphs seem like an interesting direction to explore.