Ticket #6780 (closed Patches: fixed)

Opened 2 years ago

Last modified 13 months ago

[BGL] add Maximum Adjacency Search

Reported by: fvilas@… Owned by: jewillco
Milestone: To Be Determined Component: graph
Version: Boost 1.48.0 Severity: Problem
Keywords: BGL Maximum Adjacency Search Cc:


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.


max_adj_search_v3.patch.gz Download (8.2 KB) - added by fvilas@… 2 years ago.
max_adj_search_v4.patch.gz Download (8.0 KB) - added by fvilas@… 20 months ago.
Updated against 1.51.0
max_adj_search_v5.patch.gz Download (8.7 KB) - added by fvilas 19 months ago.
max_adj_search_v6.patch Download (37.7 KB) - added by jewillco 17 months ago.
max_adj_search_v7.patch Download (37.7 KB) - added by fvilas@… 17 months ago.
mas_test_errors.txt Download (65.1 KB) - added by jewillco 17 months ago.
Errors from testing with patch applied
max_adj_search_v8.patch Download (51.1 KB) - added by fvilas@… 16 months ago.
Updated patch
max_adj_search_v9.patch Download (51.3 KB) - added by fvilas@… 14 months ago.
Updated documentation

Change History

Changed 2 years ago by fvilas@…

comment:1 Changed 23 months ago by viboes

  • Owner set to jewillco
  • Component changed from None to graph

comment:2 Changed 23 months ago by 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.

comment:3 Changed 23 months ago by jewillco

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?

comment:4 Changed 23 months ago by 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?

Changed 20 months ago by fvilas@…

Updated against 1.51.0

comment:5 Changed 20 months ago by 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?

comment:6 Changed 20 months ago by jewillco

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.

comment:7 Changed 20 months ago by 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.

Changed 19 months ago by fvilas

comment:8 Changed 19 months ago by 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?

comment:9 Changed 17 months ago by fvilas@…

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

comment:10 Changed 17 months ago by jewillco

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

Changed 17 months ago by jewillco

comment:11 Changed 17 months ago by 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 " ; 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.

Changed 17 months ago by fvilas@…

Changed 17 months ago by jewillco

Errors from testing with patch applied

comment:12 Changed 17 months ago by jewillco

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

comment:13 Changed 17 months ago by 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.

Changed 16 months ago by fvilas@…

Updated patch

comment:14 Changed 16 months ago by 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.

Changed 14 months ago by fvilas@…

Updated documentation

comment:15 Changed 13 months ago by jewillco

  • Status changed from new to closed
  • Resolution set to fixed

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


Add a comment

Modify Ticket

Change Properties
<Author field>
as closed
The resolution will be deleted. Next status will be 'reopened'

E-mail address and user name can be saved in the Preferences.

Note: See TracTickets for help on using tickets.