透過 PNG。

最短路問題を解く度に「全枝」を出力するのはとても非効率であるので、PNG, GIF フォーマットの機能である「透過」を利用することにした。「全枝を出力した画像」と「最短経路のみを出力した画像」を重ね合わせるという方法である。NY では図のようになる。

方法としては、以下のとおりである。

[準備-1] 全枝を出力した EPS ファイル (XXX_arc.eps) を作成する

[input] USA-road-d.XXX.gr, USA-road-d.XXX.co または XXX.tmp(TIGER/Line)
[output] XXX_arc.eps


[準備-2] 全枝を出力した EPS ファイルを PNG ファイル (XXX_arc.png) に変換する
convert XXX_arc.eps XXX_arc.png



ここまでの処理は最初に１回行っておけばよい。
あとは png ファイルを使いまわす。



[1] 最短路に使用した枝のみを出力した EPS ファイル (USA_path.eps) を作成する
[input1] USA-road-d.XXX.gr, USA-road-d.XXX.co または XXX.tmp(TIGER/Line)
[input2] src_id dist_id
[output] XXX_path.eps

[2] 出力した EPS ファイルを PNG ファイル (XXX_path.png) に変換する
convert -transparent white XXX_path.eps XXX_path.png

[3] 全枝を出力した PNG ファイルと、最短路のみを出力したものを重ねる
convert -composite XXX_arc.eps XXX_path.png XXX.png



と言う流れで、XXX.png が完成する。
最短路のみの EPS はとても軽いために、eps-png の convert にもあまり時間がかからなかった。（全米で 2.8[sec]）
あとは、グラフデータの読み込み時間を考慮しなければならないだろう。（全米で 51[sec]）