Molassembler  3.0.0
Molecule graph and conformer library
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
RankingTree.h
Go to the documentation of this file.
1 
31 #ifndef INCLUDE_MOLASSEMBLER_RANKING_HIERARCHICAL_TREE_H
32 #define INCLUDE_MOLASSEMBLER_RANKING_HIERARCHICAL_TREE_H
33 
34 #include "boost/variant.hpp"
35 
40 #include "Molassembler/Log.h"
41 #include "Molassembler/Molecule.h"
43 
45 
46 using namespace std::string_literals;
47 
48 namespace Scine {
49 namespace Molassembler {
50 
62 class RankingTree {
63 private:
67  static unsigned debugMessageCounter_;
68 
72  static std::string adaptMolGraph_(std::string molGraph);
73 
75  static void writeGraphvizFiles_(
76  const std::vector<std::string>& graphvizStrings
77  );
78 
79 public:
82 
89  enum class ExpansionOption {
91  OnlyRequiredBranches,
93  Full
94  };
95 
97  struct VertexData {
102 
104  boost::optional<AtomStereopermutator> stereopermutatorOption;
105 
106  // This is the place for eventual atomic number deviations
107  // boost::optional<double> deviantAtomicNumber;
108  };
109 
111  struct EdgeData {
112  boost::optional<BondStereopermutator> stereopermutatorOption;
113  };
114 
116  using BglType = boost::adjacency_list<
117  /* OutEdgeListS = Type of Container for edges of a vertex
118  * Options: vector, list, slist, set, multiset, unordered_set
119  * Choice: setS
120  */
121  boost::setS,
122  /* VertexListS = Type of Container for vertices
123  * Options: vector, list, slist, set, multiset, unordered_set
124  * Choice: vecS, removing vertices does not occur
125  */
126  boost::vecS,
127  /* DirectedS = Is the graph directed or not?
128  * Choice: Bidirectional. Although a tree is merely directional, and not
129  * bi-directional, we nevertheless also need fast access to in_edges, so
130  * we choose bidirectional
131  */
132  boost::bidirectionalS,
133  // VertexProperty = What information is stored about vertices?
134  VertexData,
135  // EdgeProperty = What information is stored about edges?
136  EdgeData
137  >;
138 
139  // IUPAC Sequence rule one tree vertex comparator
140  class SequenceRuleOneVertexComparator;
141 
142  // IUPAC Sequence rule two tree vertex comparator
143  class SequenceRuleTwoVertexComparator;
144 
145  // IUPAC Sequence rule three tree edge comparator
146  class SequenceRuleThreeEdgeComparator;
147 
148  // IUPAC Sequence rule four tree vertex and edge mixed comparator
149  class SequenceRuleFourVariantComparator;
150 
151  // IUPAC Sequence rule five tree vertex and edge mixed comparator
152  class SequenceRuleFiveVariantComparator;
153 
154  // Returns whether the vertex or edge has an instantiated Stereopermutator
155  class VariantHasInstantiatedStereopermutator;
156 
157  // Returns the mixed depth (see mixedDepth_ functions) of the vertex or edge
158  class VariantDepth;
159 
160  // Returns the source node of a vertex (identity) or an edge (source node)
161  class VariantSourceNode;
162 
163  // Returns a string representation of the stereopermutator on vertex or edge
164  class VariantStereopermutatorStringRepresentation;
165 
166  /*
167  * Returns whether two variants' stereopermutators form a like pair or not
168  * according to the sub-rules in IUPAC sequence rule four.
169  */
170  class VariantLikePair;
171 
173  class GraphvizWriter;
175 
176 private:
178  using TreeVertexIndex = BglType::vertex_descriptor;
180  using TreeEdgeIndex = BglType::edge_descriptor;
182  using VariantType = boost::variant<TreeVertexIndex, TreeEdgeIndex>;
183 
185  struct JunctionInfo {
186  TreeVertexIndex junction;
187 
188  std::vector<TreeVertexIndex> firstPath, secondPath;
189  };
190 
192  static constexpr TreeVertexIndex rootIndex = 0;
193 
194 /* State */
197 
200 
201  // Closures
202  const Graph& graph_;
203  const StereopermutatorList& stereopermutatorsRef_;
204  const std::string adaptedMolGraphviz_;
205 
206 /* Minor helper classes and functions */
208  TreeVertexIndex parent_(const TreeVertexIndex& index) const;
209 
211  std::vector<TreeVertexIndex> adjacents_(TreeVertexIndex index) const;
212 
214  unsigned adjacentTerminalHydrogens_(const TreeVertexIndex& index) const;
215 
217  bool isBondSplitDuplicateVertex_(const TreeVertexIndex& index) const;
218 
220  bool isCycleClosureDuplicateVertex_(const TreeVertexIndex& index) const;
221 
227  std::vector<TreeVertexIndex> auxiliaryAdjacentsToRank_(
228  TreeVertexIndex sourceIndex,
229  const std::vector<TreeVertexIndex>& excludeIndices
230  ) const;
231 
233  template<typename ComparisonSets>
234  bool notEmpty_(const ComparisonSets& comparisonSets) const {
235  return Temple::all_of(
236  comparisonSets,
237  [](const auto& mapPair) -> bool {
238  return !mapPair.second.empty();
239  }
240  );
241  }
242 
247  unsigned nonDuplicateDegree_(const TreeVertexIndex& index) const;
248 
256  std::vector<TreeVertexIndex> addBondOrderDuplicates_(
257  const TreeVertexIndex& treeSource,
258  const TreeVertexIndex& treeTarget
259  );
260 
262  std::unordered_set<TreeVertexIndex> treeIndicesInBranch_(TreeVertexIndex index) const;
263 
265  std::unordered_set<AtomIndex> molIndicesInBranch_(TreeVertexIndex index) const;
266 
268  unsigned duplicateDepth_(TreeVertexIndex index) const;
269 
271  unsigned depthOfNode_(TreeVertexIndex index) const;
272 
274  unsigned mixedDepth_(const TreeVertexIndex& vertexIndex) const;
275 
277  unsigned mixedDepth_(const TreeEdgeIndex& edgeIndex) const;
278 
283  JunctionInfo junction_(const TreeVertexIndex& a, const TreeVertexIndex& b) const;
284 
286  bool molIndexExistsInBranch_(
287  AtomIndex molIndex,
288  TreeVertexIndex treeIndex
289  ) const;
290 
291 /* Major helper functions */
300  std::vector<TreeVertexIndex> expand_(
301  const TreeVertexIndex& index,
302  const std::unordered_set<AtomIndex>& molIndicesInBranch
303  );
304 
310  template<typename SetValueType, typename ComparatorType>
312  const std::multiset<SetValueType, ComparatorType>& a,
313  const std::multiset<SetValueType, ComparatorType>& b
314  ) const {
315  return std::lexicographical_compare(
316  std::begin(a),
317  std::end(a),
318  std::begin(b),
319  std::end(b),
320  ComparatorType {*this}
321  );
322  }
323 
352  template<typename SetValueType, typename ComparatorType>
354  const std::map<
356  std::multiset<SetValueType, ComparatorType>
357  >& comparisonSets,
358  const std::vector<
359  std::vector<TreeVertexIndex>
360  >& undecidedSets,
362  ) const {
363  for(const auto& undecidedSet : undecidedSets) {
365  Temple::Adaptors::allPairs(undecidedSet),
366  [&](const TreeVertexIndex a, const TreeVertexIndex b) {
367  if(multisetCompare_(comparisonSets.at(a), comparisonSets.at(b))) {
368  orderingHelper.addLessThanRelationship(a, b);
369  } else if(multisetCompare_(comparisonSets.at(b), comparisonSets.at(a))) {
370  orderingHelper.addLessThanRelationship(b, a);
371  }
372  }
373  );
374  }
375  }
376 
377  static std::string toString(TreeVertexIndex vertex);
378  std::string toString(const TreeEdgeIndex& edge) const;
379  std::string toString(const VariantType& vertexOrEdge) const;
380 
408  template<
409  unsigned ruleNumber,
410  bool bfsDownOnly,
411  bool insertEdges,
412  bool insertVertices,
413  typename MultisetValueType,
414  typename MultisetComparatorType
415  > void runBFS_(
416  TreeVertexIndex sourceIndex,
418  const boost::optional<unsigned>& depthLimitOptional = boost::none
419  ) const {
420  /* Static safety checks */
421  static_assert(
422  insertEdges || insertVertices,
423  "During BFS, you must insert either edges, vertices, or both into the "
424  " comparison sets, but definitely not neither"
425  );
426 
427  static_assert(
428  (
429  insertEdges
430  && !std::is_same<MultisetValueType, TreeVertexIndex>::value
431  ) || (
432  insertVertices
433  && !std::is_same<MultisetValueType, TreeEdgeIndex>::value
434  ),
435  "Multiset value type and insert booleans are mismatched"
436  );
437 
438  // Check if depthLimit prohibits first comparison too
439  if(depthLimitOptional.value_or(std::numeric_limits<unsigned>::max()) == 0) {
440  return;
441  }
442 
443  /* Declarations */
444 
445  /* For each branch to compare, keep a multiset of all the encountered
446  * indices in the branch. The multiset keeps a descending order of the
447  * indices according to sequence rule 1 and can be lexicographically
448  * compared against one another using the SequenceRuleOneVertexComparator
449  *
450  * NOTE: Do not use operator [] to access members in comparisonSets. This
451  * old form of accessible and assignable proxy object forces a
452  * default-instantiation of the Comparator, which the
453  * MultisetComparatorTypes cannot do. Always use .at().
454  */
455  std::map<
457  std::multiset<MultisetValueType, MultisetComparatorType>
458  > comparisonSets;
459 
460  /* For each branch to compare, keep a set of seed indices to follow in an
461  * iteration. These are expanded in each iteration as long as the branch
462  * they contain remains relevant (i.e. its relation to the other branches
463  * is still unclear): They themselves are placed in the comparisonSet,
464  * while their respective adjacents are the new seeds for the next
465  * iteration.
466  */
467  std::map<
468  TreeVertexIndex,
469  std::vector<TreeVertexIndex>
470  > seeds;
471 
472  /* In case the BFS in not down-only, we have to track which indices we
473  * have visited to ensure BFS doesn't backtrack or reuse vertices.
474  */
475  std::unordered_set<TreeVertexIndex> visitedVertices;
476 
477 
478  /* Initialization */
479  if(!bfsDownOnly) { // Initialization is only necessary in this case
480  visitedVertices.insert(sourceIndex);
481  }
482 
483  auto undecidedSets = orderingHelper.getUndecidedSets();
484 
485  for(const auto& undecidedSet : undecidedSets) {
486  for(const auto& undecidedBranch : undecidedSet) {
487  comparisonSets.emplace(
488  undecidedBranch,
489  *this
490  );
491 
492  if constexpr(insertVertices) {
493  comparisonSets.at(undecidedBranch).insert(undecidedBranch);
494  }
495 
496  if constexpr(insertEdges) {
497  if(bfsDownOnly) {
498  const auto edge = boost::edge(sourceIndex, undecidedBranch, tree_).first;
499  comparisonSets.at(undecidedBranch).insert(edge);
500  } else {
501  // Need to be direction-agnostic
502  auto forwardEdge = boost::edge(sourceIndex, undecidedBranch, tree_);
503  auto backwardEdge = boost::edge(undecidedBranch, sourceIndex, tree_);
504 
505  const auto edge = forwardEdge.second ? forwardEdge.first : backwardEdge.first;
506  comparisonSets.at(undecidedBranch).insert(edge);
507  }
508  }
509 
510  seeds[undecidedBranch] = {undecidedBranch};
511  }
512  }
513 
514  // Compare undecided multisets, and add any discoveries to the ordering helper
515  compareBFSSets_(comparisonSets, undecidedSets, orderingHelper);
516 
517  // Update the undecided sets
518  undecidedSets = orderingHelper.getUndecidedSets();
519 
520  if constexpr (buildTypeIsDebug) {
521  // Write debug graph files if the corresponding log particular is set
522  if(
523  Log::particulars.count(Log::Particulars::RankingTreeDebugInfo) > 0
524  && notEmpty_(comparisonSets)
525  ) {
526  std::string header = (
527  (
528  bfsDownOnly
529  ? ""s
530  : "aux "s
531  ) + "R"s + std::to_string(ruleNumber)
532  );
533 
534  writeGraphvizFiles_({
535  adaptedMolGraphviz_,
536  dumpGraphviz(
537  header,
538  {sourceIndex},
539  collectSeeds_(seeds, undecidedSets)
540  ),
541  makeBFSStateGraph_(
542  header,
543  sourceIndex,
544  comparisonSets,
545  undecidedSets
546  ),
547  orderingHelper.dumpGraphviz()
548  });
549  }
550  }
551 
552  unsigned depth = 1;
553 
554  /* Loop BFS */
555 
556  /* As long as there are undecided sets and seeds whose expansion could be
557  * relevant for those undecided sets, continue BFS
558  */
559  while(
560  // Undecided indices remain
561  !undecidedSets.empty()
562  // Seeds exist that are relevant to the undecided sets
563  && relevantSeeds_(seeds, undecidedSets)
564  && depth < depthLimitOptional.value_or(std::numeric_limits<unsigned>::max())
565  ) {
566  // BFS Step
567  for(const auto& undecidedSet: undecidedSets) {
568  for(const auto& undecidedBranch: undecidedSet) {
569  /* Clear the comparison set at undecided branches prior to inserting
570  * anything. This doesn't change anything semantically, since
571  * everything from the prior iteration (or initialization) must have
572  * compared equal within this undecidedSet.
573  *
574  * Makes for cleaner visualization and reduces the number of
575  * Comparator calls during insert and lexicographical_compare.
576  */
577  comparisonSets.at(undecidedBranch).clear();
578 
579  std::vector<TreeVertexIndex> newSeeds;
580 
581  for(const auto& seed : seeds.at(undecidedBranch)) {
582 
583  if(!bfsDownOnly) {
584  // Mark as visited
585  visitedVertices.insert(seed);
586 
587  // In-edges are only relevant for omnidirectional BFS
588  for(
589  auto inIterPair = boost::in_edges(seed, tree_);
590  inIterPair.first != inIterPair.second;
591  ++inIterPair.first
592  ) {
593  const auto& inEdge = *inIterPair.first;
594 
595  auto edgeSource = boost::source(inEdge, tree_);
596 
597  // Check if already placed
598  if(visitedVertices.count(edgeSource) == 0) {
599  if constexpr(insertVertices) {
600  comparisonSets.at(undecidedBranch).insert(edgeSource);
601  }
602 
603  if constexpr(insertEdges) {
604  comparisonSets.at(undecidedBranch).insert(inEdge);
605  }
606 
607  newSeeds.push_back(edgeSource);
608  }
609  }
610  }
611 
612  // Out edges are considered in all cases
613  for( // Out-edges
614  auto outIterPair = boost::out_edges(seed, tree_);
615  outIterPair.first != outIterPair.second;
616  ++outIterPair.first
617  ) {
618  const auto& outEdge = *outIterPair.first;
619 
620  auto edgeTarget = boost::target(outEdge, tree_);
621 
622  // Skip this vertex if in omnidirectional BFS and already-seen node
623  if(!bfsDownOnly && visitedVertices.count(edgeTarget) > 0) {
624  continue;
625  }
626 
627  if constexpr(insertVertices) {
628  comparisonSets.at(undecidedBranch).insert(edgeTarget);
629  }
630 
631  if constexpr(insertEdges) {
632  comparisonSets.at(undecidedBranch).insert(outEdge);
633  }
634 
635  // Add out edge target to seeds only if non-terminal
636  if(!tree_[edgeTarget].isDuplicate) {
637  newSeeds.push_back(edgeTarget);
638  }
639  }
640  }
641 
642  // Overwrite seeds
643  seeds.at(undecidedBranch) = std::move(newSeeds);
644  }
645  }
646 
647  // Make comparisons in all undecided sets
648  compareBFSSets_(comparisonSets, undecidedSets, orderingHelper);
649 
650  // Recalculate the undecided sets
651  undecidedSets = orderingHelper.getUndecidedSets();
652 
653  // Increment depth
654  ++depth;
655 
656  if constexpr (buildTypeIsDebug) {
657  if(
658  Log::particulars.count(Log::Particulars::RankingTreeDebugInfo) > 0
659  && notEmpty_(comparisonSets)
660  ) {
661  std::string header;
662  if(!bfsDownOnly) {
663  header += "aux "s;
664  }
665  header += "R"s + std::to_string(ruleNumber);
666 
667  writeGraphvizFiles_({
668  adaptedMolGraphviz_,
669  dumpGraphviz(
670  header,
671  {sourceIndex},
672  collectSeeds_(seeds, undecidedSets)
673  ),
674  makeBFSStateGraph_(
675  header,
676  sourceIndex,
677  comparisonSets,
678  undecidedSets
679  ),
680  orderingHelper.dumpGraphviz()
681  });
682  }
683  }
684  }
685  }
686 
687  // Flatten the undecided branches' seeds into a single set
688  static std::unordered_set<TreeVertexIndex> collectSeeds_(
689  const std::map<
690  TreeVertexIndex,
691  std::vector<TreeVertexIndex>
692  >& seeds,
693  const std::vector<
694  std::vector<TreeVertexIndex>
695  >& undecidedSets
696  );
697 
699  template<typename ValueType, typename ComparatorType>
700  std::string makeBFSStateGraph_(
701  const std::string& title,
702  const TreeVertexIndex& base,
703  const std::map<
705  std::multiset<ValueType, ComparatorType>
706  >& comparisonSet,
707  const std::vector<
708  std::vector<TreeVertexIndex>
709  >& undecidedSets
710  ) const {
711 
712  std::set<TreeVertexIndex> activeBranches;
713  for(const auto& set : undecidedSets) {
714  for(const auto& value : set) {
715  activeBranches.insert(value);
716  }
717  }
718 
719  struct DisplayGraphVertexData {
720  std::string representation;
721  };
722 
723  using DisplayGraph = boost::adjacency_list<
724  /* OutEdgeListS = Type of Container for edges of a vertex
725  * Options: vector, list, slist, set, multiset, unordered_set
726  * Choice: setS
727  */
728  boost::setS,
729  /* VertexListS = Type of Container for vertices
730  * Options: vector, list, slist, set, multiset, unordered_set
731  * Choice: vecS, removing vertices does not occur
732  */
733  boost::vecS,
734  /* DirectedS = Is the graph directed or not?
735  * Choice: Directed, do not need bidirectional
736  */
737  boost::directedS,
738  /* VertexProperty = What information is stored about vertices?
739  * Choice: Atom, containing an index and an element type
740  */
741  DisplayGraphVertexData
742  >;
743 
744  std::set<TreeVertexIndex> colorVertices;
745  std::set<TreeVertexIndex> squareVertices;
746 
747  DisplayGraph graph;
748 
749  auto baseVertex = boost::add_vertex(graph);
750  graph[baseVertex].representation = toString(base);
751 
752  squareVertices.insert(baseVertex);
753 
754  for(const auto& branchIterPair : comparisonSet) {
755  const auto& treeBranchIndex = branchIterPair.first;
756  const auto& treeBranchMultiset = branchIterPair.second;
757 
758  auto branchVertex = boost::add_vertex(graph);
759  graph[branchVertex].representation = toString(treeBranchIndex);
760 
761  squareVertices.insert(branchVertex);
762 
763  if(activeBranches.count(treeBranchIndex) > 0) {
764  colorVertices.insert(branchVertex);
765  }
766 
767  boost::add_edge(baseVertex, branchVertex, graph);
768 
769  typename DisplayGraph::vertex_descriptor continuation = branchVertex;
770  for(const auto& multisetValue : treeBranchMultiset) {
771  auto newVertex = boost::add_vertex(graph);
772  graph[newVertex].representation = toString(multisetValue);
773 
774  boost::add_edge(continuation, newVertex, graph);
775  continuation = newVertex;
776  }
777  }
778 
779  class SmallGraphWriter {
780  private:
781  const DisplayGraph& graphBase_;
782  const std::string title_;
783  const std::set<TreeVertexIndex> colorVertices_;
784  const std::set<TreeVertexIndex> squareVertices_;
785 
786  public:
787  SmallGraphWriter(
788  const DisplayGraph& base,
789  std::string title,
790  std::set<TreeVertexIndex> colorVertices,
791  std::set<TreeVertexIndex> squareVertices
792  ) : graphBase_(base),
793  title_(std::move(title)),
794  colorVertices_(std::move(colorVertices)),
795  squareVertices_(std::move(squareVertices))
796  {}
797 
798  void operator() (std::ostream& os) const {
799  os << " graph [fontname = \"Arial\", layout=\"dot\"];\n"
800  << " node [fontname = \"Arial\", shape = circle, style = filled];\n"
801  << " edge [fontname = \"Arial\"];\n"
802  << R"( labelloc="t"; label=")" << title_ << "\"\n";
803  }
804 
805  void operator() (
806  std::ostream& os,
807  const typename DisplayGraph::vertex_descriptor& vertexIndex
808  ) const {
809  if(vertexIndex == rootIndex) {
810  os << R"([label=")" << title_ << "\\n-\\n" << graphBase_[rootIndex].representation << R"(")";
811  } else {
812  os << R"([label=")" << graphBase_[vertexIndex].representation << R"(")";
813  }
814 
815  if(colorVertices_.count(vertexIndex) > 0) {
816  os << R"(, fillcolor="tomato", fontcolor="white")";
817  }
818 
819  if(squareVertices_.count(vertexIndex) > 0) {
820  os << R"(, shape="square")";
821  }
822 
823  os << R"(])";
824  }
825 
826  void operator() (
827  std::ostream& /* os */,
828  const typename DisplayGraph::edge_descriptor& /* edge */
829  ) const { /* do nothing particular for edges */ }
830 
831  };
832 
833  SmallGraphWriter propertyWriter {graph, title, colorVertices, squareVertices};
834 
835  std::stringstream ss;
836 
837  boost::write_graphviz(
838  ss,
839  graph,
840  propertyWriter,
841  propertyWriter,
842  propertyWriter
843  );
844 
845  return ss.str();
846  }
847 
849  std::string _make4BGraph(
850  const TreeVertexIndex& sourceIndex,
851  const std::map<
852  TreeVertexIndex,
853  std::set<VariantType>
854  >& representativeStereodescriptors,
855  const TreeVertexIndex& branchA,
856  const TreeVertexIndex& branchB,
857  const std::vector<
858  std::vector<VariantType>
859  >& branchAOrders,
860  const std::vector<
861  std::vector<VariantType>
862  >& branchBOrders,
863  const std::vector<
864  std::vector<VariantType>
865  >::reverse_iterator& branchAIter,
866  const std::vector<
867  std::vector<VariantType>
868  >::reverse_iterator& branchBIter
869  ) const;
870 
872  std::vector<
873  std::vector<AtomIndex>
874  > mapToAtomIndices_(
875  const std::vector<
876  std::vector<TreeVertexIndex>
877  >& treeRankingSets
878  ) const;
879 
898  static bool relevantSeeds_(
899  const std::map<
900  TreeVertexIndex,
901  std::vector<TreeVertexIndex>
902  >& seeds,
903  const std::vector<
904  std::vector<TreeVertexIndex>
905  >& undecidedSets
906  );
907 
917  void applySequenceRules_(
918  const boost::optional<AngstromPositions>& positionsOption
919  );
920 
946  std::vector<
947  std::vector<TreeVertexIndex>
948  > auxiliaryApplySequenceRules_(
949  TreeVertexIndex sourceIndex,
950  const std::vector<TreeVertexIndex>& adjacentsToRank,
951  const boost::optional<unsigned>& depthLimitOptional = boost::none
952  ) const;
953 
954 public:
957 
965  RankingTree(
966  const Graph& graph,
967  const StereopermutatorList& stereopermutators,
968  std::string molGraphviz,
969  AtomIndex atomToRank,
970  const std::vector<AtomIndex>& excludeIndices = {},
971  ExpansionOption expansionMethod = ExpansionOption::OnlyRequiredBranches,
972  const boost::optional<AngstromPositions>& positionsOption = boost::none
973  );
975 
978 
984  std::vector<
985  std::vector<AtomIndex>
986  > getRanked() const;
987 
993  std::string dumpGraphviz(
994  const std::string& title = "",
995  const std::unordered_set<TreeVertexIndex>& squareVertices = {},
996  const std::unordered_set<TreeVertexIndex>& colorVertices = {},
997  const std::set<TreeEdgeIndex>& colorEdges = {}
998  ) const;
1000 };
1001 
1002 } // namespace Molassembler
1003 } // namespace Scine
1004 
1005 #endif
OrderDiscoveryHelper< TreeVertexIndex > branchOrderingHelper_
The helper instance for discovering the ordering of the to-rank branches.
Definition: RankingTree.h:199
void compareBFSSets_(const std::map< TreeVertexIndex, std::multiset< SetValueType, ComparatorType > > &comparisonSets, const std::vector< std::vector< TreeVertexIndex > > &undecidedSets, OrderDiscoveryHelper< TreeVertexIndex > &orderingHelper) const
Definition: RankingTree.h:353
std::vector< std::vector< T > > getUndecidedSets() const
Returns grouped data (in descending order) whose internal order is undecided.
Definition: OrderDiscoveryHelper.h:426
BglType::vertex_descriptor TreeVertexIndex
Type of tree vertex accessor.
Definition: RankingTree.h:178
Central class for unified IUPAC-like ranking of organic and inorganic structures. ...
Definition: RankingTree.h:62
Represents the connectivity of atoms of a molecule.
Definition: Graph.h:54
void runBFS_(TreeVertexIndex sourceIndex, OrderDiscoveryHelper< TreeVertexIndex > &orderingHelper, const boost::optional< unsigned > &depthLimitOptional=boost::none) const
Definition: RankingTree.h:415
std::string dumpGraphviz() const
Dumps a graphviz string for visualization of relationships.
Definition: OrderDiscoveryHelper.h:470
Basic Logging functionality for debugging.
Bond distance modelling functions.
Handle arrangements of substituents at corners of an atom-centered shape.
boost::variant< TreeVertexIndex, TreeEdgeIndex > VariantType
Variant type of both.
Definition: RankingTree.h:182
Molecule class interface.
bool isDuplicate
Whether this vertex in the tree represents a duplicate.
Definition: RankingTree.h:101
Manages all stereopermutators that are part of a Molecule.
Definition: StereopermutatorList.h:30
void forEach(const Container &container, Callable &&callable)
Apply a callable for all values of a container.
Definition: Functional.h:158
static unsigned debugMessageCounter_
Definition: RankingTree.h:67
std::size_t AtomIndex
Unsigned integer atom index type. Used to refer to particular atoms.
Definition: Types.h:51
Provides pair-generation within a single container or two.
Handle rotational arrangements of adjacent atom-centered shapes.
Defines a compile-time constant boolean indicating the build type.
Data class to store junction vertex and paths from the source vertices.
Definition: RankingTree.h:185
ExpansionOption
Definition: RankingTree.h:89
boost::optional< AtomStereopermutator > stereopermutatorOption
A vertex-central stereopermutator may be instantiated here or may not.
Definition: RankingTree.h:104
Graph class to help in gradual discovery of ordering relations.
AtomIndex molIndex
The original molecule index this vertex represents.
Definition: RankingTree.h:99
bool notEmpty_(const ComparisonSets &comparisonSets) const
Returns whether any of the comparison multisets has an entry.
Definition: RankingTree.h:234
constexpr auto map(const ArrayType< T, size > &array, UnaryFunction &&function)
Maps all elements of any array-like container with a unary function.
Definition: Containers.h:63
bool multisetCompare_(const std::multiset< SetValueType, ComparatorType > &a, const std::multiset< SetValueType, ComparatorType > &b) const
Definition: RankingTree.h:311
std::string makeBFSStateGraph_(const std::string &title, const TreeVertexIndex &base, const std::map< TreeVertexIndex, std::multiset< ValueType, ComparatorType > > &comparisonSet, const std::vector< std::vector< TreeVertexIndex > > &undecidedSets) const
Creates a graphviz representation of the BFS state.
Definition: RankingTree.h:700
Data class that sets which supplementary data is stored for a tree edge.
Definition: RankingTree.h:111
BglType::edge_descriptor TreeEdgeIndex
Type of tree edge accessor.
Definition: RankingTree.h:180
BglType tree_
The BGL Graph representing the acyclic tree.
Definition: RankingTree.h:196
Data class that sets which supplementary data is stored for a tree vertex.
Definition: RankingTree.h:97
boost::adjacency_list< boost::setS, boost::vecS, boost::bidirectionalS, VertexData, EdgeData > BglType
The BGL Graph type used to store the tree.
Definition: RankingTree.h:137
bool all_of(const Container &container, UnaryPredicate &&predicate=UnaryPredicate{})
all_of shorthand
Definition: Functional.h:234
void addLessThanRelationship(const T &a, const T &b)
Add a less-than relationship to the graph.
Definition: OrderDiscoveryHelper.h:450