[BGL] add Maximum Adjacency Search

[fvilas@…]

Currently, the maximum adjacency search (MAS) algorithm is embedded as a phase of the Stoer-Wagner min-cut algorithm. This patch promotes it to be a public search algorithm with a visitor concept similar to BFS or DFS. The existing Stoer-Wagner implementation is modified to use the MAS. The patch also includes HTML documentation of MAS.

[fvilas@…]

It would be nice to target 1.51, but if it has to slip, that is fine too. Let me know what changes I should make to get it accepted.

[Jeremiah Willcock]

Do you think it's worthwhile to change Stoer-Wagner to use your new code? I didn't see that in your patch. Also, do you have documentation for the new code?

[fvilas@…]

I thought I covered both of those.

$ zcat max_adj_search_v3.patch.gz | grep +++

+++ boost/graph/stoer_wagner_min_cut.hpp (working copy)

+++ boost/graph/maximum_adjacency_search.hpp (working copy)

+++ libs/graph/doc/maximum_adjacency_search.html (working copy)

Did I miss something?

[fvilas@…]

Updated against 1.51.0

[fvilas@…]

Updated patch to new release. Patch includes new algorithm as boost/graph/maximum_adjacency_search.hpp, changes to boost/graph/stoer_wagner_min_cut.hpp to use the new algorithm, and documentation of the algorithm as libs/graph/doc/maximum_adjacency_search.html

Since this is the same day as the release announcement for 1.51.0, what else is needed for the merge window for 1.52.0?

[Jeremiah Willcock]

Here are my comments:

• What is the reason for having mas_visitor_event_not_overridden rather than just using void for the default return value?

• Where does unsigned long come from in the return type of maximum_adjacency_search? Should there be some type obtained from a traits class used there instead?

• Please have a version of any named-parameter function in the namespace boost::graph that uses Boost.Parameter, then have the old-style named parameter version just forward to it (look at <boost/graph/isomorphism.hpp> for a simple example).

• Please try to avoid using Boost.Typeof (including the BOOST_AUTO macro) since some compilers that can otherwise compile Boost.Graph have trouble with it.

• What is the reason for copying the priority queue on entry to stoer_wagner_min_cut rather than passing in a reference like before?

Other than these issues, I think it's basically ready to put in, and it should make it into 1.52. Thank you for your contribution, and sorry for the delayed responses.

[fvilas@…]

Thanks for the help. I will work on addressing these.

The mas_visitor_event_not_overridden was a copy/paste from breadth_first_search.hpp. I can change the values to void, but I thought there was a reason for it in the BFS code, so I used that example.

The unsigned long will be converted to the key_type of the priority queue.

isomorphism.hpp has a few new named parameter macros that I was unfamiliar with, but it should clean up the code, so I will try that.

It looks like the BOOST_AUTO macro is only used in the examine_edge() routine in the Stoer-Wagner visitor to get the weight map type. I was unaware that the macro caused some issues, so I will get that fixed.

The conversion to pass-by-value happened when chasing down some "reference of reference" bugs. I forgot to put it back. I just fixed that and the code seems to compile and run fine.

It may take me a bit to get this list implemented, especially getting more familiar with the named parameters macros. I will put up a v5 of the patch as soon as I have something, so we can keep things moving. Thanks again for the feedback.

[fvilas@…]

I finally managed to get through the distractions of the day job and school to update this. It looks like I missed the new features window for 1.52.0, but if it is ready, we can target 1.53.0. Thoughts?

[fvilas@…]

Is this patch in good shape for the merge window? What else do I need to tackle?

[Jeremiah Willcock]

Here's my updated version of the patch (most stylistic things). It does not pass the Stoer-Wagner tests in the Boost trunk, however.

[fvilas@…]

I incorporated your changes and added the include for one_bit_color_map.hpp. Then I made this patch, got a clean copy of the code from SVN and applied the patch to the new code. The normal "boostrap.sh ; b2 ; cd libs/graph/example ; ../../../b2" seemed to work. I ran the resulting code for Stoer-Wagner and it worked. This was using GCC 4.7.1 with the default settings from bjam.

I have thought about changing the graph used in the test case to match the picture in the documentation, but the result should still be correct for the graph tested.

[Jeremiah Willcock]

Errors from testing with patch applied

[Jeremiah Willcock]

I have attached the errors that I get from testing the latest version of the patch.

[fvilas@…]

I missed the test directory instead of the example directory. Now that I am able to duplicate the error, it looks like I have a task for the weekend... I will upload the fix as soon as I have it. Thanks for your help.

[fvilas@…]

Updated patch

[fvilas@…]

New patch... Added mas_test.cpp test harness. Added dispatch based on weight_map, if not provided, then edge_weight is required. Return value changed to void, and the tuple previously returned can be retrieved through a visitor, shown in the test harness. Docs updated to reflect the return value change. More fixes in general, all around. This took a few weekends, as opposed to the one I expected.

Let me know if there is anything else needed.

[fvilas@…]

Updated documentation

[Jeremiah Willcock]

(In [83410]) Added maximum adjacency search from Fernando Vilas; fixes #6780