title: Boost Graph Library: edge insertion slow for large graph
body: <p>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:</p>
  
  <pre><code>typedef property&lt;vertex_index_t, int,
          property&lt;vertex_distance_t, double,
          property&lt;x_t, int, 
          property&lt;y_t, int
          &gt;&gt;&gt;&gt; VertexProperty;
  
  typedef property&lt;edge_weight_t, double&gt; EdgeProperty;
  
  // define MyGraph
  typedef adjacency_list&lt;     
      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
      &gt; MyGraph;
  </code></pre>
  
  <p>I'm using an additional class <em>Graph</em> (sorry for the uninspired naming) which  handles the graph:</p>
  
  <pre><code>class Graph
  {
  private:
      MyGraph *graph;
      property_map&lt;MyGraph, vertex_index_t&gt;::type indexmap;
      property_map&lt;MyGraph, vertex_distance_t&gt;::type distancemap;
      property_map&lt;MyGraph, edge_weight_t&gt;::type weightmap;
      property_map&lt;MyGraph, x_t&gt;::type xmap;
      property_map&lt;MyGraph, y_t&gt;::type ymap;
      std::vector&lt;MyGraph::vertex_descriptor&gt; predecessors;
  public:
      Graph();
      ~Graph();
  </code></pre>
  
  <p>};</p>
  
  <p>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:</p>
  
  <pre><code>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 &gt; 0){
          if(x &gt; 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 &lt; 511){
              tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y-1)+(x+1)], *graph);    // upper right
          }
      }
      if(x &lt; 511){    
          tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y)+(x+1)], *graph);    // right
      }
      if(y &lt; 511){
          if(x &gt; 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 &lt; 511){
              tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y+1)+(x+1)], *graph);    // lower right
          }
      }
      if(x &gt; 0){
          tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y)+(x-1)], *graph);    // left
      }
  }
  </code></pre>
  
  <p>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 <em>listS</em> container for the vertices or edges but the vertices are no problem and if I use <em>listS</em> for the edges, it gets even slower.</p>