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