jeudi 20 octobre 2016

Random directed hypergraph generation

A hypergraph is a generalization of a graph where edges (termed hyperedges) can connect more than a single pair of nodes.

In the case of a directed hypergraph, each edge takes the form of a pair of sets, that is, an edge is written as E=(A,B) where A is the set of tail nodes and B is the set of head nodes for hyperedge E.

In addition to being directed, I need the graph to be acyclic (no two hyperedges exist that contain nodes that form a loop by following the direction specified by the respective hyperedges) and connected (every node needs to be a part of at least one hyperedge).

Is there an efficient algorithm for generating such a hypergraph?

Input: 
N - number of nodes (perhaps also specify the number of root nodes)
Ut - global upper bound on number of tail nodes for each hyperedge
Uh - global upper bound on number of head nodes for each hyperedge 
M - max number of hyperedges

Output:
H = (N,E) - a directed, acyclic, connected hypergraph 




Aucun commentaire:

Enregistrer un commentaire