Re: [Boost-users] [BGL] Help with initialization of graph from image

25 Jan 2006


      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!