pythonrandomgraphnetworkxbellman-ford

How can I create random single source random acyclic directed graphs with negative edge weights in python


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?


Solution

  • 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.