Modify

Ticket #6780 (closed Patches: fixed)

Opened 3 years ago

Last modified 2 years 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:

Description

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.

Attachments

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

Change History

Changed 3 years ago by fvilas@…

comment:1 Changed 3 years ago by viboes

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

comment:2 Changed 3 years 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 3 years 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 3 years 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 3 years ago by fvilas@…

Updated against 1.51.0

comment:5 Changed 3 years 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 3 years 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 3 years 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 3 years ago by fvilas

comment:8 Changed 3 years 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 3 years ago by fvilas@…

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

comment:10 Changed 3 years 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 3 years ago by jewillco

comment:11 Changed 3 years 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 "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.

Changed 3 years ago by fvilas@…

Changed 3 years ago by jewillco

Errors from testing with patch applied

comment:12 Changed 3 years ago by jewillco

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

comment:13 Changed 3 years 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 3 years ago by fvilas@…

Updated patch

comment:14 Changed 3 years 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 3 years ago by fvilas@…

Updated documentation

comment:15 Changed 2 years ago by jewillco

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

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

View

Add a comment

Modify Ticket

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


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

 
Note: See TracTickets for help on using tickets.