如何在python中创建具有负边权重的随机单源随机无环有向图 [英] how to create random single source random acyclic directed graphs with negative edge weights in python

问题描述

我想在大量图上做bellman ford算法的执行时间分析，为了做到这一点，我需要生成大量的随机DAGS，并有可能存在负边权重。

我在python中使用networkx。在networkx库中有很多随机图形生成器，但是将会返回带有边缘权重和源顶点的有向图形。

我正在使用networkx.generators.directed.gnc_graph（），但不能保证只返回一个源顶点。

有没有办法做到这一点，甚至没有networkx我注意到，生成的图总是只有一个sink顶点，它是第一个顶点。您可以反转所有边的方向，以获得具有单一源顶点的图。

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?

解决方案

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.

这篇关于如何在python中创建具有负边权重的随机单源随机无环有向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！