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

From: Johan Oudinet (johan.oudinet_at_[hidden])
Date: 2006-01-24 18:12:05

On 1/24/06, Jef Driesen <jefdriesen_at_[hidden]> 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.

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

--
Johan