Help with initialization of graph (Boost Graph Library)


J

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
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[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?
 
Ad

Advertisements

M

mlimber

Jef said:
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
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[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
 
J

Jef Driesen

mlimber said:
Jef said:
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
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[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.
 
Ad

Advertisements

M

mlimber

Jef said:
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top