Introduce Hypergraph

[ZigRazor]

As for Graph, the library should contains also an Hypergraph class. For more details on hypergraph follow this link https://en.wikipedia.org/wiki/Hypergraph

[nolankramer]

a hypergraph is a generalization of a graph in which an edge can join any number of vertices

Based on this, I can see two modes of thought to designing this in:

Swap backend

Because hypergraphs are a generalization of graphs, it seems like the basis of graphs in CXXGraph should be based on hypergraphs - and Graph (max edge vertices = 2) and Hypergraph (max edge vertices = ∞) classes merely provide convenient API access based on the user's preferred flavor of usage.

This also seems like a significant overhaul in-terms of how the backend code would be structured, and could cause performance degradation to normal 2-vertices-per-edge graphs without careful design considerations. However the big win would be code scalability and maintenance wins.

Split architecture

Just create a completely separate class and offer completely new algorithms specialized for hypergraphs (and maybe reimplement some existing ones for compatibility with hypergraphs).

This may be a good route if we discover that there is significant overhead in using hypergraph-based graphs as the library backend, which would otherwise drag down the performance of users only interested in using classic 2-vertex-per-edge graphs.

[ZigRazor]

I think that the merge of the 2 ideas is the best solution. A generalization of Graph, where Hypergraph is the parent and the Graph is a specialization, in a first istance. Then when we implement the algorithm for hypergraph, we can verify if there are some compatibility to reduce code replication or duplication with some algorithm. In general I think that the algorithm for Hypergraph are valid also for Graph but the opposite is not true. so if we have some generalized algorithm with same performance we can think to reduce code, if the performance are not comparable I think the best solution is the double implementation ( maybe with a unique interface ) What do you think?

[nolankramer]

I think... perhaps we should survey all the kinds of graphs that are out there - in terms of functionality and storage requirements.

We may want to expand even past hypergraphs and graphs - providing weighted graphs, or even graphs where edges can connect to other edges (as a generalization of the hypergraph).

This would require a lot of research and planning before design and implementation - since the basis of all our graphs would need to encompass a fairly large mathematical space (literally all fundamental graph types), and provide adequate facilities to expand functionality and storage as the inheritance chain goes deeper.

This gets tricky for vertices and edges as well - since those definitions could change for specific graphs - meaning a parallel inheritance chain.

---

Barring all that, for now I agree - an inheritance structure makes sense, and generally algorithms operate on the assumption that the underlying structure is a hypergraph (or a constrained version thereof), and specialize implementations for perf reasons if needed.

[nolankramer]

It might make sense to find a math professor or graph PhD to comment here.

[ZigRazor]

It might make sense to find a math professor or graph PhD to comment here.

Yes, does anyone know of a figure like this? @sbaldu @nolankramer