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?
- 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? Also, I do not understand what "calls to 'tie' ... must be qualified" means.
- 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?
- As you stated, your code needs a license banner.
- You will eventually need a documentation file, preferably in HTML that is styled like the existing BGL documentation.
- I think you can just attach the header file to your emails, since the test code is in a separate email anyway. Also, it would make my life easier if you wrote your code/tests as if your header was in boost/graph/, since that is where it will end up eventually. If you do that, I will test it in place there as well.
-- Jeremiah Willcock
Daniel