Re: [Boost-users] [Graph] Maximum common subgraph

From: Andreas Sæbjørnsen (andreas.saebjoernsen_at_[hidden])
Date: 2006-01-06 17:31:06

Thank you very much. The project looks really good and I hope that we can
use this in our project. We will try to apply it in the context of complex
graphs of static data structures found in code of programs and dynamic data
structures found in the heap of a running program.

Best,
Andreas Saebjoernsen

On 1/5/06, Grégoire Dooms <dooms_at_[hidden]> wrote:
>
> Andreas Sæbjørnsen a écrit :
>
> >Hi,
> >Lately I have been looking for a good C/C++ implementation of an
> algorithm
> >for finding the maximum common subgraph in Boost::Graph. The algorithms I
> >have looked for is mainly  Bron-Kerbosch and the MCS  algorithm, but I am
> >very open for alternatives.
> >
> An alternative is constraint programming.
> The following papers describe a constraint programming approach to
> multiple graph matching problems such as isomorphism, subgraph
> isomorphism, mcs and approximate subgraph matching.
>
> This paper describes the algorithms in details and show how it allows to
> solve more instances than the vflib implementation:
>
> http://www.info.ucl.ac.be/~sz/DeclarativeApproximateGraphMatchingUsingAConstraintApproach.pdf
>
> This one describes how MCS and the different graph matching problems are
> done using this technique:
> http://www.info.ucl.ac.be/~dooms/bfd05.pdf
>
> You can find an implementation which uses Boost::Graph and the Gecode
> constraint programming library ( http://www.gecode.org/ ) at:
> http://cpgraph.info.ucl.ac.be/
> it is released under a BSD license.
> Don't hesitate to contact us would you need any further info.
>
> Best,
> --
> Grégoire Dooms
>
>
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>