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

From: Jef Driesen (jefdriesen_at_[hidden])
Date: 2006-01-24 02:25:43

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? And how can I add a vertex only if it does not 
exist already?