Boost Graph Library: Add Edges for a Large Graph

Question

I am trying to use the “smart scissor” for interactive image segmentation. Therefore, I have to create a directed graph from the image, where each vertex represents one pixel. Each vertex is then attached to each of its neighbors by two edges: one outgoing and one incoming edge. This is due to the fact that the cost of the edge (a, b) may differ from the cost (b, a). I use images with a size of 512 * 512 pixels, so I need to create a graph with 262144 vertices and edges 2091012. I am currently 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 use the optional Graph class (sorry for the non-integrated naming) that 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 vertices 262144 is pretty fast, but inserting edges takes up to 10 seconds, which is too slow for the desired application. Right now I am inserting the edges as follows:

 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 to improve program speed? I am using Microsoft Visual C ++ 2010 Express in release mode with optimization (as recommended by Boost). I thought I could use the listS container for vertices or edges, but the vertices are not a problem, and if I use listS for edges, it gets even slower.

Answer 1

adjacency_list is a very common goal; unfortunately, it will never be as effective as a solution using the regularity of your particular use case. BGL is not magical.

It is probably best to come up with an effective graphical representation that you would use in the absence of BGL (hint: for graphing neighboring pixels of an image, it will not explicitly highlight all these nodes and then install BGL on it ( example ), or equivalently just implement the analogy with existing adjacency_list / adjacency_matrix ( adjacency_matrix guidelines ) are configured to adjacency_matrix your system.

By optimized representation, of course, I mean one in which you do not actually store all nodes and edges explicitly, but just have some way to iterate over enumerations of implicit nodes and edges that arise due to the fact that the image is of a certain size. The only thing you need to store is an array of edge weights.