On Wednesday, 19. May 2010 19:08:52 Jeremiah Willcock wrote:

On Wed, 19 May 2010, Cedric Laczny wrote:

...

Hi,

I have a graph with quite some information stored in its vertices and edges.

Now I would like to perform some analyses on the general overall topology of the graph. Therefore I don't need this "big graph" but only a graph that has the same number of nodes and matching edges to the "big graph".

Do you mean a subgraph? There is an adaptor for those in BGL already.

...

To this end, I wanted to use the adjacency_list() constructor together with an EdgeIterator that models the InputIterator so the routines of the boost-graph library would take care of creating the new "simple graph", which indeed would be a nice solution.

However, I just don't get it how to program an EdgeIterator with the following constraints (taken from http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/adjacency_list.html):

The EdgeIterator must be a model of InputIterator. The value type of the EdgeIterator must be a std::pair, where the type in the pair is an integer type.

One thing I would recommend is to use Boost.Iterator's iterator_adaptor. You might even be able to do what you want with transform_iterator.

...

Here's what I experimented with so far:

<--- Code --->

template< class EdgeIterator, class Edge > class MyEdgeIterator// : public input_iterator< std::pair > { public: MyEdgeIterator() {};

MyEdgeIterator(EdgeIterator& rhs) : actual_edge_it_(rhs) {};

MyEdgeIterator(const MyEdgeIterator& to_copy) {};

bool operator==(const MyEdgeIterator& to_compare) { return actual_edge_it_ == to_compare.actual_edge_it_; }

bool operator!=(const MyEdgeIterator& to_compare) { return !(*this == to_compare); }

Edge operator*() const { return *actual_edge_it_; }

const MyEdgeIterator* operator->() const; MyEdgeIterator& operator ++() { ++actual_edge_it_; return *this; }

MyEdgeIterator operator ++(int) { MyEdgeIterator tmp = *this; ++*this; return tmp; }

private: EdgeIterator& actual_edge_it_; }

<--- Code-End --->

Especially, I'm having trouble with the fact that the EdgeIterator must return a pair of the vertex indices that the actual edge "points to".

I think that this must include something like get(vertex_index_t, adjacency_list(...), source(*EdgeIterator, adjacency_list(...)). But this would mean that e.g. MyEdgeIterator would additionally need the vertex-property map of vetex indices. This seems a bit too much information packed into this one, small iterator.

Does the vertex numbering of the new graph need to match the numbering of the old one? In any case, why can't you have the vertex_index map as a member of the iterator? Property maps are supposed to be small and cheap to copy, and these constructors do not copy their iterators too often anyway. I don't know if the vertex_index map for adjacency_list even has any data at all; I believe it is an identity function or something fairly close. Even a fairly large iterator should not be a problem to use, though; if you aesthetically prefer not to store the property map, you can use a shared_ptr that points to the property map instead.

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" :) 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? Thank you. Best, Cedric

-- Jeremiah Willcock

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

On Thursday, 20. May 2010 21:32:51 Trevor Harmon wrote:

On May 19, 2010, at 12:19 AM, Cedric Laczny wrote:

...

I have a graph with quite some information stored in its vertices and edges. Now I would like to perform some analyses on the general overall topology of the graph. Therefore I don't need this "big graph" but only a graph that has the same number of nodes and matching edges to the "big graph".

I am wondering if this is a case of premature optimization. Are you sure that removing these many properties attached to the vertices and edges would actually speed up the analysis? I would expect there to be little if any difference. Also, it is possible that the task of creating the duplicate graph would offset any speed gains there might be in the subsequent analysis.

Indeed, this is a good point. Copying the graph with copy_graph() takes O(|V| +|E|). Most of the algorithms I know/use will be linear or nearly linear, so this won't affect much of th asymptotic runtime. However, in reality this might indeed slow-up the whole thing. As said in the response to Jeremiah Willcock, I have two concerns on working on the original graph. First, the properties there are bundled properties and I don't know, neither do I if it's possible in general, how to add properties later on. Because second, I might implement different algorithms that may have special requirements (e.g. multiple flags) and always doing these adjustments on the original graph is something I don't know of if this would be a good/"nice" idea. In any case, I agree with you that _not_ doing all this copying would be favorable, as it is in most such cases. So if you have an idea, I will be happy to hear about. Best, Cedric

Trevor

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users