如何在python中创建具有负边权重的随机单源随机无环有向图

Question

我想在大量图上对 bellman Ford 算法进行执行时间分析，为此我需要生成大量随机 DAGS，并且可能具有负边权重。

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

我正在使用 networkx.generators.directed.gnc_graph() 但这并不能完全保证只返回一个源顶点。

有没有办法在有甚至没有networkx的情况下做到这一点？

Answer 1

您可以使用 gnp_random_graph() 生成器生成随机 DAG，并且只保留从较低索引指向较高索引的边。例如

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

这些可以有多个来源，但您可以通过@Christopher 的建议来解决这个问题，即制作一个指向所有来源的“超级来源”。

对于小的连接概率值（上面的 p=0.5），它们也不太可能连接。

Answer 2

我注意到生成的图始终具有一个接收顶点，即第一个顶点。您可以反转所有边的方向以获得具有单个源顶点的图。