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

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

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)!

>> 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;
    }
}