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

生成されたグラフには、最初の頂点であるシンク頂点が常に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 に答える