I'm looking for a convenient, free C++ library for graphs that include a solver for the maximum common subgraph (MCS) problem.

I'm aware of the Boost Graph Library and LEMON , but neither includes an MCS solver.


According to this ticket, Boost Graph Library added this feature around 3 years ago. The appropriate function (or set of functions) appears to be this function (mcgregor_common_subgraphs), which uses the McGregor algorithm.

  • $\begingroup$ I must have just missed it when browsing the TOC. I'll check it out and report back $\endgroup$ Feb 17 '12 at 22:34
  • $\begingroup$ It's pretty hard to find. I had to do a few Google searches to find it, and I think it'd be easy to miss when scanning the TOC, so no worries. $\endgroup$ Feb 17 '12 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.