Yükseltme Grafik Kitaplığı: Büyük grafikler için kenar ekleme yavaş çalışıyor

Question

Etkileşimli görüntü bölümlemesi için bir "akıllı makas" kullanmaya çalışıyorum. Bu nedenle, her köşe noktasının tek bir pikseli temsil ettiği bir görüntüden yönlendirilmiş bir grafik oluşturmak zorundayım. Her köşe daha sonra komşularının her birine iki kenardan girer: bir giden ve bir gelen kenar. Bunun nedeni, bir kenarın (a, b) maliyetinin (b, a) maliyetinden farklı olabilmesidir. 512 * 512 piksel boyutunda görüntüler kullanıyorum, böylece 262144 köşesi ve 2091012 kenarları ile bir grafik oluşturmam gerekiyor.

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; 

I Grafik (yavan adlandırma müteessir), ek bir sınıfı kullanıyorum grafik işleme: Şu anda, aşağıdaki grafik kullanıyorum

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 köşesiyle yeni bir grafik oluşturmak oldukça hızlıdır, ancak kenarların yerleştirilmesi 10 saniyeye kadar çıkar ve bu da istenen uygulama için çok yavaştır. Ben programm hızını artırmak do yapabileceğim bir şey

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 
    } 
} 

var mı: Şu anda, aşağıdaki yolu kenarları takacağım? Microsoft Visual C++ 2010 Express'i optimizasyon ile (Boost tarafından tavsiye edildiği şekilde) serbest bırakma modunda kullanıyorum. Köşeler veya kenarlar için listS kapsayıcıyı kullanabileceğimi düşündüm ama köşeler sorun değil ve kenarlar için listeS kullanırsanız, daha da yavaşlar.

Answer 1

adjacency_list çok genel amaçlı; Maalesef, özel kullanım durumunuzun düzenliliğini kullanarak bir çözüm kadar verimli olmayacak. BGL sihir değil. Bu değil açıkça tüm bu düğümü tahsis edecek olan, bir görüntünün komşu piksel grafik için:

Yapabileceğiniz en iyi şey BGL (ipucu yokluğunda kullanırım verimli grafik gösterimi ile gelip muhtemelen ve kenar nesneleri) ve daha sonra BGL'yi (example) veya eşdeğer bir şekilde doğrudan sisteminizin düzenlilikleri için ayarlanmış mevcut adjacency_list/adjacency_matrix şablonlarına (concept guidelines) uygulayın.

En iyi duruma getirilmiş bir gösterimle, tabii ki, tüm düğümleri ve kenarları gerçekte sakladığınız, ancak görüntünün ortaya çıkmasından kaynaklanan örtük düğümlerin ve kenarların numaralandırmalarını yinelemenin bir yolu vardır. belirli bir boyuttur. Gerçekten depolamanız gereken tek şey kenar ağırlıklarının bir dizisidir.