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.


1 Answer 1


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$ Commented Feb 17, 2012 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$ Commented Feb 17, 2012 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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