Boost C++ Libraries: Ticket #6780: [BGL] add Maximum Adjacency Search

attachment set

fvilas@… — Wed, 11 Apr 2012 02:14:53 GMT

attachment → max_adj_search_v3.patch.gz

component changed; owner set

viboes — Mon, 28 May 2012 17:19:42 GMT

owner set to Jeremiah Willcock
component None → graph

fvilas@… — Mon, 28 May 2012 18:42:38 GMT

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 — Mon, 28 May 2012 18:54:51 GMT

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@… — Mon, 28 May 2012 19:45:09 GMT

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?

attachment set

fvilas@… — Tue, 21 Aug 2012 03:09:26 GMT

attachment → max_adj_search_v4.patch.gz

Updated against 1.51.0

fvilas@… — Tue, 21 Aug 2012 03:13:04 GMT

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 — Tue, 21 Aug 2012 17:45:11 GMT

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@… — Sat, 25 Aug 2012 12:32:43 GMT

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.

attachment set

fvilas — Tue, 02 Oct 2012 02:27:45 GMT

attachment → max_adj_search_v5.patch.gz

fvilas@… — Tue, 02 Oct 2012 02:29:30 GMT

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@… — Tue, 27 Nov 2012 03:04:49 GMT

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

Jeremiah Willcock — Mon, 03 Dec 2012 15:20:10 GMT

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

attachment set

Jeremiah Willcock — Mon, 03 Dec 2012 15:20:39 GMT

attachment → max_adj_search_v6.patch

fvilas@… — Fri, 07 Dec 2012 22:38:21 GMT

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.

attachment set

fvilas@… — Fri, 07 Dec 2012 22:38:45 GMT

attachment → max_adj_search_v7.patch

attachment set

Jeremiah Willcock — Sat, 08 Dec 2012 02:25:06 GMT

attachment → mas_test_errors.txt

Errors from testing with patch applied

Jeremiah Willcock — Sat, 08 Dec 2012 02:25:40 GMT

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

fvilas@… — Sat, 08 Dec 2012 04:30:17 GMT

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.

attachment set

fvilas@… — Sun, 06 Jan 2013 01:12:51 GMT

attachment → max_adj_search_v8.patch

Updated patch

fvilas@… — Sun, 06 Jan 2013 01:13:42 GMT

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.

attachment set

fvilas@… — Sun, 24 Feb 2013 03:12:38 GMT

attachment → max_adj_search_v9.patch

Updated documentation

status changed; resolution set

Jeremiah Willcock — Tue, 12 Mar 2013 00:35:52 GMT

status new → closed
resolution → fixed

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