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