GAP Benchmarkのグラフ変換用ツールconverterについて解析

GAP Benchmarkのグラフを変換するツールconverterが何をしているのかちょっと見ておく。

./converter -f benchmark/graphs/raw/twitter.el -b benchmark/graphs/twitter.sg
./converter -f benchmark/graphs/raw/sk-2005/sk-2005.mtx -b benchmark/graphs/web.sg
./converter -f benchmark/graphs/raw/USA-road-d.USA.gr -b benchmark/graphs/road.sg
./converter -g27 -k16 -b benchmark/graphs/kron.sg
./converter -u27 -k16 -b benchmark/graphs/urand.sg
./converter -f benchmark/graphs/raw/twitter.el -wb benchmark/graphs/twitter.wsg
./converter -f benchmark/graphs/raw/sk-2005/sk-2005.mtx -wb benchmark/graphs/web.wsg
./converter -f benchmark/graphs/raw/USA-road-d.USA.gr -wb benchmark/graphs/road.wsg
./converter -g27 -k16 -wb benchmark/graphs/kron.wsg
./converter -u27 -k16 -wb benchmark/graphs/urand.wsg
./converter -sf benchmark/graphs/raw/twitter.el -b benchmark/graphs/twitterU.sg
./converter -sf benchmark/graphs/raw/sk-2005/sk-2005.mtx -b benchmark/graphs/webU.sg
./converter -sf benchmark/graphs/raw/USA-road-d.USA.gr -b benchmark/graphs/roadU.sg

./converter -help
converter
 -h          : print this help message                                         
 -f <file>   : load graph from file                                            
 -s          : symmetrize input edge list                               [false]
 -g <scale>  : generate 2^scale kronecker graph                                
 -u <scale>  : generate 2^scale uniform-random graph                           
 -k <degree> : average degree for synthetic graph                          [16]
 -m          : reduces memory usage during graph building               [false]
 -b <file>   : output serialized graph to file                                 
 -e <file>   : output edge list to file                                        
 -w <file>   : make output weighted

• -fから-bへの変換は、単なるテキストのノードペアが記載されているテキストファイルを、バイナリ形式に変換している。.sgはserialized graphの略だと思われる。 おそらく出力はこのあたり。バイナリで書き出している。

    out.write(reinterpret_cast<char*>(&directed), sizeof(bool));
    out.write(reinterpret_cast<char*>(&edges_to_write), sizeof(SGOffset));
    out.write(reinterpret_cast<char*>(&num_nodes), sizeof(SGOffset));
    pvector<SGOffset> offsets = g_.VertexOffsets(false);
    out.write(reinterpret_cast<char*>(offsets.data()), index_bytes);
    out.write(reinterpret_cast<char*>(g_.out_neigh(0).begin()), neigh_bytes);
    if (directed) {
      offsets = g_.VertexOffsets(true);
      out.write(reinterpret_cast<char*>(offsets.data()), index_bytes);
      out.write(reinterpret_cast<char*>(g_.in_neigh(0).begin()), neigh_bytes);
    }

• -gと-uは、それぞれkroneckerとuniform-randomグラフを自動生成している。
• 出力オプションが-wbになる重み付きグラフを生成するらしい。.wsgはweighted serialized graphの略称。
• 入力オプションに-sが付くと、symmetrize input edge listと書いているが、これは対称グラフにするという意味だと思う。