Boost Graph Library: edge insertion slow for large graph

Question

I'm trying to use implement an "intelligent scissor" for an interactive image segmentation. Therefore, I have to create a directed graph from an image where each vertex represents a single pixel. Each vertex is then conntected to each of its neighbours by two edges: one outgoing and one incoming edge. This is due to the fact that the cost of an edge (a,b) may differ from the cost of (b,a). I'm using images with a size of 512*512 pixel so i need to create a graph with 262144 vertices and 2091012 edges. Currently, I'm using the following graph:

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'm using an additional class Graph (sorry for the uninspired naming) which handles the 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();

};

Creating a new graph with 262144 vertices is pretty fast but the insertion of the edges tooks up to 10 seconds which is way too slow for the desired application. Right now, I'm inserting the edges the following way:

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

Is there anything I can do do improve the speed of the programm? I'm using Microsoft Visual C++ 2010 Express in release mode with optimization (as recommended by Boost). I thought I could use a listS container for the vertices or edges but the vertices are no problem and if I use listS for the edges, it gets even slower.

Answer 1

adjacency_list is very general purpose; unfortunately it's never going to be as efficient as a solution exploiting the regularity of your particular use-case could be. BGL isn't magic.

Your best bet is probably to come up with the efficient graph representation you'd use in the absence of BGL (hint: for a graph of an image's neighbouring pixels, this is not going to explicitly allocate all those node and edge objects) and then fit BGL to it (example), or equivalently just directly implement a counterpart to the existing adjacency_list / adjacency_matrix templates (concept guidelines) tuned to the regularities of your system.

By an optimised representation, I of course mean one in which you don't actually store all the nodes and edges explicitly but just have some way of iterating over enumerations of the implicit nodes and edges arising from the fact that the image is a particular size. The only thing you should really need to store is an array of edge weights.