On Sun, 4 Jul 2010, Daniel Trebbien wrote:
Hello Jeremiah,
I commented below.
Why do you have IndexInHeapMap as an input parameter to the algorithm? Do you expect that a user would ever pass it in directly?
I figured that I would allow it as an input parameter for the same reason as why `assignments` and `wAs` are possible input parameters: all three are utility maps that have meaningless values at algorithm completion, so the temporary, underlying storage of the maps can be created if not specified, but the user might not need to create a `std::vector` backing for them because perhaps the per-vertex utility values were made into vertex properties, or perhaps the user wishes to use a container that is backed by a custom allocator.
Following similar reasoning, I was thinking about a HeapContainer input parameter. What do you think?
Right now, Dijkstra's algorithm creates those structures internally in the normal case. I'm fine with making the heap an optional parameter, but not the underlying storage. I guess it makes sense to allow the index_in_heap_map to be a parameter; that could then be added to Dijkstra's algorithm as well.
What is the difference between parity_map and vertex_parity_map, especially considering that you do not appear to use the second in your algorithm? Will you ever use vertex_parity_map as a named parameter name? That is the only reason it should appear in the list of duplicate parameter names. I think just having vertex_parity_map as an alias to parity_map is not enough of a reason to have it as a parameter name.
Oh, my mistake. I meant to alias `vertex_assignment_map` and `assignment_map` rather than `vertex_parity_map` and `parity_map`.
OK. Is there a reason that you need two names for that? It is much simpler to have only one name for each parameter; that avoids having to use the duplicate name list (which is for parts of BGL that have aliased parameter names for backwards compatibility).
I was thinking about writing an implementation of a randomized min-cut algorithm by Karger that merges edges rather than vertices. This might require an `edge_assignment_map` and `vertex_assignment_map`. I'm not sure. Perhaps this change can come later if I decide to implement this algorithm.
We can just add both of those now.
The code in <boost/graph/bipartite.hpp> uses a partition map to record its result, either passed in by the user or created internally. Is it possible for you to use that name as well? Or does it not make sense for your algorithm? There is currently on named parameter for that, since the code in bipartite.hpp does not use named parameters; that could be added, though.
I could use "black" and "white". That will work.
It's fine if the partition map has bool as its value type, so you don't need to change your code other than the name.
Your default for parity_map is dummy_property_map; did you mean instead to use the vertex_parity_map from the graph if it has one?
No, I figured that the user might not be interested in the vertex parities, so the default `dummy_property_map` would throw away this information.
I thought that the parities were the (only) output of the algorithm. Is there ever a case where the user would not want that?
If vertex_assignment_map is a temporary for the user-exposed parts of your algorithm, it should not be an explicit parameter; it should be generated instead (like index_in_heap_map is for dijkstra_shortest_paths()).
BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS does not have a semicolon after the argument list.
Okay
I refactored the color_map_maker code in named_function_params.hpp so it would be more useful for you. You should now just be able to write objects like make_color_map_from_arg_pack for the property maps that you need to create. Note that if you have a different value type for each map that you are creating, you can leave off the second template argument to make_property_map_from_arg_pack_gen (and the default value from its constructor) and then pass the default value that you want into the generated class's operator()().
I see it in Subversion, and will switch to using it. Thank you.
Switching to two-space indentation and K&R-style formatting in your code will make the lines shorter and make it fit better with existing BGL code.
Sure, I'll switch the code to two spaces.
What style changes do I need to make to make it K&R style?
It turns out that we actually use a two-space variant of the Java standard coding style (that you can find online). I think <URL:http://osl.iu.edu/download/research/mtl/papers/code_stds.pdf> (see pages starting at 25) is still reasonably accurate, except for the formatting of the opening braces of functions. Of course, anything that's explicitly specified in the Boost requirements takes precedence.
Could you please use a Boost directory layout for your code?
Sure
Thanks. That will make testing and integrating it much easier.
Where do you think your function should go in the BGL table of contents? What name should I use for it and what section should it be under?
In the "Algorithms" chapter, I think that a section titled "Min-Cut Algorithms" should be added between "Maximum Flow and Matching Algorithms" and "Sparse Matrix Ordering Algorithms" because min-cuts are related to max-flow algorithms: http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
Are you sure that you don't want me to add "min-cut" to the maximum flow section title and then put your code in there? How related is your code to standard max-flow algorithms? BTW, what is the timeframe that you expect to have this finished? Are you targeting getting it into 1.44.0? That would require a working version of the code by tomorrow (July 5), but that would not need documentation and would probably only require minimal tests. It would be more pressure, though, and it is probably not too important to get it into the absolute next version. -- Jeremiah Willcock