Prufer sequence によるランダムツリー生成

Prüfer sequence - Wikipedia

Prufer sequence に関しては wikipedia を参照してください。python の networkx はランダム木生成に prufer sequence を使ってるらしい*1ので実装してみました。

Wikipedia に書いてある擬似コードをそのまま実装すると O(n^2) ですが、明らかに O(n log n) にできます。

std::vector<std::vector<int>> prufer_to_tree(std::vector<int> a) {
  const int n = a.size() + 2;
  std::vector<int> deg(n, 1);
  for (int x : a) {
    deg[x]++;
  }
  std::priority_queue<int> q;
  for (int i = 0; i < n; i++) {
    if (deg[i] == 1) {
      q.push(-i);
    }
  }

  std::vector<std::vector<int>> g(n);

  for (int x : a) {
    int y = -q.top();
    q.pop();
    g[x].push_back(y);
    g[y].push_back(x);

    deg[x]--;
    deg[y]--;
    if (deg[x] == 1) {
      q.push(-x);
    }
  }

  int x = std::find(deg.begin(), deg.end(), 1) - deg.begin();
  int y = std::find(deg.begin() + x + 1, deg.end(), 1) - deg.begin();
  g[x].push_back(y);
  g[y].push_back(x);

  return g;
}

std::vector<int> tree_to_prufer(std::vector<std::vector<int>> g) {
  const int n = g.size();
  std::vector<int> deg(n); 
  std::priority_queue<int> q;
  for (int i = 0; i < n; i++) {
    deg[i] = g[i].size();
    if (deg[i] == 1) {
      q.push(-i);
    }
  }

  std::vector<int> ret;
  while (!q.empty()) {
    int x = -q.top();
    q.pop();
    for (int y : g[x]) if (deg[y] >= 2) {
      deg[x]--;
      deg[y]--;
      ret.push_back(y);
      if (deg[y] == 1) {
        q.push(-y);
      }
    }
  }

  return ret;
}

random_tree2 は本当に簡単なランダム生成アルゴリズムですが、直径が小さくなりがちで、使い勝手が悪いです。Prufer sequence を用いた方法だとこれが改善されるのか実験してみました。

std::mt19937 mt(123456);

// Prufer
std::vector<std::vector<int>> random_tree(int n) {
  std::vector<int> a(n - 2);
  auto uid = std::uniform_int_distribution<int>(0, n - 1);
  for (int i = 0; i < n - 2; i++) {
    a[i] = uid(mt);
  }
  return prufer_to_tree(a);
}

// Stupid
std::vector<std::vector<int>> random_tree2(int n) {
  std::vector<std::vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    int j = std::uniform_int_distribution<int>(0, i - 1)(mt);
    g[i].push_back(j);
    g[j].push_back(i);
  }
  return g;
}

試行回数100000回です。


f:id:pekempey:20171205172429p:plain

直径の分布(n=100)



f:id:pekempey:20171205173151p:plain

直径の分布(n=1000)

n が大きくなると Stupid は使い物にならないですね。Prufer は割と普通です。n/log n くらい?(解析どうするんですかね…)

おまけ

ランダムツリー生成するコマンドラインツール。コンパイルg++ randtree.cpp -o randtree -std=c++11, 使う時は ./randtree 頂点数 シード。シードは省略すると std::random_device を使うようになっているが、環境によっては一定の値しか返さないので適当に書き換える。
https://gist.github.com/pekempey/6d63ddee071a1d82815736966b96a754