c++ - ランダム DAG の生成

Question

有向非巡回グラフの問題を解決しています。

しかし、いくつかの有向非巡回グラフでコードをテストするのに問題があります。テストグラフは大きく、(明らかに) 非周期的である必要があります。

非循環有向グラフを生成するためのコードを書くために多くのことを試みました。でも毎回失敗しました。

使用できる非循環有向グラフを生成する既存の方法はありますか?

score 59 · Accepted Answer

これを行う C プログラムを作成しました。重要なのは、ノードを「ランク付け」し、ランクの低いノードからランクの高いノードへのエッジのみを描画することです。

私が書いたプログラムは、DOT 言語で出力されます。

これがコード自体で、その意味を説明するコメントが付いています。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MIN_PER_RANK 1 /* Nodes/Rank: How 'fat' the DAG should be.  */
#define MAX_PER_RANK 5
#define MIN_RANKS 3    /* Ranks: How 'tall' the DAG should be.  */
#define MAX_RANKS 5
#define PERCENT 30     /* Chance of having an Edge.  */

int main (void)
{
  int i, j, k,nodes = 0;
  srand (time (NULL));

  int ranks = MIN_RANKS
              + (rand () % (MAX_RANKS - MIN_RANKS + 1));

  printf ("digraph {\n");
  for (i = 0; i < ranks; i++)
    {
      /* New nodes of 'higher' rank than all nodes generated till now.  */
      int new_nodes = MIN_PER_RANK
                      + (rand () % (MAX_PER_RANK - MIN_PER_RANK + 1));

      /* Edges from old nodes ('nodes') to new ones ('new_nodes').  */
      for (j = 0; j < nodes; j++)
        for (k = 0; k < new_nodes; k++)
          if ( (rand () % 100) < PERCENT)
            printf ("  %d -> %d;\n", j, k + nodes); /* An Edge.  */

      nodes += new_nodes; /* Accumulate into old node set.  */
    }
  printf ("}\n");
  return 0;
}

テスト実行から生成されたグラフは次のとおりです。

ランダムに生成された DAG

score 21 · Accepted Answer

https://mathematica.stackexchange.com/questions/608/how-to-generate-random-directed-acyclic-graphsへの回答が適用されます。グラフのエッジの隣接行列表現がある場合は、行列が下三角で、必然的にDAGです。

同様のアプローチは、ノードの任意の順序を取り、 x<yの場合にのみノードxからyへのエッジを考慮することです。その制約は、構造によってDAGnessも取得する必要があります。構造体を使用してノードを表す場合、メモリ比較はノードを順序付ける任意の方法の1つです。

基本的に、擬似コードは次のようになります。

for(i = 0; i < N; i++) {
    for (j = i+1; j < N; j++) {
        maybePutAnEdgeBetween(i, j);
    }
}

ここで、Nはグラフ内のノードの数です。

擬似コードは、Nノードが与えられた場合の潜在的なDAGの数が

2^(n*(n-1)/2),

あるので

n*(n-1)/2

順序対（「Nは2を選択」）であり、それらの間にエッジがあるかどうかを選択できます。

score 4 · Accepted Answer

したがって、これらすべての合理的な答えをまとめると、次のようになります。

(以下では、生成されたグラフの頂点の数に V を使用し、エッジの数に E を使用し、E ≤ V(V-1)/2 と仮定します。)

個人的には、最も有用な答えは、http://condor.depaul.edu/rjohnson/source/graph_ge.cのコードを指し示す Flavius によるコメントにあると思います。そのコードは非常にシンプルで、コメントで簡単に説明されています。これを再現します。

To generate a directed acyclic graph, we first
generate a random permutation dag[0],...,dag[v-1].
(v = number of vertices.)
This random permutation serves as a topological
sort of the graph. We then generate random edges of the
form (dag[i],dag[j]) with i < j.

実際、コードが行うことは、以下を繰り返し実行することによって、要求された数のエッジを生成することです。

[0, V) の範囲で 2 つの数値を生成します。
等しい場合は拒否します。
最初の方が大きい場合はそれらを交換します。
以前に生成したことがある場合は拒否します。

このソリューションの問題は、E がエッジの最大数 V(V-1)/2 に近づくにつれて、ますます多くのエッジを拒否する必要があるため、アルゴリズムがますます遅くなることです。より良い解決策は、すべての V(V-1)/2 可能なエッジのベクトルを作成することです。ランダムにシャッフルします。シャッフルされたリストで最初の (要求されたエッジ) エッジを選択します。

