On Wed, 23 Jun 2010, Daniel Trebbien wrote:
Hi Jeremiah,
Thank you for your feedback. This gives me a lot to work on, which I will be implementing soon.
I have addressed some of your points below.
On 2010-06-23, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
I skimmed through your code, and saw couple of little things to change:
- Boost code doesn't use tabs (<URL:http://www.boost.org/community/policy.html#tabs>)
- I don't think you need to use BOOST_DEDUCED_TYPENAME; I just use "typename" myself and haven't had any problems. I think it might be a workaround for compilers that are not used anymore.
- Your header guard should start with BOOST_GRAPH_ to avoid conflicts with other header files.
- You can replace "c.size() > 0" by "!c.empty()"; this is likely to be faster for many containers.
- Your non-detail code should be in the "boost" namespace.
- From a superficial look, it seems like maxAdjSearchList might be implementable as a heap (or some other priority queue) rather than as a multiset. Am I mistaken on that?
You are correct that I should use a maximum priority queue. The algorithm is best implemented with a Fibonacci heap, but I couldn't get the C++ implementation that appeared in Dr. Dobb's Journal to work. Granted, this was early on and the segmentation fault that I was getting could have been caused by my own code.
I also looked at `std::priority_queue`, but it does not implement `increasekey`.
For this algorithm, I need to associate each vertex with a value w(A), which is the sum of weights of edges containing the vertex and a point in a set A of vertices. Each iteration until the priority queue is empty, I need to select and remove the vertex u with the greatest w(A) to be added to A, thus requiring an update (increasekey) of the w(A) values of vertices v in the priority queue such that {u, v} is in E, the set of edges.
How do other BGL algorithms implement priority queues having the `increasekey` operation?
We have several heap implementations in BGL that support the increasekey operation. The one you may want to use is the d-ary heap (<boost/graph/detail/d_ary_heap.hpp>) since it seems to be the fastest in practice (although not in theoretical complexity); there are comments in that file on how to use it. Look at <boost/graph/dijkstra_shortest_paths.hpp> for example uses of several of the heaps. Note that the d-ary heap includes an indirect comparison (comparing values from a weight or distance map) natively, while some of the other heaps need the indirect_cmp function object (from <boost/pending/indirect_cmp.hpp>) to implement that. Dijkstra's algorithm uses all of the things I mentioned so you can look there to see sample code.
- Operations on graphs and property maps (but not on tuples) need to use unqualified names (such as "get" and "target") in order for ADL to work on user-defined graph types that are not in the boost namespace. Calls to "tie", however, must be qualified (I had to fix many of those yesterday because unqualified calls to tie break C++0x compilers).
I am not sure what you mean by "need to use unqualified names". Do you mean without the `boost::` namespace qualification?
Yes.
Also, I do not understand what "calls to 'tie' ... must be qualified" means.
Those must have a namespace qualification.
- Is there a reason that you do not handle parallel edges? Is it just a simplification in the code?
- It looks like the code handling sOutEdges and tOutEdges is unnecessarily complicated. Are you just intersecting the two lists of out edges? If so, you can use lookup_edge (from <boost/graph/lookup_edge.hpp>) to allow edge lookups in constant time for adjacency matrices (however, unlike the map-based implementation, lookup_edge takes linear time when it must actually do a search).
- You may want to use the macros in <boost/graph/iteration_macros.hpp> to simplify your code. Those macros replace explicit declarations of iterators and tie operations when you are doing a simple iteration through vertices, out edges, etc. If you use them, please include <boost/graph/iteration_macros_undef.hpp> at the end of your file.
- Property maps are passed by copy; they are intended to be lightweight and using copies allows temporary property maps to be passed in.
- Are users always going to pass in all of the parameters you have in your algorithm? If not, overloads or named parameters may be worthwhile to add.
Named parameters would be good. What Boost libraries can I use for named parameters?
Although we have wanted to move to Boost.Parameter for a while, BGL currently uses its own named parameter mechanism. I don't know if it is documented anywhere; your best hope would probably be to look through another algorithm in BGL that uses named parameters and see what the calls look like. Some of the handling of property maps is complicated, though, so you may want to wait on adding named parameters until the rest of the algorithm is finished and ready to submit. -- Jeremiah Willcock