Re: [igraph] Random DAG Generation

[Tamas Nepusz]

> This is a nice library. I'm looking to generate a random directed  
> acyclic graph (DAG). I'm not too good at graph theory terminology so  
> I may have missed something in the documentation. Is there a C  
> function that would help me out?
I think there isn't; sampling _uniformly_ from the space of all  
connected directed acyclic graphs with n vertices seems to be a  
complicated problem for me. There's igraph_degree_sequence_game which  
samples uniformly from the space of graphs with a prescribed in- and  
out-degree distribution, but these are not guaranteed to be acyclic.  
There's also igraph_growing_random_game which generates a growing  
directed random graph, where a new vertex is added to the graph in  
every time step and it links to m other vertices already present in  
the graph. This will be acyclic by definition as vertices can only  
link to earlier vertices that are already present. There are some  
other generators for citation networks (i.e.,  
igraph_establishment_game, igraph_cited_type_game,  
igraph_citing_cited_type_game), these may or may not be useful to you,  
depending on what you want to achieve. Neither of these generators  
sample uniformly from the space of all DAGs with n vertices.

--
Tamas