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

From: Jef Driesen (jefdriesen_at_[hidden])
Date: 2006-01-25 09:50:03

Jef Driesen wrote:
> Johan Oudinet wrote:
>> On 1/24/06, Jef Driesen <jefdriesen_at_[hidden]> 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<unsigned int, typename
> boost::graph_traits<G>::vertex_descriptor > map,
>        G g)
> {
>     [body removed]
> }

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