ブーストグラフライブラリ：大きなグラフのエッジ挿入が遅い

Question

インタラクティブな画像セグメンテーションに「インテリジェントシザー」を実装しようとしています。したがって、各頂点が1つのピクセルを表す画像から有向グラフを作成する必要があります。次に、各頂点は、2つのエッジ、すなわち1つの出力エッジと1つの入力エッジによって、その近隣ノードのそれぞれに連結される。これは、エッジ（a、b）のコストが（b、a）のコストと異なる可能性があるためです。私は512×512ピクセルのサイズの画像を使用しているので、262144の頂点と2091012のエッジを持つグラフを作成する必要があります。

typedef property<vertex_index_t, int, 
     property<vertex_distance_t, double, 
     property<x_t, int, 
     property<y_t, int 
     >>>> VertexProperty; 

typedef property<edge_weight_t, double> EdgeProperty; 

// define MyGraph 
typedef adjacency_list<  
    vecS,   // container used for the out-edges (list) 
    vecS,   // container used for the vertices (vector) 
    directedS,  // directed edges (not sure if this is the right choice for incidenceGraph) 
    VertexProperty, 
    EdgeProperty 
    > MyGraph; 

私はグラフ（平凡な命名のため申し訳ありません）追加のクラスを使用していグラフ処理します：現在、私は次のグラフ使ってい

class Graph 
{ 
private: 
    MyGraph *graph; 
    property_map<MyGraph, vertex_index_t>::type indexmap; 
    property_map<MyGraph, vertex_distance_t>::type distancemap; 
    property_map<MyGraph, edge_weight_t>::type weightmap; 
    property_map<MyGraph, x_t>::type xmap; 
    property_map<MyGraph, y_t>::type ymap; 
    std::vector<MyGraph::vertex_descriptor> predecessors; 
public: 
    Graph(); 
    ~Graph(); 

を};

頂点が262144の新しいグラフを作成するのはかなり速いですが、エッジの挿入には最大10秒かかってしまいます。今、私は次のようにエッジを挿入しています：

tie(vertexIt, vertexEnd) = vertices(*graph); 
for(; vertexIt != vertexEnd; vertexIt++){ 
    vertexID = *vertexIt; 
    x = vertexID % 512; 
    y = (vertexID - x)/512; 
    xmap[vertexID] = x; 
    ymap[vertexID] = y; 
    if(y > 0){ 
     if(x > 0){ 
      tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y-1)+(x-1)], *graph); // upper left neighbour 
     } 
     tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y-1)+(x)], *graph); // upper 
     if(x < 511){ 
      tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y-1)+(x+1)], *graph); // upper right 
     } 
    } 
    if(x < 511){  
     tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y)+(x+1)], *graph); // right 
    } 
    if(y < 511){ 
     if(x > 0){ 
      tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y+1)+(x-1)], *graph); // lower left 
     } 
     tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y+1)+(x)], *graph); // lower 
     if(x < 511){ 
      tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y+1)+(x+1)], *graph); // lower right 
     } 
    } 
    if(x > 0){ 
     tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y)+(x-1)], *graph); // left 
    } 
} 

私はプログラムの速度を向上させるために何かできますか？私はMicrosoft Visual C++ 2010 Expressをリリースモードで最適化を使用しています（Boostが推奨するように）。私はlistSコンテナを頂点やエッジに使うことができると思ったが、頂点に問題はなく、リストSをエッジに使用すると、それはさらに遅くなる。

Answer 1

adjacency_listは非常に一般的な目的です。残念ながら、特定のユースケースの規則性を利用するソリューションほど効率的ではありません。 BGLは魔法ではありません。

あなたの最善の策は、あなたがBGLの不存在下で使用したい効率的なグラフ表現（ヒントを思い付くことはおそらくです：画像の隣接する画素のグラフのために、これはが明示的にこれらすべてのノードを割り当てることするつもりはありません（example）、または同等の方法で、システムの規則性に合わせて既存のadjacency_list/adjacency_matrixテンプレート（concept guidelines）に対応するものを直接実装するだけです。

最適化された表現では、もちろん、実際にはすべてのノードとエッジを明示的に保存するのではなく、暗黙的なノードとエッジの列挙を反復する何らかの方法があります特定のサイズです。実際に格納する必要があるのは、エッジウェイトの配列だけです。