[graph] Is reverse_graph<> read-only?
Hello! Is reverse_graph<> in Boost::Graph Library, read-only? I just can't beleive it:) Can it be fixed?
On Mon, 14 Feb 2011, al.zatv wrote:
Hello!
Is reverse_graph<> in Boost::Graph Library, read-only? I just can't beleive it:) Can it be fixed?
It appears to be read-only. It should be possible to add mutation; it just isn't there yet. Do you need that feature? -- Jeremiah Willcock
Jeremiah Willcock <jewillco@osl.iu.edu> писал(а) в своём письме Fri, 18 Feb 2011 01:49:27 +0300:
Is reverse_graph<> in Boost::Graph Library, read-only?
It appears to be read-only. It should be possible to add mutation; it just isn't there yet. Do you need that feature?
Yes. My program build two trees in the same graph. First tree is "forward". Second tree is "backward": build by the same algorithm, but in reverse order. So I need add_vertex and add_edge for reverse trees. I wrote them this way (please look if I'm correct - because I'm a newbie and can make stupid errors). ============= template <typename Graph> inline std::pair<typename reverse_graph<Graph,Graph&>::edge_descriptor, bool> add_edge(typename reverse_graph<Graph,Graph&>::vertex_descriptor u, typename reverse_graph<Graph,Graph&>::vertex_descriptor v, //const typename reverse_graph<Graph,Graph&>::edge_property_type& p, reverse_graph<Graph,Graph&> &g) { return add_edge(v,u,g.m_g); } template <typename Graph> inline std::pair<typename reverse_graph<Graph,Graph&>::edge_descriptor, bool> add_edge(typename reverse_graph<Graph,Graph&>::vertex_descriptor u, typename reverse_graph<Graph,Graph&>::vertex_descriptor v, const typename reverse_graph<Graph,Graph&>::edge_property_type& p, reverse_graph<Graph,Graph&> &g) { return add_edge(v,u,p,g.m_g); } ==============
On Fri, 18 Feb 2011, al.zatv wrote:
Jeremiah Willcock <jewillco@osl.iu.edu> писал(а) в своём письме Fri, 18 Feb 2011 01:49:27 +0300:
Is reverse_graph<> in Boost::Graph Library, read-only?
It appears to be read-only. It should be possible to add mutation; it just isn't there yet. Do you need that feature?
Yes. My program build two trees in the same graph. First tree is "forward". Second tree is "backward": build by the same algorithm, but in reverse order. So I need add_vertex and add_edge for reverse trees. I wrote them this way (please look if I'm correct - because I'm a newbie and can make stupid errors).
Do those versions work? I forgot whether edge_descriptors in the original graph are implicitly convertible to edge_descriptors in the reverse_graph; your implementations require that. Your code would be easy to fix for the other case, though. Could you please add in the rest of the mutating functions so that I can add your code to BGL? -- Jeremiah Willcock
Jeremiah Willcock <jewillco@osl.iu.edu> писал(а) в своём письме Fri, 18 Feb 2011 02:14:08 +0300:
Do those versions work?
Yes, they work as they should on graphs with adjacent_list<listS,listS.....> and with adjacent_list<vecS,vecS,.....> I don't check them on other types of graphs.
I forgot whether edge_descriptors in the original graph are implicitly convertible to edge_descriptors in the reverse_graph; your implementations require that. Your code would be easy to fix for the other case, though. Could you please add in the rest of the mutating functions so that I can add your code to BGL?
OK. My code in Boost - that's will be great:) I'll send that code to you later. But I don't know about iterators and descriptors stability: if some code in BGL assumes that it can delete an edge, and iterator on next edge will stay valid, it will fail with reverse_graph. I just don't know BGL good enought to understand if it can be a problem or not. WBR, Alexander Zatvornitskiy
On Fri, 18 Feb 2011, al.zatv wrote:
Jeremiah Willcock <jewillco@osl.iu.edu> писал(а) в своём письме Fri, 18 Feb 2011 02:14:08 +0300:
Do those versions work?
Yes, they work as they should on graphs with adjacent_list<listS,listS.....> and with adjacent_list<vecS,vecS,.....> I don't check them on other types of graphs.
It turns out that what you are doing will work in general.
I forgot whether edge_descriptors in the original graph are implicitly convertible to edge_descriptors in the reverse_graph; your implementations require that. Your code would be easy to fix for the other case, though. Could you please add in the rest of the mutating functions so that I can add your code to BGL?
OK. My code in Boost - that's will be great:) I'll send that code to you later. But I don't know about iterators and descriptors stability: if some code in BGL assumes that it can delete an edge, and iterator on next edge will stay valid, it will fail with reverse_graph. I just don't know BGL good enought to understand if it can be a problem or not.
Iterator validity is up to the underlying graph; your functions will not change that behavior at all. -- Jeremiah Willcock
Hi Jeremiah, On Friday, 18. February 2011 00:14:08 Jeremiah Willcock wrote:
On Fri, 18 Feb 2011, al.zatv wrote:
Jeremiah Willcock <jewillco@osl.iu.edu> писал(а) в своём письме Fri, 18 Feb
2011 01:49:27 +0300:
Is reverse_graph<> in Boost::Graph Library, read-only?
It appears to be read-only. It should be possible to add mutation; it just isn't there yet. Do you need that feature?
Yes. My program build two trees in the same graph. First tree is "forward". Second tree is "backward": build by the same algorithm, but in reverse order. So I need add_vertex and add_edge for reverse trees. I wrote them this way (please look if I'm correct - because I'm a newbie and can make stupid errors).
Do those versions work? I forgot whether edge_descriptors in the original graph are implicitly convertible to edge_descriptors in the reverse_graph; your implementations require that.
Just of pure interest, where do you see this requirement in the code? It's not that I doubt the fact that it actually is like this but I am interested in knowing how this can be seen in these short, two functions?
Your code would be easy to fix for the other case, though.
Again, I would really like to know how.
Could you please add in the rest of the mutating functions so that I can add your code to BGL?
-- Jeremiah Willcock
Thank you. Best, Cedric
On Fri, 18 Feb 2011, Cedric Laczny wrote:
Hi Jeremiah,
On Friday, 18. February 2011 00:14:08 Jeremiah Willcock wrote:
On Fri, 18 Feb 2011, al.zatv wrote:
Jeremiah Willcock <jewillco@osl.iu.edu> писал(а) в своём письме Fri, 18 Feb
2011 01:49:27 +0300:
Is reverse_graph<> in Boost::Graph Library, read-only?
It appears to be read-only. It should be possible to add mutation; it just isn't there yet. Do you need that feature?
Yes. My program build two trees in the same graph. First tree is "forward". Second tree is "backward": build by the same algorithm, but in reverse order. So I need add_vertex and add_edge for reverse trees. I wrote them this way (please look if I'm correct - because I'm a newbie and can make stupid errors).
Do those versions work? I forgot whether edge_descriptors in the original graph are implicitly convertible to edge_descriptors in the reverse_graph; your implementations require that.
Just of pure interest, where do you see this requirement in the code? It's not that I doubt the fact that it actually is like this but I am interested in knowing how this can be seen in these short, two functions?
He's directly returning the result of add_edge() on the underlying graph as a pair<reverse_graph::edge_descriptor, bool> without explicitly converting the underlying graph's edge_descriptor to the reverse_graph's version. Anyway, it turns out that the descriptors are exactly the same between the underlying and reverse graphs; that is not documented, however.
Your code would be easy to fix for the other case, though.
Again, I would really like to know how.
See above about the types being the same. If not, there is no documented way to do the conversion. -- Jeremiah Willcock
On Friday, 18. February 2011 07:50:09 Jeremiah Willcock wrote:
On Fri, 18 Feb 2011, Cedric Laczny wrote:
Hi Jeremiah,
On Friday, 18. February 2011 00:14:08 Jeremiah Willcock wrote:
On Fri, 18 Feb 2011, al.zatv wrote:
Jeremiah Willcock <jewillco@osl.iu.edu> писал(а) в своём письме Fri, 18 Feb
2011 01:49:27 +0300:
Is reverse_graph<> in Boost::Graph Library, read-only?
It appears to be read-only. It should be possible to add mutation; it just isn't there yet. Do you need that feature?
Yes. My program build two trees in the same graph. First tree is "forward". Second tree is "backward": build by the same algorithm, but in reverse order. So I need add_vertex and add_edge for reverse trees. I wrote them this way (please look if I'm correct - because I'm a newbie and can make stupid errors).
Do those versions work? I forgot whether edge_descriptors in the original graph are implicitly convertible to edge_descriptors in the reverse_graph; your implementations require that.
Just of pure interest, where do you see this requirement in the code? It's not that I doubt the fact that it actually is like this but I am interested in knowing how this can be seen in these short, two functions?
He's directly returning the result of add_edge() on the underlying graph as a pair<reverse_graph::edge_descriptor, bool> without explicitly converting the underlying graph's edge_descriptor to the reverse_graph's version.
I just saw, that reverse_graph.hpp does not provide add_edge()... Which function is then called? The one of the underlying graph, that is _not_ reversed? Because I was assuming that add_ege would simply return an edge_descriptor of the same type as the input graph, which in this case actually is reverse_graph<>. Therefore I didn't quite see the implicit conversion...
Anyway, it turns out that the descriptors are exactly the same between the underlying and reverse graphs; that is not documented, however.
Your code would be easy to fix for the other case, though.
Again, I would really like to know how.
See above about the types being the same. If not, there is no documented way to do the conversion.
-- Jeremiah Willcock
Best, Cedric
On Fri, 18 Feb 2011, Cedric Laczny wrote:
On Friday, 18. February 2011 07:50:09 Jeremiah Willcock wrote:
On Fri, 18 Feb 2011, Cedric Laczny wrote:
Hi Jeremiah,
On Friday, 18. February 2011 00:14:08 Jeremiah Willcock wrote:
On Fri, 18 Feb 2011, al.zatv wrote:
Jeremiah Willcock <jewillco@osl.iu.edu> писал(а) в своём письме Fri, 18 Feb
2011 01:49:27 +0300:
> Is reverse_graph<> in Boost::Graph Library, read-only?
It appears to be read-only. It should be possible to add mutation; it just isn't there yet. Do you need that feature?
Yes. My program build two trees in the same graph. First tree is "forward". Second tree is "backward": build by the same algorithm, but in reverse order. So I need add_vertex and add_edge for reverse trees. I wrote them this way (please look if I'm correct - because I'm a newbie and can make stupid errors).
Do those versions work? I forgot whether edge_descriptors in the original graph are implicitly convertible to edge_descriptors in the reverse_graph; your implementations require that.
Just of pure interest, where do you see this requirement in the code? It's not that I doubt the fact that it actually is like this but I am interested in knowing how this can be seen in these short, two functions?
He's directly returning the result of add_edge() on the underlying graph as a pair<reverse_graph::edge_descriptor, bool> without explicitly converting the underlying graph's edge_descriptor to the reverse_graph's version.
I just saw, that reverse_graph.hpp does not provide add_edge()... Which function is then called? The one of the underlying graph, that is _not_ reversed?
Yes -- he's calling add_edge on g.m_g, the underlying graph.
Because I was assuming that add_ege would simply return an edge_descriptor of the same type as the input graph, which in this case actually is reverse_graph<>. Therefore I didn't quite see the implicit conversion...
It's implicitly converting from edge_descriptors of the underlying graph to those of the reverse_graph. -- Jeremiah Willcock
Jeremiah Willcock <jewillco@osl.iu.edu> wrote, Fri, 18 Feb 2011 02:14:08 +0300:
Is reverse_graph<> in Boost::Graph Library, read-only? It appears to be read-only. It should be possible to add mutation; it just isn't there yet. Do you need that feature?
other case, though. Could you please add in the rest of the mutating functions so that I can add your code to BGL?
Hello! I find the time and add all mutable functions. Not fast, but I did it:) I attach them to this message. I also wrote small test program, but may be it must be tested more deeply. I want to find way to do it with minimal writing of code. What do you think? And, one problem: it doesn't pass test for MutableBidirectionalGraphConcept. For example: typedef adjacency_list<setS, vecS, bidirectionalS> fwdGraph; typedef reverse_graph<fwdGraph,fwdGraph&> Graph; //TODO: this fails: function_requires< MutableBidirectionalGraphConcept<Graph> >(); It is in attached test file. Could you please drop a look at this? Thank you. Alexander Zatvornitskiy.
On Tue, 8 Mar 2011, al.zatv wrote:
Jeremiah Willcock <jewillco@osl.iu.edu> wrote, Fri, 18 Feb 2011 02:14:08 +0300:
Is reverse_graph<> in Boost::Graph Library, read-only? It appears to be read-only. It should be possible to add mutation; it just isn't there yet. Do you need that feature?
other case, though. Could you please add in the rest of the mutating functions so that I can add your code to BGL?
Hello! I find the time and add all mutable functions. Not fast, but I did it:) I attach them to this message.
I also wrote small test program, but may be it must be tested more deeply. I want to find way to do it with minimal writing of code. What do you think?
And, one problem: it doesn't pass test for MutableBidirectionalGraphConcept. For example:
typedef adjacency_list<setS, vecS, bidirectionalS> fwdGraph; typedef reverse_graph<fwdGraph,fwdGraph&> Graph; //TODO: this fails: function_requires< MutableBidirectionalGraphConcept<Graph> >();
It is in attached test file. Could you please drop a look at this?
I'm taking a look; one issue is that your test file is not valid C++03 (it uses C++0x auto). Some of your failures were because of other issues in BGL; those are now fixed (r69726 in trunk). I had failures in your code even without uncommenting anything; I think there are two issues: 1. You are using G::vertex_property_type rather than vertex_property_type<G>::type to get the list of vertex properties, and the same for edge properties. The member forms of those traits are not defined for reverse_graph. 2. You don't have a remove_edge overload that takes an out_edge_iterator as the first parameter (you have one for edge_iterator, but that is not the same thing). -- Jeremiah Willcock
Jeremiah Willcock <jewillco@osl.iu.edu> писал(а) wrote, on Tue, 08 Mar 2011 23:57:12 +0300:
It is in attached test file. Could you please drop a look at this?
I'm taking a look; one issue is that your test file is not valid C++03 (it uses C++0x auto). Some of your failures were because of other issues in BGL; those are now fixed (r69726 in trunk). I had failures in your code even without uncommenting anything;
hmm,it's working on my computer:) g++4.2, boost 1.45
I think there are two issues: 1. You are using G::vertex_property_type rather than ..
Thank you for directions! I will fix them and let you know.
On Wed, 9 Mar 2011, al.zatv wrote:
Jeremiah Willcock <jewillco@osl.iu.edu> писал(а) wrote, on Tue, 08 Mar 2011 23:57:12 +0300:
It is in attached test file. Could you please drop a look at this?
I'm taking a look; one issue is that your test file is not valid C++03 (it uses C++0x auto). Some of your failures were because of other issues in BGL; those are now fixed (r69726 in trunk). I had failures in your code even without uncommenting anything;
hmm,it's working on my computer:) g++4.2, boost 1.45
I was using a prerelease of 4.6 (to get C++0x features) and the Boost trunk. -- Jeremiah Willcock
participants (3)
-
al.zatv -
Cedric Laczny -
Jeremiah Willcock