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,] showed that in chemistry, the problem can be drastically pruned with the use of heuristics.
The following heuristics published in [Raymond,] 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.


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


The first molecule morpho::cdl::molecule
The second molecule morpho::cdl::molecule
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>


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


  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