As a policy in CDL, all algorithms that do not involve a direct knowledge of
atom, bond or molecule properties are written accepting a graph object rather
than a molecule. In this way, the algorithms can be used for BGL in general,
not only for CDL. Even if the knowledge is needed, then the access to the
properties is parametrized somehow to hide CDL's implementation.
Ullmann's algorithm for subgraph isomorphism is an example of this case.
Subgraph isomorphism testing is a commom task in computational chemistry. The
basic task in this field is the substructure search.
The algorithm prunes the search using labels for vertices and edges. For chemical
graph this labels come from the properties of the molecule. Then, the labels are
user defined predicates that accepts vertices/edges of two graphs: the subgraph and
the graph that is being tested for isomorphism. As simple as that. If you want
to search substructures taking chirality into account, then you provide a predicate
that accepts a vertex descriptor from the graph, and one from the subgraph,
and returns true if the atoms are the same element, and have the same chirality.
Same semantics for the edge labeling.
]. Where
n are the number of nodes.
In chemistry, this complexity is largely pruned.
Example
Lest consider we want to search for a substructure considering the bond types:
#include <morpho/cdl/molecule/molecule.hpp>
#include <morpho/cdl/bgl_expansions/algorithms/ullmann.hpp>
#include <vector>
#include <algorithm>
#include <iterator>
// define the atom labeling :
template <class Molecule>
struct atom_labeling {
atom_labeling(const Molecule& subgraph, const Molecule& graph) :
m_subgraph_mol(subgraph), m_graph_mol(graph) {}
bool operator() (typename Molecule::vertex_descriptor v1,
typename Molecule::vertex_descriptor v2) {
const bool rvo(AtomProperty<atomic_numberS,typename Molecule::atom_type>::get(m_subgraph_mol.get_atom(v1))
== AtomProperty<atomic_numberS,typename Molecule::atom_type>::get(m_graph_mol.get_atom(v2)));
return rvo;
}
private :
const Molecule& m_subgraph_mol;
const Molecule& m_graph_mol;
};
// define the edge labeling
template <class Molecule>
struct bond_labeling {
bond_labeling(const Molecule& subgraph, const Molecule& graph) :
m_subgraph_mol(subgraph), m_graph_mol(graph) {}
bool inline operator() (typename Molecule::edge_descriptor e1,
typename Molecule::edge_descriptor e2) {
const bool rvo(BondProperty<type_of_bondS,typename Molecule::bond_type>::get(m_subgraph_mol.get_bond(e1))
== BondProperty<type_of_bondS,typename Molecule::bond_type>::get(m_graph_mol.get_bond(e2)));
return rvo;
}
private :
const Molecule& m_subgraph_mol;
const Molecule& m_graph_mol;
};
int main() {
typedef molecule M;
nail_juice<M> j1, j2;
get_juice_from_stream(std::cin,j1,0,smile_formatT());
get_juice_from_stream(std::cin,j2,1,smile_formatT());
M m1(j1), m2(j2);
// the labels:
atom_labeling<M> alabel(m1.get_graph(), m2.get_graph());
bond_labeling<M> blabel(m1.get_graph(), m2.get_graph());
// get the first mapping :
std::vector<std::pair<size_t,size_t> > mapping;
ullmann(m1.get_graph(), m2.get_graph(), alabel, blabel, mapping);
std::cout << "The mapped vertices : \n";
std::copy(mapping.begin(),mapping.end(), std::ostream_iterator<size_t>(std::cout, " "));
return 0;
}
Copyright © Vladimir Josef Sykora & Morphochem AG 2003
Copyright © Vladimir Josef Sykora 2003-2006