how to create random single source random acyclic

问题:

I want to do a execution time analysis of the bellman ford algorithm on a large number of graphs and in order to do that I need to generate a large number of random DAGS with the possibility of having negative edge weights.

I am using networkx in python. There are a lot of random graph generators in the networkx library but what will be the one that will return the directed graph with edge weights and the source vertex.

I am using networkx.generators.directed.gnc_graph() but that does not quite guarantee to return only a single source vertex.

Is there a way to do this with or even without networkx?

回答1:

I noticed that the generated graphs have always exactly one sink vertex which is the first vertex. You can reverse direction of all edges to get a graph with single source vertex.

回答2:

You can generate random DAGs using the gnp_random_graph() generator and only keeping edges that point from lower indices to higher. e.g.

In [44]: import networkx as nx

In [45]: import random

In [46]: G=nx.gnp_random_graph(10,0.5,directed=True)

In [47]: DAG = nx.DiGraph([(u,v,{'weight':random.randint(-10,10)}) for (u,v) in G.edges() if u<v])

In [48]: nx.is_directed_acyclic_graph(DAG)
Out[48]: True

These can have more than one source but you could fix that with @Christopher's suggestion of making a "super source" that points to all of the sources.

For small connectivity probability values (p=0.5 in the above) these won't likely be connected either.