Graph Format。

いまさらではあるが、最短経路問題に用いているグラフフォーマットは、DIMACS 9th から Download したものである。他のフォーマットにも対応することもできるが、用意されているデータを用いて実験を行っている。全米データが無料で公開されているというのはとてもありがたいことである。

まずは、DIMACS フォーマットから紹介する。このフォーマットは、以下のようにして TIGER/Line から変換されて作られている。
・点番号　：　１ ～ "number of nodes"（TIGER/Line は、０ ～ "number of nodes"-1 で１つずつずらしている）
・枝長　　：　小数点以下を切り落とし。（最小枝長は１）

グラフデータは USA-road-x.XXX.gr というファイル名で、 以下のようなフォーマットである。
距離グラフと、移動時間グラフが用意されている。

c comment
p sp "number of nodes" "number of arcs"
a "src id" "dest id" "weight"
　　　　：


また、座標データは USA-road-d.XXX.co というファイル名で、以下のようなフォーマットである。
c comment
p aux sp co "number of nodes"
a "id" "longitude" "latitude"
　　　　：


また、DIMACS フォーマットの元になった TIGER/Line のフォーマットも紹介しておく。先ほども説明したが、TIGER/Lineでは、点番号が ０ ～ "number of nodes"-1 であり、また距離・移動時間も小数で表示されている。

またカテゴリーというものもあり 41, 42, 43, 44（実際には A1, A2, A3, A4 らしいが）、道路の分類もされている。

"number of nodes"
"id" "longitude" "latitude"
　　　　：
　　　　：
"id" "longitude" "latitude"
"number of arcs"
"src id" "dest id"
"time" "length" "category"
　　　　：
　　　　：
"src id" "dest id"
"time" "length" "category"