Help with initialization of graph (Boost Graph Library)

[Jef Driesen]

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?

[mlimber]

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

This post is off-topic here (see FAQ 5.9). You probably want to post to
the Boost users list:

http://boost.org/more/mailing_lists.htm#users

Cheers! --M

[Jef Driesen]

mlimber wrote:

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

This post is off-topic here (see FAQ 5.9). You probably want to post to
the Boost users list:

http://boost.org/more/mailing_lists.htm#users

I do not entirely agree with you that my post is off-topic here, but
it's a good idea do post my question to the boost users list anyway. I
wasn't even aware of the existence of that list.

[mlimber]

Jef Driesen wrote:

mlimber wrote:

This post is off-topic here (see FAQ 5.9). You probably want to post to
the Boost users list:

http://boost.org/more/mailing_lists.htm#users

I do not entirely agree with you that my post is off-topic here, but
it's a good idea do post my question to the boost users list anyway. I
wasn't even aware of the existence of that list.

I suppose the original post could be in the gray area for this
newsgroup, but since the graph library is not part of TR1, you'll
likely get better help from the Boost user's list.

Cheers! --M