グラフとは点の辺で構築される一般的なデータ構造の一つです。
身近な例では友人ネットワークやWebページなどもグラフとして表現することができます。
現在、グラフを扱う場合PythonのNetworkxが非常に便利なツールとなっています。
書きやすく簡単なとても便利なライブラリです。
グラフを扱ってみようと思ったらまず試してみると良さそうです。
しかし、NetworkXには大規模なグラフに対して非常に処理が重くなってしまうという問題点があります。
そこで本記事では処理が高速であるC++を用い、NetworkXでグラフを構築するときのファイル形式のままC++でのグラフ構築の情報に用いる方法を紹介します。
前提知識としてC++の一通りの書き方は知っているものとします。
なおNetworkxについての記述がありますがNetworkXについて知らなくても問題はありません。
NetworkX形式のノード
NetworkXでは行ごとの各頂点のスペース区切りで頂点の出次点が書かれています。
※今回NetworkXのファイル形式にこだわりましたが、後述のsplit関数の区切り文字を変更すればcsv形式にも対応できます。
この記事を参考にエッジのリストは こちら の Facebook のグラフを使用します。
（リンク先のページ下部にある "facebook_combined.txt.gz" が該当ファイル）
ファイルはこのような形式になっています。
0 1
0 2
0 3
0 4
0 5
0 6
︙
(始点ノードid) (終点ノードid) という形式です。
このようなノード情報に対してNetworkXでは一瞬でできますがC++ではひと手間必要です。
実際の手順として
1. ファイルの読み込み
2. ストリングの分割
3. vectorへの代入
順に説明していきます。
ファイルの読み込み
string path = argv[1];
string num_nodes = stoi(argv[2]);
ifstream ifs(path);
vector<vector<int>> nodes;
nodes = vector<vector<int>>(num_nodes);
String の分割関数
vector<string> split(string& input, char delimiter){
istringstream stream(input);
string field;
vector<string> result;
while (getline(stream, field, delimiter)) {
result.push_back(field);
}
return result;
}
C++ でよくあるstringの分割関数です。
対象のstringと分割文字を引数にしてその分割文字でstringを分割しvectorを返します。
ファイルを一行ずつ読み込みsplitしたあとvectorに代入
string str;
int from, to;
while(getline(ifs, str)){
// スペース区切りで分割
vector<string> strvec = split(str, ' ');
from = stoi(strvec.at(0));
to = stoi(strvec.at(1));
nodes[from].push_back(to);
}
getline関数でファイルを一行ずつ読み込みsplit 関数を用いることでスペース区切りで分割された行を解釈します。
結果として返ってきた始点ノードid と終点ノードid の情報をvector に代入します。
こうしてノードの構造情報をvector に格納することができました。
確認
for(int i = 0; i < num_nodes; i++){
cout << i << "->";
for(int j = 0; j < nodes[i].size(); j++){
cout << nodes[i][j];
if(j != nodes[i].size()-1)cout << ",";
}
cout << endl;
}
結果
1->48,53,54,73,88,92,119,126,133,194,236,280,299,315,322,346
2->20,115,116,149,226,312,326,333,343
3->9,25,26,67,72,85,122,142,170,188,200,228,274,280,283,323
4->78,152,181,195,218,273,275,306,328
︙
このようにノードのエッジ情報を確認することができます。
ここまでするのでも大変ですね。