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を小さいほうに統一する。

// Place nodes u and v in same component of lower component ID
void Link(NodeID u, NodeID v, pvector<NodeID>& comp) {
  NodeID p1 = comp[u];
  NodeID p2 = comp[v];
  while (p1 != p2) {
    NodeID high = p1 > p2 ? p1 : p2;
    NodeID low = p1 + (p2 - high);
    NodeID p_high = comp[high];
    // Was already 'low' or succeeded in writing 'low'
    if ((p_high == low) ||
        (p_high == high && compare_and_swap(comp[high], high, low)))
      break;
    p1 = comp[comp[high]];
    p2 = comp[low];
  }
}

最後に、圧縮ステージで 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]];
    }
  }
}