Jef Driesen wrote:

Johan Oudinet wrote:

...

On 1/24/06, 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? Yes, and a set for your vertices too.

Doesn't this contradict with your statement below? How can a set prevent duplicates if there is no way to add vertex only if that vertex does not exist in the graph already? I tried using a set for the vertex list, but it makes no difference.

When using a list for both the adjacency and vertex list, i get these numbers: Maximum #labels: 2453 #vertices: 603844 <-- This should be equal to (or smaller than 2453) #edges: 301922 And using a set for both lists results in exactly the same output (and is also much slower)!

With the problem below fixed, the output for using lists is now Maximum #labels: 2453 #vertices: 2453 #edges: 301922 and for sets: Maximum #labels: 2453 #vertices: 2453 #edges: 7343 Seems like the set is doing well for edges, but not for the vertices (where I have to exclude duplicates manually). The obvious question is now what is a set doing for the vertices? If it can't be used to prevent duplicates, how can it be usefull? What key is used to sort the container, because it is certainly not my label.

...

...

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.

Using your idea of using a map seemed a very nice solution. But I can't get it work properly. I wrote a special "add_unique_vertex" function to replace the "boost::add_vertex" function in the code above. The program compiles, but crashes during the first call of "boost::add_edge". Even if replace the body of my function with "return boost::add_vertex(label, g);". What is going wrong?

template <class G> typename boost::graph_traits<G>::vertex_descriptor add_unique_vertex( unsigned int label, std::map map, G g) { [body removed] }

Ignore the problem related to the crash. I forgot to pass 'g' and 'map' as a reference!