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

From: Grégoire Dooms (dooms_at_[hidden])
Date: 2006-01-05 03:59:56

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