31 #ifndef INCLUDE_MOLASSEMBLER_RANKING_HIERARCHICAL_TREE_H
32 #define INCLUDE_MOLASSEMBLER_RANKING_HIERARCHICAL_TREE_H
34 #include "boost/variant.hpp"
46 using namespace std::string_literals;
49 namespace Molassembler {
72 static std::string adaptMolGraph_(std::string molGraph);
75 static void writeGraphvizFiles_(
76 const std::vector<std::string>& graphvizStrings
112 boost::optional<BondStereopermutator> stereopermutatorOption;
116 using BglType = boost::adjacency_list<
132 boost::bidirectionalS,
140 class SequenceRuleOneVertexComparator;
143 class SequenceRuleTwoVertexComparator;
146 class SequenceRuleThreeEdgeComparator;
149 class SequenceRuleFourVariantComparator;
152 class SequenceRuleFiveVariantComparator;
155 class VariantHasInstantiatedStereopermutator;
161 class VariantSourceNode;
164 class VariantStereopermutatorStringRepresentation;
170 class VariantLikePair;
173 class GraphvizWriter;
182 using VariantType = boost::variant<TreeVertexIndex, TreeEdgeIndex>;
188 std::vector<TreeVertexIndex> firstPath, secondPath;
204 const std::string adaptedMolGraphviz_;
214 unsigned adjacentTerminalHydrogens_(
const TreeVertexIndex& index)
const;
220 bool isCycleClosureDuplicateVertex_(
const TreeVertexIndex& index)
const;
227 std::vector<TreeVertexIndex> auxiliaryAdjacentsToRank_(
229 const std::vector<TreeVertexIndex>& excludeIndices
233 template<
typename ComparisonSets>
234 bool notEmpty_(
const ComparisonSets& comparisonSets)
const {
237 [](
const auto& mapPair) ->
bool {
238 return !mapPair.second.empty();
247 unsigned nonDuplicateDegree_(
const TreeVertexIndex& index)
const;
256 std::vector<TreeVertexIndex> addBondOrderDuplicates_(
257 const TreeVertexIndex& treeSource,
258 const TreeVertexIndex& treeTarget
262 std::unordered_set<TreeVertexIndex> treeIndicesInBranch_(TreeVertexIndex index)
const;
265 std::unordered_set<AtomIndex> molIndicesInBranch_(TreeVertexIndex index)
const;
268 unsigned duplicateDepth_(TreeVertexIndex index)
const;
271 unsigned depthOfNode_(TreeVertexIndex index)
const;
274 unsigned mixedDepth_(
const TreeVertexIndex& vertexIndex)
const;
277 unsigned mixedDepth_(
const TreeEdgeIndex& edgeIndex)
const;
283 JunctionInfo junction_(
const TreeVertexIndex& a,
const TreeVertexIndex& b)
const;
286 bool molIndexExistsInBranch_(
288 TreeVertexIndex treeIndex
300 std::vector<TreeVertexIndex> expand_(
301 const TreeVertexIndex& index,
302 const std::unordered_set<AtomIndex>& molIndicesInBranch
310 template<
typename SetValueType,
typename ComparatorType>
312 const std::multiset<SetValueType, ComparatorType>& a,
313 const std::multiset<SetValueType, ComparatorType>& b
315 return std::lexicographical_compare(
320 ComparatorType {*
this}
352 template<
typename SetValueType,
typename ComparatorType>
356 std::multiset<SetValueType, ComparatorType>
359 std::vector<TreeVertexIndex>
363 for(
const auto& undecidedSet : undecidedSets) {
365 Temple::Adaptors::allPairs(undecidedSet),
367 if(multisetCompare_(comparisonSets.at(a), comparisonSets.at(b))) {
369 }
else if(multisetCompare_(comparisonSets.at(b), comparisonSets.at(a))) {
377 static std::string toString(TreeVertexIndex vertex);
378 std::string toString(
const TreeEdgeIndex& edge)
const;
379 std::string toString(
const VariantType& vertexOrEdge)
const;
413 typename MultisetValueType,
414 typename MultisetComparatorType
418 const boost::optional<unsigned>& depthLimitOptional = boost::none
422 insertEdges || insertVertices,
423 "During BFS, you must insert either edges, vertices, or both into the "
424 " comparison sets, but definitely not neither"
430 && !std::is_same<MultisetValueType, TreeVertexIndex>::value
433 && !std::is_same<MultisetValueType, TreeEdgeIndex>::value
435 "Multiset value type and insert booleans are mismatched"
439 if(depthLimitOptional.value_or(std::numeric_limits<unsigned>::max()) == 0) {
457 std::multiset<MultisetValueType, MultisetComparatorType>
469 std::vector<TreeVertexIndex>
475 std::unordered_set<TreeVertexIndex> visitedVertices;
480 visitedVertices.insert(sourceIndex);
485 for(
const auto& undecidedSet : undecidedSets) {
486 for(
const auto& undecidedBranch : undecidedSet) {
487 comparisonSets.emplace(
492 if constexpr(insertVertices) {
493 comparisonSets.at(undecidedBranch).insert(undecidedBranch);
496 if constexpr(insertEdges) {
498 const auto edge = boost::edge(sourceIndex, undecidedBranch, tree_).first;
499 comparisonSets.at(undecidedBranch).insert(edge);
502 auto forwardEdge = boost::edge(sourceIndex, undecidedBranch, tree_);
503 auto backwardEdge = boost::edge(undecidedBranch, sourceIndex, tree_);
505 const auto edge = forwardEdge.second ? forwardEdge.first : backwardEdge.first;
506 comparisonSets.at(undecidedBranch).insert(edge);
510 seeds[undecidedBranch] = {undecidedBranch};
515 compareBFSSets_(comparisonSets, undecidedSets, orderingHelper);
520 if constexpr (buildTypeIsDebug) {
523 Log::particulars.count(Log::Particulars::RankingTreeDebugInfo) > 0
524 && notEmpty_(comparisonSets)
526 std::string header = (
531 ) +
"R"s + std::to_string(ruleNumber)
534 writeGraphvizFiles_({
539 collectSeeds_(seeds, undecidedSets)
561 !undecidedSets.empty()
563 && relevantSeeds_(seeds, undecidedSets)
564 && depth < depthLimitOptional.value_or(std::numeric_limits<unsigned>::max())
567 for(
const auto& undecidedSet: undecidedSets) {
568 for(
const auto& undecidedBranch: undecidedSet) {
577 comparisonSets.at(undecidedBranch).clear();
579 std::vector<TreeVertexIndex> newSeeds;
581 for(
const auto& seed : seeds.at(undecidedBranch)) {
585 visitedVertices.insert(seed);
589 auto inIterPair = boost::in_edges(seed, tree_);
590 inIterPair.first != inIterPair.second;
593 const auto& inEdge = *inIterPair.first;
595 auto edgeSource = boost::source(inEdge, tree_);
598 if(visitedVertices.count(edgeSource) == 0) {
599 if constexpr(insertVertices) {
600 comparisonSets.at(undecidedBranch).insert(edgeSource);
603 if constexpr(insertEdges) {
604 comparisonSets.at(undecidedBranch).insert(inEdge);
607 newSeeds.push_back(edgeSource);
614 auto outIterPair = boost::out_edges(seed, tree_);
615 outIterPair.first != outIterPair.second;
618 const auto& outEdge = *outIterPair.first;
620 auto edgeTarget = boost::target(outEdge, tree_);
623 if(!bfsDownOnly && visitedVertices.count(edgeTarget) > 0) {
627 if constexpr(insertVertices) {
628 comparisonSets.at(undecidedBranch).insert(edgeTarget);
631 if constexpr(insertEdges) {
632 comparisonSets.at(undecidedBranch).insert(outEdge);
636 if(!tree_[edgeTarget].isDuplicate) {
637 newSeeds.push_back(edgeTarget);
643 seeds.at(undecidedBranch) = std::move(newSeeds);
648 compareBFSSets_(comparisonSets, undecidedSets, orderingHelper);
656 if constexpr (buildTypeIsDebug) {
658 Log::particulars.count(Log::Particulars::RankingTreeDebugInfo) > 0
659 && notEmpty_(comparisonSets)
665 header +=
"R"s + std::to_string(ruleNumber);
667 writeGraphvizFiles_({
672 collectSeeds_(seeds, undecidedSets)
688 static std::unordered_set<TreeVertexIndex> collectSeeds_(
691 std::vector<TreeVertexIndex>
694 std::vector<TreeVertexIndex>
699 template<
typename ValueType,
typename ComparatorType>
701 const std::string& title,
705 std::multiset<ValueType, ComparatorType>
708 std::vector<TreeVertexIndex>
712 std::set<TreeVertexIndex> activeBranches;
713 for(
const auto& set : undecidedSets) {
714 for(
const auto& value : set) {
715 activeBranches.insert(value);
719 struct DisplayGraphVertexData {
720 std::string representation;
723 using DisplayGraph = boost::adjacency_list<
741 DisplayGraphVertexData
744 std::set<TreeVertexIndex> colorVertices;
745 std::set<TreeVertexIndex> squareVertices;
749 auto baseVertex = boost::add_vertex(graph);
750 graph[baseVertex].representation = toString(base);
752 squareVertices.insert(baseVertex);
754 for(
const auto& branchIterPair : comparisonSet) {
755 const auto& treeBranchIndex = branchIterPair.first;
756 const auto& treeBranchMultiset = branchIterPair.second;
758 auto branchVertex = boost::add_vertex(graph);
759 graph[branchVertex].representation = toString(treeBranchIndex);
761 squareVertices.insert(branchVertex);
763 if(activeBranches.count(treeBranchIndex) > 0) {
764 colorVertices.insert(branchVertex);
767 boost::add_edge(baseVertex, branchVertex, graph);
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);
774 boost::add_edge(continuation, newVertex, graph);
775 continuation = newVertex;
779 class SmallGraphWriter {
781 const DisplayGraph& graphBase_;
782 const std::string title_;
783 const std::set<TreeVertexIndex> colorVertices_;
784 const std::set<TreeVertexIndex> squareVertices_;
788 const DisplayGraph& base,
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))
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";
807 const typename DisplayGraph::vertex_descriptor& vertexIndex
809 if(vertexIndex == rootIndex) {
810 os << R
"([label=")" << title_ << "\\n-\\n" << graphBase_[rootIndex].representation << R
"(")";
812 os << R
"([label=")" << graphBase_[vertexIndex].representation << R"(")";
815 if(colorVertices_.count(vertexIndex) > 0) {
816 os << R
"(, fillcolor="tomato", fontcolor="white")";
819 if(squareVertices_.count(vertexIndex) > 0) {
820 os << R
"(, shape="square")";
828 const typename DisplayGraph::edge_descriptor&
833 SmallGraphWriter propertyWriter {graph, title, colorVertices, squareVertices};
835 std::stringstream ss;
837 boost::write_graphviz(
849 std::string _make4BGraph(
850 const TreeVertexIndex& sourceIndex,
853 std::set<VariantType>
854 >& representativeStereodescriptors,
855 const TreeVertexIndex& branchA,
856 const TreeVertexIndex& branchB,
858 std::vector<VariantType>
861 std::vector<VariantType>
864 std::vector<VariantType>
865 >::reverse_iterator& branchAIter,
867 std::vector<VariantType>
868 >::reverse_iterator& branchBIter
873 std::vector<AtomIndex>
876 std::vector<TreeVertexIndex>
898 static bool relevantSeeds_(
901 std::vector<TreeVertexIndex>
904 std::vector<TreeVertexIndex>
917 void applySequenceRules_(
918 const boost::optional<AngstromPositions>& positionsOption
947 std::vector<TreeVertexIndex>
948 > auxiliaryApplySequenceRules_(
949 TreeVertexIndex sourceIndex,
950 const std::vector<TreeVertexIndex>& adjacentsToRank,
951 const boost::optional<unsigned>& depthLimitOptional = boost::none
968 std::string molGraphviz,
970 const std::vector<AtomIndex>& excludeIndices = {},
971 ExpansionOption expansionMethod = ExpansionOption::OnlyRequiredBranches,
972 const boost::optional<AngstromPositions>& positionsOption = boost::none
985 std::vector<AtomIndex>
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 = {}
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