Stanford GraphBase .gb形式

Question

スタンフォードGraphBase CWEBライブラリで使用するために私自身のグラフを入力したいと思います。私はSGBのウェブページでthisのグラフの例を見つけて、大部分を理解しています。私が理解できないのは、頂点リストに4つのゼロ行（ ""、0 \ n）があり、エッジリストに非常に多くのゼロ行（0,0,0）があることです。グラフは、それらがなければ正常にコンパイルされているように見えますが、その目的はわかりません。

Answer 1

余分なゼロラインは厳密に必要ではありません。グラフがロードされると、後でグラフに追加される可能性のある頂点や円弧（たとえば、グラフ上で実行されるアルゴリズムによっては）にメモリが事前に割り当てられます。これは、新しい頂点とエッジに動的にメモリを割り当てる代わりの方法です。そのリンク内のグラフは、グラフ上の余分なノードとアークのためのスペースを必要とするアルゴリズムと一緒に使用されることになっています。