On Friday, 21. May 2010 22:16:01 Jeremiah Willcock wrote:
On Fri, 21 May 2010, Cedric Laczny wrote:
In fact, I was not aware that I could have the vertex_index map as a member of the iterator. i only realized it recently. Unfortunately, I don't program C++ that often and have never done it in such detail as I have to do it now. Thus, I'm still in the process of learning and especially discovering the great abilities of boost-library. To answer your question, indeed, it should match. I'm thinking of creating a "simple" graph as a copy of the original one, containing the same number of vertices and the same edges as in the original graph because I want to keep the original graph only for storing purposes. More specifically, the original graph's vertices have bundled properties (at the moment only 2 strings) and for the algorithm I want to implement, the vertices need a mark, that can be set. First, I don't know how to add this _later_ to the graph (don't even know if it is possible though), and second, there might be different algorithms I have to implement that will need special properties (e.g. several marks) and always changing this on the original graph is not what I find that "nice" :)
You can just use external properties if you want to add properties later; properties such as marks/colors/distances/... can just be built as std::vectors and turned into property maps using iterator_property_map. That way, each algorithm can create its temporary property maps, use them, and destroy them without needing to copy or change the graph at all.
Actually, I now use boost::copy_graph() to create the copy, together with the following vertex copier: // Used to copy only relevant properties template
struct Vcopier{ Vcopier(const G1& g1, G2& g2)
: m_g1(g1), m_g2(g2)
{}
// explicit cast operator // Used to "convert" one vertex into another template< class V1, class V2> void operator() (const V1& v1, const V2& v2) const {
m_g2[v2] = false;
}
const G1& m_g1; G2& m_g2;
};
Thus, I can directly set the mark to a default value. For me, as a beginner, this is far easier than doing this with a custom InputIterator. However, if you find that with an InputIterator this might be also nice to solve, I really would appreciate an example.
I don't know if the vertex_index map has data in it either. However, when using vecS for the vertex-list, this property_map is automatically created and _not_changeable from outside (had to realize that during my tests). The vertex indices are accessible via get(vertex_index, g, v) and for my simple example, that numbering matches the numbering in the original graph. But, what I definitely need to know for sure is, if this is pure coincidence or if copy_graph() does always preserve the vertex-numbering?
I do not know. Try using external properties instead of copy_graph and see if that solves your problem. It should be a lot simpler and faster than graph copying.
Great suggestion, thank you! This is especially apealing, as the algorithm only needs to mark the vertices and I don't even need the copied edges. By using external properties (here is a nice example (http://www.informit.com/articles/article.aspx?p=25777&seqNum=6))) I can also be sure, that the vertices stay the same and I don't risk to mix something up due to a probably wrong mapping from one graph to the other. So thank you again.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Best, Cedric