a question about incremental_component and disjoint_sets.
Hi, I have a 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: //.... some graph typedef 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
On Apr 11, 2005, at 10:17 AM, Vivid Yang wrote:
I have a 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?
Yes. Whenever you add a vertex, you will need to call make_set on it. Also, be careful with the property maps rank and parent: if you add vertices, you'll need to make space in those property maps, but if the vectors reallocate your property maps will become invalid. The easiest way to handle things would be to either (1) use a vector_property_map, which automatically resizes and won't invalidator, or (2) make the rank and parent properties part of the vertices in the graph.
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: //.... some graph typedef std::vector<graph_vertex_size_type> rank; std::vector<graph_vertex_descriptor> parent; disjoint_sets<Rank, Parent> ds; ...... };
In the constructor for X, you will need to initialize "ds" with the rank and property maps. The example in http://www.boost.org/libs/graph/doc/incremental_components.html should help with this. Doug
participants (2)
-
Doug Gregor -
Vivid Yang