Changeset 1c0b0b

Timestamp:

Oct 23, 2022, 9:08:55 AM (3 years ago)

Author:

Frederik Heber <frederik.heber@…>

Branches:

Candidate_v1.7.0, stable

Children:

894040

Parents:

0daef6

git-author:

Frederik Heber <frederik.heber@…> (10/19/22 19:38:02)

git-committer:

Frederik Heber <frederik.heber@…> (10/23/22 09:08:55)

Message:

Graph6Writer::write_elementlist uses BFS from boundary atom.

• the elementlist is not stable as the set of atoms is arbitrary to any kind of permutation. However, the underlying bond graph is not, even though it may also have some symmetries.
• Therefore, we use a BFS from a non-hydrogen atom on the boundary.
• FIX: BoosGraphCreator gets vector of const atom*.

Location:

src/Graph

Files:

• BoostGraphCreator.cpp (modified) (2 diffs)
• BoostGraphCreator.hpp (modified) (1 diff)
• Graph6Writer.cpp (modified) (2 diffs)
• Graph6Writer.hpp (modified) (2 diffs)
• unittests/BoostGraphCreatorUnitTest.cpp (modified) (1 diff)

src/Graph/BoostGraphCreator.cpp

@@ -75 +75 @@
 
 void BoostGraphCreator::createFromAtoms(
-    const std::vector<atom *> &_atoms,
+    const std::vector<const atom *> &_atoms,
     const predicate_t &_pred)
 {
@@ -88 +88 @@
   std::sort(atomids.begin(), atomids.end());
   const predicate_t predicate = boost::bind(inSetPredicate, boost::ref(atomids), _1);
-  createFromRange<std::vector<atom *>::const_iterator>(
-      const_cast<const std::vector<atom *> &>(_atoms).begin(),
-      const_cast<const std::vector<atom *> &>(_atoms).end(),
+  createFromRange<std::vector<const atom *>::const_iterator>(
+      const_cast<const std::vector<const atom *> &>(_atoms).begin(),
+      const_cast<const std::vector<const atom *> &>(_atoms).end(),
       _atoms.size(),
       boost::bind(predicateAnd, _pred, predicate, _1));

src/Graph/BoostGraphCreator.hpp

@@ -87 +87 @@
    */
   void createFromAtoms(
-      const std::vector<atom *> &_atoms,
+      const std::vector<const atom *> &_atoms,
       const predicate_t &_pred);
 

src/Graph/Graph6Writer.cpp

@@ -44 +44 @@
 
 #include "Atom/atom.hpp"
+#include "Descriptors/AtomIdDescriptor.hpp"
 #include "Element/element.hpp"
+#include "Graph/BoostGraphCreator.hpp"
+#include "Graph/BreadthFirstSearchGatherer.hpp"
+#include "World.hpp"
 
 //#include "CodePatterns/MemDebug.hpp"
@@ -116 +120 @@
   ASSERT( value==0,
       "Graph6Writer::write_graph6() - byte is not null, i.e. chars left to write?");
-  ASSERT( bytes_written == (int)ceil(n*(n-1)/12.0f),
+  ASSERT( bytes_written == (unsigned int)ceil(n*(n-1)/12.0f),
       "Graph6Writer::write_graph6() - unexpected number of bytes written");
 }
 
+/**
+ * Picks a non-hydrogen from all hydrogen atoms in the current set
+ * of atoms.
+ *
+ * Returns -1 if none could be found.
+ */
+atomId_t Graph6Writer::getBoundaryNonHydrogen() const {
+  atomId_t start_atom_id = -1;
+  int bond_degree = 16;
+  for(std::vector<const atom *>::const_iterator iter = _atoms.begin();
+      iter != _atoms.end(); ++iter) {
+    const atom *walker = *iter;
+    if (walker->getElement().getSymbol() == "H") {
+      const BondList& bond_list = walker->getListOfBonds();
+      assert(bond_list.size() == 1);
+      const atom *other = bond_list.front().get()->GetOtherAtom(walker);
+      const int number_of_bonds = other->getListOfBonds().size();
+      if ((other->getElement().getSymbol() != "H") && (bond_degree > number_of_bonds)) {
+        start_atom_id = other->getId();
+        bond_degree = number_of_bonds;
+      }
+    }
+  }
+  return start_atom_id;
+}
+
+bool OnlyNonHydrogens(const bond &_bond) {
+  return _bond.HydrogenBond == 0;
+}
+
 void Graph6Writer::write_elementlist(std::ostream& out) {
-  for (std::vector<const atom *>::const_iterator iter = _atoms.begin();
-      iter != _atoms.end(); ++iter) {
-    if (iter != _atoms.begin())
+  /** Execute a Breadth-First Search discovery from one terminal atom (e.g.,
+   * pick random hydrogen and then it's bond-neighbor if it is non-hydrogen).
+   * Then return the element list in that ordering.
+   *
+   * The graph6 string does not account for the inherent graph symmetries
+   * (e.g., BW having 123<->321 but not 123<->132 symmetry).
+   */
+  // pick bond neighbor of a hydrogen atom
+  atomId_t start_atom_id = getBoundaryNonHydrogen();
+  if (start_atom_id == (unsigned int)-1) {
+    // fall back to first atom in list
+    start_atom_id = _atoms.front()->getId();
+  }
+
+  // do an unlimited BFS and get set of nodes, ordered by discovery level
+  BoostGraphCreator graphCreator;
+  graphCreator.createFromAtoms(_atoms, OnlyNonHydrogens);
+  BreadthFirstSearchGatherer gatherer(graphCreator);
+  const std::vector<atomId_t> gathered_atoms = gatherer(start_atom_id);
+
+  // print all nodes
+  const World& world = World::getConstInstance();
+  for (std::vector<atomId_t>::const_iterator iter = gathered_atoms.begin();
+      iter != gathered_atoms.end(); ++iter) {
+    if (iter != gathered_atoms.begin())
       out << ' ';
-    out << (*iter)->getElement().getSymbol();
+    const atom* walker = world.getAtom(AtomById(*iter));
+    assert(walker != NULL);
+    out << walker->getElement().getSymbol();
   }
 }

src/Graph/Graph6Writer.hpp

@@ -17 +17 @@
 #include <iosfwd>
 #include <vector>
+
+#include "types.hpp"
 
 class atom;
@@ -41 +43 @@
 
    void write_elementlist(std::ostream& out);
+
+private:
+   atomId_t getBoundaryNonHydrogen() const;
 };
 

src/Graph/unittests/BoostGraphCreatorUnitTest.cpp

@@ -164 +164 @@
 void BoostGraphCreatorTest::createFromAtomsTest()
 {
-  std::vector<atom *> atoms;
+  std::vector<const atom *> atoms;
   std::copy(TestMolecule->begin(), TestMolecule->end(), std::back_inserter(atoms));
   BGCreator->createFromAtoms(atoms, BreadthFirstSearchGatherer::AlwaysTruePredicate);