performance - Boost Graph Library: inserción de bordes lenta para gráficos grandes

boost-graph edges

Question

Estoy tratando de usar implementar una "tijera inteligente" para una segmentación de imagen interactiva. Por lo tanto, tengo que crear un gráfico dirigido desde una imagen donde cada vértice representa un solo píxel. Cada vértice se conecta a cada uno de sus vecinos por dos bordes: uno de salida y otro de entrada. Esto se debe al hecho de que el costo de un borde (a, b) puede diferir del costo de (b, a). Estoy usando imágenes con un tamaño de 512 * 512 píxeles, así que necesito crear un gráfico con 262144 vértices y 2091012 bordes. Actualmente, estoy usando el siguiente gráfico:

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;

Estoy usando un gráfico de clase adicional (lo siento por el nombre no inspirado) que maneja el gráfico:

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

};

Crear un nuevo gráfico con 262144 vértices es bastante rápido, pero la inserción de los bordes lleva hasta 10 segundos, lo cual es demasiado lento para la aplicación deseada. En este momento, estoy insertando los bordes de la siguiente manera:

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

¿Hay algo que pueda hacer para mejorar la velocidad del programa? Estoy usando Microsoft Visual C ++ 2010 Express en modo de lanzamiento con optimización (recomendado por Boost). Pensé que podría usar un contenedor de listas para los vértices o los bordes, pero los vértices no son un problema y si uso listS para los bordes, se vuelve aún más lento.

Answer 1

adjacency_list es un propósito muy general; desafortunadamente nunca va a ser tan eficiente como una solución que explote la regularidad de tu caso particular de uso. BGL no es magia.

Su mejor opción es probablemente obtener la representación gráfica eficiente que usaría en ausencia de BGL (sugerencia: para un gráfico de los píxeles vecinos de una imagen, esto no asignará explícitamente todos esos objetos de nodo y borde) y luego ajuste BGL a este ( ejemplo ) o, de forma equivalente, implemente directamente una contraparte de las plantillas existentes adjacency_list / adjacency_matrix ( pautas conceptuales ) ajustadas a las regularidades de su sistema.

Por una representación optimizada, quiero decir, por supuesto, una en la que no almacena realmente todos los nodos y bordes explícitamente, sino que solo tiene alguna forma de iterar sobre enumeraciones de los nodos y bordes implícitos que surgen del hecho de que la imagen tiene un tamaño particular . Lo único que realmente debe almacenar es una matriz de contrapesos.