|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:
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> std::list<Molecule> 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.