Johan Oudinet wrote:
On 1/24/06, Jef Driesen <jefdriesen@hotmail.com> 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)!
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<unsigned int, typename boost::graph_traits<G>::vertex_descriptor > map, G g) { typedef boost::graph_traits<G>::vertex_descriptor vertex_descriptor; typedef std::map<unsigned int, vertex_descriptor> vertex_map; typedef std::pair<vertex_map::iterator, bool> pair; // Search the vertex_map for the label. If // no vertex is found, a new entry is created. pair p = map.insert(vertex_map::value_type(label, vertex_descriptor())); if (p.second) { return (p.first->second = boost::add_vertex(label,g)); } else { // Return existing vertex. return p.first->second; } }