5

我想在大量图上对贝尔曼福特算法进行执行时间分析，为了做到这一点，我需要生成大量随机 DAGS，并且可能具有负边权重。

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

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

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

4

4 回答 4

10

您可以使用 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），这些也不太可能连接。

于 2012-11-24T23:38:35.503 回答
1

我注意到生成的图总是恰好有一个接收器顶点，它是第一个顶点。您可以反转所有边的方向以获得具有单个源顶点的图形。

于 2012-11-24T19:07:01.983 回答
1

@Aric 建议的方法将生成随机 DAG，但该方法不适用于大量节点，例如：n 趋于 100000。

        G = nx.gnp_random_graph(n, 0.5, directed=True)
        DAG = nx.DiGraph([(u, v,) for (u, v) in G.edges() if u < v])
        # print(nx.is_directed_acyclic_graph(DAG)) # to check if the graph is DAG (though it will be a DAG)
        A = nx.adjacency_matrix(DAG)
        AM = A.toarray().tolist()  # 1 for outgoing edges
        while(len(AM)!=n):
            AM = create_random_dag(n)

        # to display the DAG in matplotlib uncomment these 2 line
        # nx.draw(DAG,with_labels = True)
        # plt.show()

        return AM

对于大量节点，您可以使用每个下三角矩阵都是 DAG 的属性。因此生成随机下三角矩阵将生成随机 DAG。

        mat = [[0 for x in range(N)] for y in range(N)]
        for _ in range(N):
             for j in range(5):
                 v1 = random.randint(0,N-1)
                 v2 = random.randint(0,N-1)
                 if(v1 > v2):
                     mat[v1][v2] = 1
                 elif(v1 < v2):
                     mat[v2][v1] = 1

        for r in mat:
            print(','.join(map(str, r)))
于 2019-06-09T12:09:46.883 回答
0

对于 G -> DG -> DAG

具有 k 个输入和 m 个输出的 DAG

  1. 用你最喜欢的算法生成一个图（G=watts_strogatz_graph(10,2,0.4) ）
  2. 使图形为双向 ( DG = G.to_directed())
  3. 确保只有低索引的节点指向高索引
  4. 删除 k 个最低索引节点的输入边和 m 个最高索引节点的输出边（使 DG 变为 DAG）
  5. 确保每 k 个最低索引节点都有输出边，并且每 m 个最高索引节点都有输入边。
  6. 检查这个 DAG 中的每个节点，如果 k<index<nm，并且它只有没有输入边或输出边，随机选择 k 个最低索引节点中的一个节点链接到或选择 m 个最高索引节点中的一个节点链接到它，然后你会得到一个带有 k 个输入和 m 个输出的随机 DAG

喜欢：

 def g2dag(G: nx.Graph, k: int, m: int, seed=None) -> nx.DiGraph:
     if seed is not None:
         random.seed(seed)
     DG = G.to_directed()
     n = len(DG.nodes())
     assert n > k and n > m
     # Ensure only node with low index points to high index
     for e in list(DG.edges):
         if e[0] >= e[1]:
             DG.remove_edge(*e)
     # Remove k lowest index nodes' input edge. Randomly link a node if
     # they have not output edges.
     # And remove m highest index nodes' output edges. Randomly link a node if
     # they have not input edges.
     # ( that make DG to DAG)
     n_list = sorted(list(DG.nodes))
     for i in range(k):
         n_idx = n_list[i]
         for e in list(DG.in_edges(n_idx)):
             DG.remove_edge(*e)
         if len(DG.out_edges(n_idx)) == 0:
             DG.add_edge(n_idx, random.random_choice(n_list[k:]))
     for i in range(n-m, n):
         n_idx = n_list[i]
         for e in list(DG.out_edges(n_idx)):
             DG.remove_edge(*e)
         if len(DG.in_edges(n_idx)) == 0:
             DG.add_edge(random.random_choice(n_list[:n-m], n_idx))
     # If the k<index<n-m, and it only has no input edges or output edges,
     # randomly choose a node in k lowest index nodes to link to or
     # choose a node in m highest index nodes to link to it,
     for i in range(k, m-n):
         n_idx = n_list[i]
         if len(DG.in_edges(n_idx)) == 0:
             DG.add_edge(random.random_choice(n_list[:k], n_idx))
         if len(DG.out_edges(n_idx)) == 0:
             DG.add_edge(n_idx, random.random_choice(n_list[n-m:]))

     # then you get a random DAG with k inputs and m outputs
     return DG
于 2020-07-02T09:46:41.097 回答