HyperEdges and MultiEdges on PropertyGraph

[promontis]

I wonder why you've opted to include hyperedges and multi-edges on the propertygraph. Doesn't that make it somewhat of a hybrid propertygraph?

[ahzf]

Hi,

as I don't know what you might mean when you're talking about a "hybrid propertygraph" I just write down my intention behind those higher level relationships.

Hyperedges are a collection of "normal" edges to group them by some characteristics. Think of a vertex being a supernode in a very large graph and having 1000000 incoming and outgoing edges. Probably they are not all the same. So if you have 999000 edges of type friends and 1000 of type enemies but what to traverse all enemies it would be a very slow traversal as it takes a long time to find the 1000 edges within the group of 1000000 edges. A hyperedge with a single outgoing vertex could now group all enemy-edges giving you a huge speedup. But in my imagination hyperedges should not be limited to group edges only by their type. A better solution is to use a delegate for this decision returning true or false. Additionally a hyperedge can have its own set of properties and especially properties of type delegate which allows you to do calculations on the collection of edges. For example it might return you the oldest friend from the group of friends. This way a hyperedge is some king of index for relationships and a nice way to have something like stored procedures in a graphy way. The only sad thing about this feature that it is not production ready at the moment ;)

Multiedges are a lightweight hyperedges as they just connect multiple vertices without the overhead of being a collection of single edges. In that way multiedges are the equivalent of a collection or enumeration in C#. As this is just an optimization its implementation has not the highest priority for me.

In the future I might also add hypervertices and subgraphs to the library which will allow you to group an entire collection of vertices and edges into a single vertex. The difference between them is when you use hyperevertices the edges between the grouped vertices will be accessible as self-loops/self-edges at the hypervertex but when you use a subgraph they are hidden. Both features will allow you to create hierarchical graphs which speeds up traversals and is an important feature for graph visualization.

[promontis]

Aha, I understand your motivation now. Thnx for explaining.

What I meant with a hybrid propertygraph is that the currently implementation of it, is a graph, a multigraph and a hypergraph, which seems to increase the complexity; a person wanting to use the concept of a graph, is now forced to understand multigraphs and hypergraphs, as they are denoted as typeparams. I do see the power of allowing normal edges to become hyperedges as determined by a delegate... a powerful implementation... kudos!

A wonder if it would be easier if the propertygraph would be a normal graph and to create additional graphs, say PropertyHyperGraph and PropertyMultiGraph? I do reckon that this would introduce additional interfaces and classes, but it reduces complexity for the easier interfaces like a normal graph.

Actually, thinking about it, the following could hold:

• a graph only has vertices and edges (pairs)
• a hypergraph only has vertices and hyperedges
• a hybridhypergraph has vertices, edges and hyperedges, and would use delegates to "upgrade" edges to hyperedges.

Note that I didn't take the multigraph into account.

Is this a feasable solution? Like I said previously, you're a bit more experience in graph theory, so I might be saying some stupid stuff... feel free to correct me :)