kの値からk^番目のエッジの端点を推定できるため、リザーバーサンプリングアルゴリズムを使用すると、空間 O(E) でこれを行うことができます。したがって、実際にソースベクトルを作成する必要はありません。ただし、それでも O(V ² ) の時間が必要です。

あるいは、Fisher-Yatesシャッフル (または、必要に応じて Knuth シャッフル) を実行して、E 回の反復後に停止することもできます。ウィキペディアで提示されているバージョンの FY シャッフルでは、これにより末尾のエントリが生成されますが、アルゴリズムは逆方向でも同様に機能します。

// At the end of this snippet, a consists of a random sample of the
// integers in the half-open range [0, V(V-1)/2). (They still need to be
// converted to pairs of endpoints).
vector<int> a;
int N = V * (V - 1) / 2;
for (int i = 0; i < N; ++i) a.push_back(i);
for (int i = 0; i < E; ++i) {
  int j = i + rand(N - i);
  swap(a[i], a[j]);
a.resize(E);

これには O(E) 時間しか必要ありませんが、O(N ² ) スペースが必要です。実際、これはいくつかのトリックで O(E) 空間に改善できますが、SO コードスニペットは小さすぎて結果を含めることができないため、O(E) 空間と O(E log E ）時間。少なくとも次のクラス DAG があると仮定します。

class DAG {
  // Construct an empty DAG with v vertices
  explicit DAG(int v);

  // Add the directed edge i->j, where 0 <= i, j < v
  void add(int i, int j);
};

ここに行きます：

// Return a randomly-constructed DAG with V vertices and and E edges.
// It's required that 0 < E < V(V-1)/2.
template<typename PRNG>
DAG RandomDAG(int V, int E, PRNG& prng) {
  using dist = std::uniform_int_distribution<int>;
  // Make a random sample of size E
  std::vector<int> sample;
  sample.reserve(E);
  int N = V * (V - 1) / 2;
  dist d(0, N - E);  // uniform_int_distribution is closed range
  // Random vector of integers in [0, N-E]
  for (int i = 0; i < E; ++i) sample.push_back(dist(prng));
  // Sort them, and make them unique
  std::sort(sample.begin(), sample.end());
  for (int i = 1; i < E; ++i) sample[i] += i;
  // Now it's a unique sorted list of integers in [0, N-E+E-1]
  // Randomly shuffle the endpoints, so the topological sort
  // is different, too.
  std::vector<int> endpoints;
  endpoints.reserve(V);
  for (i = 0; i < V; ++i) endpoints.push_back(i);
  std::shuffle(endpoints.begin(), endpoints.end(), prng);
  // Finally, create the dag
  DAG rv;
  for (auto& v : sample) {
    int tail = int(0.5 + sqrt((v + 1) * 2));
    int head = v - tail * (tail - 1) / 2;
    rv.add(head, tail);
  }
  return rv;
}

score 3 · Accepted Answer

ランダムな有向グラフを生成してから、深さ優先探索を実行してサイクルを検索できます。サイクルを見つけたら、エッジを削除してサイクルを中断します。

これは最悪の場合のO（VE）だと思います。各DFSはO（V）を取り、各DFSは少なくとも1つのエッジを削除します（つまり最大E）

すべてのV^2の可能なエッジを均一にランダムに選択して有向グラフを生成し、ランダムな順序でDFSを実行し、ランダムなエッジを削除すると、すべての可能なダグにわたって均一な分布（または少なくともそれに近い）が得られます。

score 1 · Accepted Answer

nノードと、ノードの各ペアn1とn2ifn1 != n2およびの間にエッジがあるグラフを作成しますn2 % n1 == 0。

score 1 · Accepted Answer

最近、受け入れられた回答を再実装しようとしましたが、それが不確定であることがわかりました。min_per_rank パラメーターを強制しないと、ノードが 0 のグラフになる可能性があります。

これを防ぐために、for ループを関数でラップし、ランクごとにそれmin_per_rankが満たされていることを確認しました。JavaScript の実装は次のとおりです。

https://github.com/karissa/random-dag

そして、受け入れられた回答のメインループを置き換える疑似Cコード。

int pushed = 0

int addRank (void) 
{
  for (j = 0; j < nodes; j++)
    for (k = 0; k < new_nodes; k++)
      if ( (rand () % 100) < PERCENT)
        printf ("  %d -> %d;\n", j, k + nodes); /* An Edge.  */

  if (pushed < min_per_rank) return addRank()
  else pushed = 0

  return 0
}

c++ - ランダム DAG の生成

9 に答える 9

Related

Reference