トポロジカルソートと強連結成分分解でWikipediaの特定カテゴリー配下のページをすべて取得する - 終末 A.I.

Wikipediaの特定カテゴリー配下のページをすべて取得するためには、整理されていないグラフデータ特有のいくつかの問題に向き合う必要があります。 一つは、Category:カツラ科と糸井の大カツラのように、サブカテゴリーにはページへのリンクが含まれているが、カテゴリー本体にはページへのリンクが含まれていないケースがあるという問題。 もう一つは、Category:インフォグラム・エンターテインメントームソフトとCategory:アタリのゲームソフトのように、お互いがお互いのサブカテゴリーに含まれてしまっているケースがあるという問題です。 これらの問題は、以下の手順を踏むことで解決できます。 カテゴリーにリンクされているページだけでなく、サブカテゴリー内のリンクを順にたどって含まれるすべてのページを収集する ただし、一度たどったカテゴリーに再度到達した場合、それ以上はそのルートを探索しない

[synopses]

ここの日本語が良くわからんかった>お気持ちだけ簡単に説明すると

[pmint]

"同じマークのついた"…マークは1種類でなさそうだけど「何に基づいてマークを変えるのか」が分からない。

[ultimatebreak]

トポロジカルってなんか美味しそうだよね

[yumura_s]

トポロジカルソートは必要なのか？強連結成分分解で凝縮グラフ作って推移簡約で親子関係決めるとかではなくて？？（transitive reduction of the condensation of G）

[rrringress]

カツラ科について、wikipediaでそんな事が起こっていたなんて

[rgfx]

グラフデータ構造を処理するお話だ。

[takuya-a]

なるほどー、アルゴリズム的にも面白いし、Wikipedia使ったデータ処理するときに役立ちそう