これを理解するのに数時間を要したよ orz
推移閉包を求める。
下半分は、無限ループ回避。←違った。もっかい読む
下半分は、グラフがループしている場合にそのループ内のノードは同じ bitset を持つことになるので、ループ内の全ノードに bitset をコピーしている。
static relation R; static relation_nodes INDEX; static relation_nodes VERTICES; static relation_node top; static relation_node infinity; static bitsetv F; static void traverse (relation_node i) { relation_node j; relation_node height; VERTICES[++top] = i; INDEX[i] = height = top; if (R[i]) for (j = 0; R[i][j] != END_NODE; ++j) { if (INDEX[R[i][j]] == 0) traverse (R[i][j]); if (INDEX[i] > INDEX[R[i][j]]) INDEX[i] = INDEX[R[i][j]]; bitset_or (F[i], F[i], F[R[i][j]]); } if (INDEX[i] == height) for (;;) { j = VERTICES[top--]; INDEX[j] = infinity; if (i == j) break; bitset_copy (F[j], F[i]); } }http://google.com/codesearch?hl=en&q=+bison-2.3/src/relation.c+show:fFa-8tgHjbU:SxNuVTmdWBo:gXWMzbhBK00&sa=N&cd=1&ct=rc&cs_p=ftp://ftp.gnu.org/gnu/bison/bison-2.3.tar.bz2&cs_f=bison-2.3/src/relation.c