[BGL] Daisy chaining algorithms using vistor mechanism?
Still up hacking... Without cluttering the question with a ton of detail, basically I need to perform a DFS on a forest stored in a bidirectionalS adjacency_list and then perform a subgraph traversal in response to each finish_vertex invocation in the visitor. (The idea is to push information down the branches towards the root of a tree in the forest). Calling in_edges(v,g) from within the finish_vertex method in a dfs_visitor will not compile however. This is because the graph is passed by const reference into the visitor method and in_edges requires a non-const graph reference? (this seems similar in spirit to a question I posted a week or two ago about boost::get(some_property, Graph) from within a visitor). Generally, I would like to be able to daisy chain graph algorithms - that is invoke a sub-algorithm from within a visitor method called by a controlling algorithm. This would require that the sub-algorithm not change the graph topology, trample on properties used by its controller (e.g. coloring), or otherwise invalidate vertex descriptors or iterators so some care would need to be taken in designing the sub-algorithm. But it seems like a useful mechanism for extension. Am I missing something about getting at the in_edges given that I'm working with a const graph_t& in the context of the "controlling" DFS' visitor method? Why is this so restrictive? I'm guessing it might have something to do with having multiple copies of vertex and edge iterators floating around but I'm not sure. Will you comment on this please Jeremy? Thank you. - Chris Russell
Hi Chris, On Wed, 2 Oct 2002, Chris Russell wrote: [snip] cdr> finish_vertex method in a dfs_visitor will not compile however. This cdr> is because the graph is passed by const reference into the visitor cdr> method and in_edges requires a non-const graph reference? No, in_edges is declared const for the graph parameter, at least for adjacency_list, and it should be for other graph types as well. cdr> Generally, I would like to be able to daisy chain graph algorithms - cdr> that is invoke a sub-algorithm from within a visitor method called by cdr> a controlling algorithm. This would require that the sub-algorithm cdr> not change the graph topology, trample on properties used by its cdr> controller (e.g. coloring), or otherwise invalidate vertex cdr> descriptors or iterators so some care would need to be taken in cdr> designing the sub-algorithm. But it seems like a useful mechanism for cdr> extension. You can do that as long as you use a different color map, etc. Regards, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
Whoops... My bad. I did this: // given vertex_t Vertex, const graph_t& Graph boost::graph_traits<my_graph_t>::edge_iterator iterInEdgeCurrent, iterInEdgeEnd; //..................................................^ Bozo no no boost::tie(iterInEdgeCurrent, iterInEdgeEnd) = boost::in_edges(Vertex,Graph); ... What I meant was: boost::graph_traits<my_graph_t>::in_edge_iterator iterInEdgeCurrent, iterInEdgeEdge; Thanks Jeremy. Back on track. Regards - Chris Russell
Whenever I start feeling proud of myself due to my C++ prowess, I mosey over to the boost developer's list and am promptly humbled. Recently there was a discussion started by David Abrahams about how great MPL is. There were various comments that the following example was confusing or that it was perfectly clear, but nobody hinted toward what it actually does. I'd love to be excited about the current and upcoming possibilities in boost, but I just can't wrap my brain around this metaprogramming thing. Can anybody explain in English what the following does? Posted by David Abrahams on boost developers list:
Have I mentioned recently how totally cool MPL's lambda facility is? I can't believe I can do things like this, even with MSVC6. It makes my metaprograms SO much easier to manage! mpl::logical_and< is_reference_to_class<add_reference<mpl::_> > , mpl::logical_not< is_reference_to_args<add_reference<mpl::_> >
Thanks, Jeff
----- Original Message ----- From: "Jeff Faust" <jeff@opticalres.com> To: <Boost-Users@yahoogroups.com> Sent: Wednesday, October 02, 2002 11:32 AM Subject: [Boost-Users] MPL?
[...] Can anybody explain in English what the following does?
I believe that Aleksey posted the runtime pseudo-equivalent.
Posted by David Abrahams on boost developers list:
Have I mentioned recently how totally cool MPL's lambda facility is? I can't believe I can do things like this, even with MSVC6. It makes my metaprograms SO much easier to manage! mpl::logical_and< is_reference_to_class<add_reference<mpl::_> > , mpl::logical_not< is_reference_to_args<add_reference<mpl::_> >
[Aleksey, on 9/27] // "ideal" version, for comparison purposes: // is_reference_to_class( add_reference(_) ) // && !is_reference_to_args( add_reference(_) ) I can't say for sure what the code does myself, but if I could venture a guess, I would say that it's a condition for something else (maybe an iterative algorithm over a type container?) that checks to see if an argument is a reference type of various sorts. Basically, if you don't understand it, in this case, you probably don't need it. ;) I know I don't! Dave
Well, I didn't know I needed boost until I saw it. Same for STL several years back. 'Metaprogramming' comes up a lot on the boost list, but I have no understanding about what it's for--what problems it solves. The documentation is sparse. Then this thread comes up and everybody talks about it like it's obvious. I dislike being baffled. But mostly it's curiosity. I need something to talk about at parties and impress the ladies. MPL will do that, right? Right? Hello? Jeff -----Original Message----- From: David B. Held [mailto:dheld@codelogicconsulting.com] Sent: Wednesday, October 02, 2002 12:14 PM To: Boost-Users@yahoogroups.com Subject: Re: [Boost-Users] MPL? ----- Original Message ----- From: "Jeff Faust" <jeff@opticalres.com> To: <Boost-Users@yahoogroups.com> Sent: Wednesday, October 02, 2002 11:32 AM Subject: [Boost-Users] MPL?
[...] Can anybody explain in English what the following does?
I believe that Aleksey posted the runtime pseudo-equivalent.
Posted by David Abrahams on boost developers list:
Have I mentioned recently how totally cool MPL's lambda facility is? I can't believe I can do things like this, even with MSVC6. It makes my metaprograms SO much easier to manage! mpl::logical_and< is_reference_to_class<add_reference<mpl::_> > , mpl::logical_not< is_reference_to_args<add_reference<mpl::_> >
[Aleksey, on 9/27] // "ideal" version, for comparison purposes: // is_reference_to_class( add_reference(_) ) // && !is_reference_to_args( add_reference(_) ) I can't say for sure what the code does myself, but if I could venture a guess, I would say that it's a condition for something else (maybe an iterative algorithm over a type container?) that checks to see if an argument is a reference type of various sorts. Basically, if you don't understand it, in this case, you probably don't need it. ;) I know I don't! Dave Info: <http://www.boost.org> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
Hi Jeff, all, It seems that part of Jeff's question is "What is meta-programming good for?", which strikes me as a good question to ask (and I agree with all the other responses suggesting Alexandrescu's book as a good starting point). But, I thought it still might be useful to suggest a list of problems that I have solved, seen solved, or thought about solving with metaprogramming. The "classic" example of meta-programming is using lex & yacc - programs that themselves generate programs. The point of the MPL (and Loki) is to be able to do this in C++ rather than depending on an external tool. In general, what meta-programming lets you do is to do computation at compile time instead of at runtime. For example, you could precompute a table of values as compile time constants instead of filling a table in at initialization time. This might be useful in game programming, for precomputer trig functions. Alexandrescu's book shows how you can automatically generate class heirarchies. Or, have the compiler do the "dirty work" of implementing double-dispatch (picking a function to call based on the runtime types of 2 parameters instead of just one. Virtual functions give you one, metaprogramming gives you 2+ without a lot of code). I use meta-programming to be able to switch between having parameters for my simulation programs be hard-coded (ie compile time constants) or appear as command line arguments by changing just one line of code. MPL (and Loki) gives you the tools to do these kinds of compile-time computations by giving you fundamental algorithms and data structures that exist and can be manipulated in the compiler, but that don't actually exist at run time. Best Regards, -Tom Wenisch
participants (5)
-
Chris Russell -
David B. Held -
Jeff Faust -
Jeremy Siek -
Thomas Wenisch