search

alex-87 / HyperGraphLib

C++ Hypergraph modelling Library using Boost and OpenMP with some algorithms, including isomorphism using Gecode.
https://alex-87.github.io/HyperGraphLib
MIT License
20 stars 3 forks source link

Support for Directed Hypergraphs? #12

Open scignscape opened 6 years ago

scignscape commented 6 years ago

It would be great to have a directed hypergraph library in C++. Looking at HyperEdge.cpp, it would seem straightforward to split the vertex set into "head set" and "tail set", but I don't know how such modification would affect the analytic parts of the library. Any suggestions? (Sorry for writing in English ...)

m0rsch1 commented 6 years ago

Well, it will affect all traversals. Instead inserting all adjacent nodes into the set of to be visited nodes, only those which are predecessors or successors are added. In summary, the definition of adjacency is now extended: Adjacent(u,v) = Precedes(u,v) || Follows(u,v). Since we work on similar libraries, you may want to have a look: https://github.com/ESANPI2015/hypergraph

scignscape commented 6 years ago

Thanks for the ref! I agree that's an interesting project but I'm not sure generalizing to dimensions beyond "1-edges" gets closer to a "natural" representation for, say, RDF graphs whose nodes have extra "structure". With respect to traversals, there are AFAICT different kinds of queries needing different kinds of traversals. For some relations the edge order and head/tail distinction is inconsequential, so the edges can be regarded as unordered. For others, the traversal can be split into two scales: first work only on the hypernodes, then separately look at nodes "in" whichever hypernode fits a particular criterion. I'm assuming that in those scenarios there's some kind of "type system" on each graph and that nodes inside hypernodes are in some contexts "hidden" like C++ data members.

Perhaps I should look at combining HyperGraphLib with ordinary directed graphs, and have each node in the ordinary graph point to an edge in the hypergraph along with an index dividing the hyperedge into head and tail sets. Then I could traverse the hypergraph when I don't care about head-vs-tail and traverse the ordinary graph when I don't care about "hidden nodes".

Anyways, thanks again ...