Hi, I have a further question about incremental_component and disjoint_sets. Here is the context: I have a class object initialized with an empty boost::graph. The algorithm incrementally builds the graph with the function add_vertex(graph). At the same time, I have to maintain the connected components of the graph. Here is the question: I know incremental_component.hpp can deal with the case edges are being added. Could it deal with the case that vertices are being added? Especially at the beginning, the graph is empty. And it seems I cannot declare an empty disjoint_sets variable in the class: classe X { ...... protected: std::vector<graph_vertex_size_type> rank; std::vector<graph_vertex_descriptor> parent; disjoint_sets<Rank, Parent> ds; ...... }; Here is the compiler error: error C2248: 'disjoint_sets<unsigned int *,void * *,struct boost::find_with_full_path_compression>::disjoint_sets<unsigned int *,void * *,struct boost::find_with_full_path_compression> ' : cannot access private member declared in class 'boost::disjoint_sets<unsigned int *,void * *,struct boost::find_with_full_path_compression>' e:\temp\boost\boost_1_32_0\boost\pending\disjoint_sets.hpp(68) : see declaration of 'disjoint_sets<unsigned int *,void * *,struct boost::find_with_full_path_compression>::disjoint_sets<unsigned int *,void * *,struct boost::find_with_full_pat h_compression>' Could anybody help? Thanks a lot. Vivid "Vivid Yang" <yyd_iris@yahoo.com> wrote in message news:d2u63o$csc$1@sea.gmane.org...
Hi,
I saw all the BGL examples begin with enumeration: // Make convenient labels for the vertices enum { Amherst, Boston, City, Denver, Egypt, Niagara }; So it is convenient to access properties, for example: distance(Boston) = 50; //distance is a property of vertices
The problem is that I have to build my graph incrementally and might have to remove some vertices later. So enumeration does not work for me. When I want to set distance(Boston) = 50, I have to find the descriptor for "Boston" first, (It takes O(n) to traverse all the vertices). It is too expensive for a large graph.
Is there anyway I can skip this step? I am thinking add a hash table, which maps each city to a descriptor. I have to update the hash table whenever I remove vertices. It is inconvenient neither.
Do I think it in the right way? Any suggestions?
Thanks a lot. Vivid