Re: [Boost-users] [BGL] Help with initialization of graph from image

25 Jan 2006


      Johan Oudinet wrote:
...
On 1/24/06, Jef Driesen  wrote:
...
I'm trying to create a graph from an image, where pixel values are
regions labels. I have defined my graph to use lists instead of the
vectors (because I need to add/remove vertices and edges) and one extra
property for the vertex (the region label):
typedef boost::adjacency_list<
    boost::listS,        // Adjacency list
    boost::listS,        // Vertex list
    boost::undirectedS,  // Undirected graph
    unsigned int,        // Vertex property (=label)
    boost::no_property,  // Edge property
    boost::no_property,  // Graph property
    boost::listS         // Edge list
...
graph;
typedef boost::graph_traits<graph>::vertex_descriptor vertex_t;
typedef boost::graph_traits<graph>::edge_descriptor edge_t;
I have the following pseudo code to populate the graph:
graph g;
for each pixel (i,j) {
    unsigned int u_label = image[i][j];
    for each neighbourhood pixel (k,l) {
       unsigned int v_label = image[k][l];
       if (u_label != v_label) {
          // Find/add both vertices
          vertex_t u = boost::add_vertex(u_label,g);
          vertex_t v = boost::add_vertex(v_label, g);
          // Find/add edge
          boost::add_edge(u, v, g);
       }
    }
}
But this creates many duplicates (with regard to the label) for both
vertices and edges. How can i prevent this? Would using a set for the
edges solves my problem?
Yes, and a set for your vertices too.
Doesn't this contradict with your statement below? How can a set prevent
duplicates if there is no way to add vertex only if that vertex does not
exist in the graph already? I tried using a set for the vertex list, but
it makes no difference.

When using a list for both the adjacency and vertex list, i get these
numbers:
    Maximum #labels: 2453
    #vertices: 603844 <-- This should be equal to (or smaller than 2453)
    #edges: 301922
And using a set for both lists results in exactly the same output (and
is also much slower)!
...
...
And how can I add a vertex only if it does not
exist already?
You can't, unless using a map from vertex_label to vertex_descriptor and
  ensure the vertex_label doesn't exist in this map before inserting a vertex.
Using your idea of using a map seemed a very nice solution. But I can't
get it work properly. I wrote a special "add_unique_vertex" function to
replace the "boost::add_vertex" function in the code above. The program
compiles, but crashes during the first call of "boost::add_edge". Even
if replace the body of my function with "return boost::add_vertex(label,
g);". What is going wrong?

template <class G>
typename boost::graph_traits<G>::vertex_descriptor
add_unique_vertex(
       unsigned int label,
       std::map map,
       G g)
{
    typedef boost::graph_traits<G>::vertex_descriptor vertex_descriptor;
    typedef std::map vertex_map;
    typedef std::pair pair;

    // Search the vertex_map for the label. If
    // no vertex is found, a new entry is created.
    pair p = map.insert(vertex_map::value_type(label, vertex_descriptor()));
    if (p.second) {
       return (p.first->second = boost::add_vertex(label,g));
    } else {
       // Return existing vertex.
       return p.first->second;
    }
}