Boost Graph Library: медленная вставка ребер для большого графика - PullRequest
Новая
       95

Boost Graph Library: медленная вставка ребер для большого графика

7 голосов
/ 25 октября 2011

Я пытаюсь использовать «интеллектуальные ножницы» для интерактивной сегментации изображений. Поэтому мне нужно создать ориентированный граф из изображения, где каждая вершина представляет один пиксель. Каждая вершина затем соединяется с каждым из своих соседей двумя ребрами: одним исходящим и одним входящим ребром. Это связано с тем, что стоимость ребра (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 контейнер для вершин или ребер, но с вершинами проблем нет, и если я использую listS для ребер, он станет еще медленнее.

1 Ответ

6 голосов
/ 26 октября 2011

adjacency_list очень общего назначения;к сожалению, оно никогда не будет таким эффективным, как решение, использующее регулярность вашего конкретного варианта использования.BGL не волшебство.

Вероятно, вам лучше всего придумать эффективное представление графика, которое вы бы использовали в отсутствие BGL (подсказка: для графика соседних пикселей изображения это не собирается явно выделять все эти узлы и граничные объекты), а затем подгонять к нему BGL ( пример ) или эквивалентно просто напрямую реализовывать аналог существующих шаблонов adjacency_list / adjacency_matrix( Руководство по концепции ), настроенное на закономерности вашей системы.

Под оптимизированным представлением я, конечно, подразумеваю тот, в котором вы на самом деле сохраняете не все узлы и ребра явно, а простоиметь некоторый способ перебирать перечисления неявных узлов и ребер, вытекающие из того факта, что изображение имеет определенный размер.Единственное, что вам действительно нужно хранить, это массив весов ребер.

...