Thư viện biểu đồ tăng cường: chèn cạnh chậm cho biểu đồ lớn

Question

Tôi đang cố gắng sử dụng triển khai "hình cắt kéo thông minh" cho phân đoạn hình ảnh tương tác. Do đó, tôi phải tạo một đồ thị có hướng từ một hình ảnh mà mỗi đỉnh đại diện cho một điểm ảnh duy nhất. Mỗi đỉnh sau đó được conntected đến mỗi người hàng xóm của nó bằng hai cạnh: một đi và một cạnh đến. Điều này là do thực tế rằng chi phí của một cạnh (a, b) có thể khác với chi phí của (b, a). Tôi đang sử dụng hình ảnh có kích thước 512 * 512 pixel vì vậy tôi cần tạo một biểu đồ có 262144 đỉnh và cạnh 2091012. Hiện nay, tôi đang sử dụng đồ thị sau:

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; 

Tôi đang sử dụng một lớp thêm Graph (xin lỗi cho việc đặt tên tẻ nhạt) mà xử lý đồ thị:

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(); 

};

Tạo biểu đồ mới với 262144 đỉnh là khá nhanh nhưng việc chèn các cạnh mất tới 10 giây, điều đó quá chậm đối với ứng dụng mong muốn. Ngay bây giờ, tôi đang chèn các cạnh theo cách sau:

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

Tôi có thể làm gì để cải thiện tốc độ của chương trình không? Tôi đang sử dụng Microsoft Visual C++ 2010 Express trong chế độ phát hành với tối ưu hóa (theo khuyến cáo của Boost). Tôi nghĩ rằng tôi có thể sử dụng một danh sách danh mục cho các đỉnh hoặc cạnh nhưng các đỉnh không có vấn đề gì và nếu tôi sử dụng listS cho các cạnh, nó thậm chí còn chậm hơn.

Answer 1

adjacency_list là mục đích rất chung chung; tiếc là nó sẽ không bao giờ hiệu quả như một giải pháp khai thác tính đồng đều của trường hợp sử dụng cụ thể của bạn. BGL không phải là ma thuật. Đặt cược tốt nhất của bạn có thể là đưa ra biểu diễn biểu đồ hiệu quả mà bạn sử dụng khi thiếu BGL (gợi ý: đối với biểu đồ pixel lân cận của hình ảnh, đây là không phải sẽ phân bổ rõ ràng tất cả các nút đó và các đối tượng cạnh) và sau đó vừa với BGL (example) hoặc tương đương trực tiếp triển khai đối tác với các mẫu adjacency_list/adjacency_matrix hiện tại (concept guidelines) được điều chỉnh theo quy luật của hệ thống. Với một đại diện được tối ưu hóa, tất nhiên tôi có nghĩa là bạn không thực sự lưu trữ tất cả các nút và cạnh một cách rõ ràng nhưng chỉ có một số cách lặp qua các liệt kê các nút và các cạnh ngầm phát sinh từ thực tế là hình ảnh là một kích thước cụ thể. Điều duy nhất bạn nên thực sự cần lưu trữ là một mảng các trọng số cạnh.