performance - Boost 图形库 : edge insertion slow for large graph

Question

我正在尝试使用“智能剪刀”进行交互式图像分割。因此，我必须从图像中创建一个有向图，其中每个顶点代表一个像素。然后每个顶点通过两条边连接到它的每个邻居:一条出边和一条入边。这是因为边 (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;

我正在使用一个额外的类 Graph (抱歉没有启发性的命名)来处理图形:

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

我可以做些什么来 boost 程序的速度？我在 Release模式下使用 Microsoft Visual C++ 2010 Express 进行优化(如 Boost 推荐的那样)。我以为我可以对顶点或边使用 listS 容器，但顶点没有问题，如果我对边使用 listS，它会变得更慢。

Answer 1

adjacency_list 非常通用；不幸的是，它永远不会像利用您的特定用例的规律性的解决方案那样有效。 BGL 不是魔法。

最好的办法可能是想出在没有 BGL 的情况下使用的有效图形表示(提示:对于图像相邻像素的图形，这不会显式分配所有这些节点和边缘对象)，然后将 BGL 适配到它( example )，或者等效地直接实现现有 adjacency_list 的对应物/adjacency_matrix模板 ( concept guidelines ) 调整到您系统的规律。

通过优化表示，我当然是指您实际上并不显式存储所有节点和边，而只是有某种方式迭代隐式节点和边的枚举，因为图像是特定大小的事实.您真正需要存储的唯一内容是边权重数组。