GAP Benchmarkの各プログラムの構成について (cc.cc)

GAP Benchmarkの各プログラムの中身を調べている。cc.ccについて調べた。

CC (Connected Components) : 連結成分

連結成分は、グラフの中でつながっているグループをまとめ上げる作業。 連結しているノードをグループ化し、最終的に連結していないグループでまとめる。

これを実現するためには、単純に考えるとBFSやDFSでノードを追っていけばよい。 ただし、ここは並列アルゴリズムが前提となり、GAPではAfforestというアルゴリズムを実装しているようだ。

Afforestというアルゴリズムがなんだかわからなかったので、ChatGPTに聞いてみた。

1. 初期化ステージ：各ノードをその成分としてマークする。つまり、最初は各ノードそれ自体が1つのグループであるとする。
2. フック・ステージ：ノードのエッジをたどっていき、エッジで結ばれるノードの一方が他のノードと同一のグループになるようにフックしていく。これにより、エッジでつながっているノードはグループ化されていく。
3. 圧縮ステージ：ノード番号とグループ番号を再調整して、各ノードが自分のグループを直接示すようにする。

この、フック・ステージと圧縮ステージが何で別々なのかはわからないが、おそらく並列実行するためにステージを分けているのではと思っている。

まず、それぞれのノードが単一のグループであると設定する。

for (NodeID n = 0; n < g.num_nodes(); n++)
  comp[n] = n;

次に、隣接するノードを探索して、各ノードをリンクする。これがフッキングステージに相当する。

  // Process a sparse sampled subgraph first for approximating components.
  // Sample by processing a fixed number of neighbors for each node (see paper)
  for (int r = 0; r < neighbor_rounds; ++r) {
  #pragma omp parallel for schedule(dynamic,16384)
    for (NodeID u = 0; u < g.num_nodes(); u++) {
      for (NodeID v : g.out_neigh(u, r)) {
        // Link at most one time if neighbor available at offset r
        Link(u, v, comp);
        break;
      }
    }
    Compress(g, comp);
  }

Link()の実装は以下だ。ノードuとノードvを同じグループに設定し、そのグループIDを小さいほうに統一する。

最後に、圧縮ステージでCompress()を動かす。これは、どうも同じグループのグループIDが複数個存在してしまった場合、同じグループのIDを統一する（つまり、すべてのノードが同じグループIDを共有することになる）。これは、以降のグループ化処理を高速化する意図も含んでいる。

// Reduce depth of tree for each component to 1 by crawling up parents
void Compress(const Graph &g, pvector<NodeID>& comp) {
  #pragma omp parallel for schedule(dynamic, 16384)
  for (NodeID n = 0; n < g.num_nodes(); n++) {
    while (comp[n] != comp[comp[n]]) {
      comp[n] = comp[comp[n]];
    }
  }
}