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