| Projected Molecule | |
Frequently, algorithms in graph theory are optimized for performance deleting
vertices and/or edges that are not relevant for the calculation itself. Moreover,
sometimes you are working with your molecule in the middle of a calculation of
some property that calls, as a mid-step, other algorithm that uses vertex/edge
deletion. Then you are faced with the question: if a pass the molecule as a
reference, is a cheap call to the algorithm, but then the molecule gets
modified, and I don't want this. Other solution would be to copy the molecule,
and then pass the copy to the algorithm. This won't be convenient, since the
copy of the molecule means the copy of all internal properties. If you're using
customized props, and the props are lightweight, then this won't be an inconvenient.
But when you're using default CDL props, or your own props which are heavy, this
will involve in some overhead.
For this cases, other object is provided, which has as its properties, pointers
to the properties of the molecule you are working on. Then the copy of the
molecule will involve copying just one pointer per property: one pointer per
atom and bond. When accessing a property of this 'projected molecule', then a
pointer derreferenciation will be involved.
This object behaves almost as a molecule: the only difference is
that it doesn't provide functions to add atoms and bonds, because where the
pointers are going to point to?
An example says more than thousend words.
Suppose we want to get the vertices of the smallest set of smallest subrings,
neatly organized in a vector of sets.
The SSSR algorithm of [Figueras] involves the deletion of vertices and edges. This
algorithm is provided by CDL, and is documented somewhere else.
Here goes >10E3 words:
template<class Molecule>
std::vector<std::set<size_t> >
get_sssr_vertices(const Molecule& m) {
// first some the objects needed to call the algorithm
std::vector<std::set<size_t> > cyclic_vertices;
typename MolProperty<cyclic_edgesS,Molecule>::result_type&
cyclic_edgs(MolProperty<cyclic_edgesS,Molecule>::get(m));
typename MolProperty<back_edgesS,Molecule>::result_type&
back_edges(MolProperty<back_edgesS,Molecule>::get(m));
// now the type we're interested in
projected_molecule<Molecule> proj_mol(m);
calculate_sssr(proj_mol,cyclic_vertices,cyclic_edgs,back_edges);
return cyclic_vertices;
}
 |
 |
 |