Chemical Descriptors Library: MOS
Maximum common edge subgraph

The Maximum Common Edge Subgraph (MCES) algorithm is used in computational chemistry basically to stablish similarities between molecules.
To calculate the MCES is necessary to calculate the maximum clique (fully connected set) of a modular graph. The calculation of the maximum clique of a graph is known to be a NP-complete problem.
[Raymond, et.al.] showed that in chemistry, the problem can be drastically pruned with the use of heuristics.
The following heuristics published in [Raymond, et.al.] are implemented in CDL:

  1. Weak ring heuristic.
  2. Ring symmetry heuristic.

With these heuristics is still not guaranteed that the algorithm will find the optimal solution in a reasonable time.
CDL's implementation will terminate the calculation and return the maximum clique calculated by then when a maximum number of iterations is reached. This means that the solution given by the algorithm might not be the optimal.

Prototype 


  template <class Molecule, class HeuristicsFactory>
  std::list<Molecule>
  max_common_edge_sg(Molecule& m1, Molecule& m2, HeuristicsFactory heuristics_factory)

Arguments

ParameterDescriptionModels
m1
 		The first molecule morpho::cdl::molecule
m2
 		The second molecule morpho::cdl::molecule
heuristics_factory
 		Factory for the heuristic functors. The Factory has a member function called make_heuristics() which accepts the two molecules, the modular product graph, the two line graphs, and the two line graph mappings. Plase use : all_mos_heuristic_factory <---

The function returns a std::list of molecules that are the MCES of the two molecules.

Where Defined 

#include <morpho/cdl/bgl_expansions/algorithms/max_common_edge_subg.hpp>

Complexity

Pruned NP-complete

See also: 

  1. morpho/cdl/bgl_expansions/algorithms/max_common_edge_subg.hpp
  2. morpho/cdl/bgl_expansions/mos_heuristics/mos_heuristics.hpp
  3. morpho/cdl/bgl_expansions/algorithms/max_clique.hpp
  4. morpho/cdl/bgl_expansions/algorithms/line_graph.hpp
  5. morpho/cdl/bgl_expansions/algorithms/modular_product.hpp
  6. morpho/cdl/bgl_expansions/line_graph_labeling.hpp

References

  1. Raymond, J.; Gardiner, E.; Willett, P. "Heuristics for similarity searching of chemical graphs using a maximum common edge subgraph algorithm". J. Chem. Inf. Compuz. Sci. 2002. 42, 305-316
Copyright © Vladimir Josef Sykora 2003-2006