NCBI C++ ToolKit
phylo_tree_algorithm.hpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef GUI_WIDGETS_PHYLO_TREE__PHYLO_TREE_ALGORITHM_HPP
2 #define GUI_WIDGETS_PHYLO_TREE__PHYLO_TREE_ALGORITHM_HPP
3 
4 /* $Id: phylo_tree_algorithm.hpp 47479 2023-05-02 13:24:02Z ucko $
5  * ===========================================================================
6  *
7  * PUBLIC DOMAIN NOTICE
8  * National Center for Biotechnology Information
9  *
10  * This software/database is a "United States Government Work" under the
11  * terms of the United States Copyright Act. It was written as part of
12  * the author's official duties as a United States Government employee and
13  * thus cannot be copyrighted. This software/database is freely available
14  * to the public for use. The National Library of Medicine and the U.S.
15  * Government have not placed any restriction on its use or reproduction.
16  *
17  * Although all reasonable efforts have been taken to ensure the accuracy
18  * and reliability of the software and data, the NLM and the U.S.
19  * Government do not and cannot warrant the performance or results that
20  * may be obtained by using this software or data. The NLM and the U.S.
21  * Government disclaim all warranties, express or implied, including
22  * warranties of performance, merchantability or fitness for any particular
23  * purpose.
24  *
25  * Please cite the author in any work or product based on this material.
26  *
27  * ===========================================================================
28  *
29  * Authors: Vladimir Tereshkov
30  *
31  * File Description:
32  *
33  */
34 
35 
36 #include <corelib/ncbistd.hpp>
37 #include <corelib/ncbiobj.hpp>
38 #include <corelib/ncbi_tree.hpp>
39 #include <gui/opengl/glpane.hpp>
42 #include <objmgr/scope.hpp>
46 #include <util/ncbi_table.hpp>
47 
48 
50 
52 {
53 public:
57 
58 public:
60  virtual ~IPhyloTreeVisitor(){}
61 
63 protected:
65  virtual ETreeTraverseCode x_OnStepLeft(TTreeIdx x_node);
66  virtual ETreeTraverseCode x_OnStepDown(TTreeIdx x_node);
67  virtual ETreeTraverseCode x_OnStep(TTreeIdx x_node, int delta);
68 
70 };
71 
72 
73 
74 
76 {
77 public:
81 
82 public:
85 
86 
87  unsigned GetNumNodes() { return m_NodeCount; }
88  unsigned GetVisibleNodes() { return m_VisibleNodes; }
89  // as a tree number of edges has to be m_NodeCount -1
90  unsigned GetNumEdges() { return m_NodeCount-1; }
91  int GetWidth() { return m_Width; }
92  int GetHeight() { return m_Height;}
93  double GetMaxDistance() { return m_MaxDistance; }
94  double GetMinDistance() { return m_MinDistance; }
95  int GetMaxLabelLen() { return static_cast<int>(m_MaxLabelLen); }
96  void DumpStats();
97  const TClusterHash & GetClusters() { return m_Clusters; }
98  void SetClusters(const TClusterHash & clst) { m_Clusters = clst; }
100  void SetAttrTable(const TAttrTable & attr);
101  void ClearAttrTable();
102  void SetLabelFormat(string labelFmt) { m_LabelFormat = labelFmt; }
103  void Init(CRgbaGradColorTable* ct);
104 
105 
106 
107 protected:
108  virtual ETreeTraverseCode x_OnStepRight(TTreeIdx x_node);
109  virtual ETreeTraverseCode x_OnStepLeft(TTreeIdx x_node);
110  virtual ETreeTraverseCode x_OnStepDown(TTreeIdx x_node);
111  virtual ETreeTraverseCode x_OnStep(TTreeIdx x_node, int delta);
112 
113  /// Updates node properties using values from m_AttrTable
114  void x_UpdateProperties(TNodeType& node, int row_idx);
115 
116 private:
117  unsigned m_PamlID;
118  unsigned m_ID;
119  unsigned m_NodeCount;
120  unsigned m_VisibleNodes;
121  int m_PosX;
122  int m_PosY;
123  int m_Leaves;
124  int m_Childs;
125  int m_Width;
126  int m_Height;
130 
133 
135  float m_LastDist;
136 
137  // The top-level collapsed node (if any) to keep track of hidden nodes
139 
140  /// Attributes with seq-ids optionally provided to update tree properties
144 
145  /// Structure allows us to more efficiently store and look up keys (usually seq-ids)
146  /// in m_AttrTable.
147  struct AttrKey {
149  AttrKey(const string& id, unsigned int idx)
150  : m_IDStr(id)
151  , m_AttrTableIdx(idx) {}
152 
153  /// Sort keys on seq-id string value
154  bool operator<(const AttrKey& rhs) const { return (m_IDStr <
155  rhs.m_IDStr); }
156  string m_IDStr;
157  unsigned int m_AttrTableIdx;
158  };
159 
160 
161  /// Mapping for efficient lookup of seq-ids in m_AttrTable.
162  vector<AttrKey> m_AttrKeys;
163 
164  /// label calculation
168 };
169 
171 {
172 public:
175  { Init(); }
176 
178  const TModelRect & GetRect() const {return m_Rect; }
179  void Init();
180 protected:
181  virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta);
182 private:
184 };
185 
187 {
188 public:
191  , m_PriorityLeafIdx(TTreeType::Null())
192  , m_LeafMidpoint(0.0f)
193  , m_LeafCount(0)
194  , m_PriorityId(-1)
195  , m_MaxPriority(-1)
197  {
198  Init(node_idx);
199  }
200 
202  void Init(TTreeIdx node_idx);
203 
205 
206 protected:
207  virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta);
208 
209 private:
210  /// Leaf with highest priority number
212  /// Index of leaf at center of subtree (leaves in subtree/2)
214  /// Current leaf count (as we iterate over the subtree)
215  size_t m_LeafCount;
216 
217  /// Id of priority feature in tree
219 
220  /// Max priority value found in priority field in subtree
222  /// Leaf index of node with m_MaxPriority. Used to resolve conflicts if
223  /// more than one node in subtree has same max priority value.
225 };
226 
228 {
229 public:
232  , m_Id(0) {}
233 
235 
236  CPhyloNodeData::TID GetMaxId() const {return m_Id; }
237 
238 protected:
239  virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta);
241 };
242 
244 {
245 public:
246  CPhyloTreeSorter(TTreeType* tree, bool x_order)
248  , m_Order(x_order) {}
249 
250 protected:
251  virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta);
252 
253 private:
254  bool m_Order;
255 };
256 
259  SChildMaxDist(TTreeIdx idx, float dist)
260  : m_NodeIdx(idx)
261  , m_MaxChildDist(dist) {}
262 
263  /// Sort keys on seq-id string value
264  bool operator<(const SChildMaxDist& rhs) const {
265  return (m_MaxChildDist < rhs.m_MaxChildDist);
266  }
269 };
270 
271 
272 // Pass in a function derived from SCollapsable that returns
273 // false for any nodes that should not be collapsed.
274 struct SCollapsable : public CObject {
275  virtual bool operator() (const CPhyloTreeNode& n) { return true; }
276 };
277 
278 /// For each node this finds the maximum distance of any of its immediate
279 /// (not recursively searched) children from the root.
281 {
282 public:
285  , m_Distances(tree->GetSize(), SChildMaxDist(0, 0.0f))
286  , m_LastDist(0.0f)
287  , m_DistFromRoot(0.0f)
288  , m_CheckCollapseFunc(collapsable_func)
289  {
290  if (m_CheckCollapseFunc.IsNull()) {
292  }
293  }
294 
295  vector<SChildMaxDist>& GetDistances() { return m_Distances; }
296 
297 protected:
298  virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta);
299 
300 private:
301  /// Max distace of any direct child of a node from the root, saved in same order
302  /// as node array in tree
303  vector<SChildMaxDist> m_Distances;
304  float m_LastDist;
307 };
308 
309 /// For each node, this returns the maximum distances of any of its children
310 /// (recursively searched) from the root node.
312 {
313 public:
316  , m_Distances(tree->GetSize(), 0.0f)
317  , m_LastDist(0.0f)
318  , m_DistFromRoot(0.0f)
319  , m_MaxDist(-std::numeric_limits<float>::max())
320  , m_MinDist(std::numeric_limits<float>::max())
321  {
322  }
323 
324  vector<float>& GetDistances() { return m_Distances; }
325  float GetMaxDist() const { return m_MaxDist; }
326  float GetMinDist() const { return m_MinDist; }
327 
328 protected:
329  virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta);
330 
331 private:
332  /// Max distace of any child of a node from the root, saved in same order
333  /// as node array in tree
334  vector<float> m_Distances;
335  float m_LastDist;
337 
338  /// Keep track of overall max and min distances
339  float m_MaxDist;
340  float m_MinDist;
341 };
342 
343 // Build a vector of a the distance of each node from the root node.
344 // This is needed by the CPhyloTreeMidpointDist algorithm .
346 {
347 public:
350  , m_Distances(tree->GetSize(), 0.0f)
351  , m_LastDist(0.0f)
352  , m_DistFromRoot(0.0f)
353  , m_MaxBranchDist(0.0f)
354  , m_MaxDistNode(CPhyloTree::Null()) {}
355 
356  vector<float>& GetDistances() { return m_Distances; }
358 
359 protected:
360  virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta);
361 
362 private:
363  /// Distance of each node from root
364  vector<float> m_Distances;
365 
366  float m_LastDist;
369 
370  /// Index of node that is furthest from the root.
372 };
373 
374 // Find the pair of nodes in the tree with the longest path between
375 // them, and return that path and it's total distance.
377 {
378 public:
380  vector<float>& distances,
381  TTreeIdx max_dist_node_idx)
383  , m_Distances(distances)
384  , m_MaxDistNode(max_dist_node_idx)
385  , m_MaxDist(0.0f)
386  {
388 
389  // Get all nodes from m_MaxDistNode to root:
390  TTreeIdx idx = m_MaxDistNode;
391  while (idx != CPhyloTree::Null()) {
392  m_MaxDistPathToRoot.insert(m_MaxDistPathToRoot.begin(), idx);
393  idx = (*m_Tree)[idx].GetParent();
394  }
395 
399  }
400 
401  void GetLongest(vector<TTreeIdx>& path, float& length);
402 
403 protected:
404  virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta);
405 
406 private:
407  /// Distance of each node from root node
408  vector<float> m_Distances;
409 
410  /// Node at greatest distance from root, its distance and vector
411  /// of nodes from root to m_MaxDistNode (sorted and unsorted)
414  vector<TTreeIdx> m_MaxDistPathToRoot;
415  vector<TTreeIdx> m_SortedMaxDistPathToRoot;
416 
417  /// Path (set of nodes) that is the longest path in the tree
418  vector<TTreeIdx> m_MaxPath;
419  /// Total distance along m_MaxPath
420  float m_MaxDist;
421 };
422 
423 // For each node int the tree find from its subnodes the lexiocographical
424 // min and max label values, e.g. if lables of the children of 'q' are
425 // 'c', 'f' and 't', the min is 'c' and the max is 't'.
427 {
428 public:
431  , m_LabelRanges(tree->GetSize()) {}
432 
433  vector<pair<string,string> >& GetLabelRanges() { return m_LabelRanges; }
434 
435 protected:
436  virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta);
437 
438 private:
439  /// Min and max label values (according to lexicographic
440  vector<pair<string,string> > m_LabelRanges;
443 };
444 
446 {
447 public:
449  const vector<float>& distances,
450  bool x_order)
452  , m_Distances(distances)
453  , m_Order(x_order) {}
454 
455 protected:
456  virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta);
457 
458 private:
459  const vector<float>& m_Distances;
460  bool m_Order;
461 };
462 
464 {
465 public:
468  , m_Order(x_order) {}
469 
470 protected:
471  virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta);
472 
473 private:
474  bool m_Order;
475 };
476 
477 
479 {
480 public:
482  const vector<pair<string,string> >& label_ranges,
483  bool x_order)
485  , m_LabelRanges(label_ranges)
486  , m_Order(x_order) {}
487 
488 protected:
489  virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta);
490 
491 private:
492  const vector<pair<string,string> >& m_LabelRanges;
493  bool m_Order;
494 };
495 
497 {
498 public:
500 
501 protected:
502  virtual ETreeTraverseCode x_OnStep(TTreeIdx x_node, int delta);
503 
504  // all allowed
505  virtual bool x_Allowed(TNodeType& /*node*/) {return true;}
506 
507 private:
508  vector<TTreeIdx> m_TreeStack;
509 };
510 
511 // filter out not selected nodes
513 {
514 public:
516 protected:
517  virtual bool x_Allowed(TNodeType& node)
518  {
519  return (((*node).GetSelectedState()==CPhyloNodeData::eSelected) ||
520  ((*node).GetSelectedState()==CPhyloNodeData::eShared));
521  }
522 };
523 
524 // filter out nodes, having childs number == 1
526 {
527 public:
529 protected:
530  virtual bool x_Allowed(TNodeType& node)
531  {
532  if (node.GetChildren().size() == 1 && node.GetParent() != TNodeType::Null()) {
533  TTreeIdx child_idx = node.GetChildren()[0];
534  if (m_Tree->GetNode(child_idx).GetChildren().size() == 0)
535  return false;
536  }
537  return true;
538  }
539 };
540 
541 
542 // filter out nodes, with distances falling under threshold
544 {
545 public:
548  , m_Dist((float)x_dist) {}
549 
550 protected:
551  virtual bool x_Allowed(TNodeType& node)
552  {
553  return !(node.GetParent()==TNodeType::Null()) ||
554  ((*node).GetDistance() > m_Dist);
555  }
556 private:
557  double m_Dist;
558 };
559 
560 // filter out nodes, exceeding specified depth
562 {
563 public:
566  , m_Depth(x_depth) {}
567 protected:
568  virtual bool x_Allowed(TNodeType& node)
569  {
570  return ((*node).IDX().first <= m_Depth);
571  }
572 private:
573  int m_Depth;
574 };
575 
576 
577 /// Find all nodes within 'd' distance of the nodes 'node_ids'
578 /// If tree does not have distance information, return node_ids.
579 /// Traverse the tree both up and down (as if it were a graph) when
580 /// accumulating distance.
581 /// Avoid using recursion to eliminate possibility of stack overflow.
582 template<class TPhyloTree>
584  const vector<CPhyloTree::TID>& node_ids,
585  float d)
586 {
587  typedef typename CPhyloTree::TTreeIdx TTreeIdx;
588  typedef typename CPhyloTree::TNodeType TNodeType;
589  typedef pair<TTreeIdx, float> TNodeDist;
590 
591  // The current set of nodesnd their distance from the first node
592  // node_idx
593  vector<TNodeDist> node_distances;
595  set<CPhyloTree::TTreeIdx> visited_nodes;
596 
597  for (size_t i = 0; i < node_ids.size(); ++i) {
598  TTreeIdx node_idx = phylo_tree.FindNodeById(node_ids[i]);
599  if (node_idx != CPhyloTree::Null()) {
600  node_distances.push_back(TNodeDist(node_idx, 0.0f));
601  results.insert(node_idx);
602  visited_nodes.insert(node_idx);
603  }
604  }
605 
606  // Make sure tree has a distance parameter (it's not required)
607  // Also return if d==0 since that means we do not expand the neighborhood
608  if (!phylo_tree.GetFeatureDict().HasFeature("dist") || d <= 0.0f)
609  return results;
610 
611  while (node_distances.size() > 0) {
612  vector<TNodeDist> prev_node_distances = node_distances;
613 
614  node_distances.clear();
615 
616  // Add children and parent of nodes in prev_node_distances to results if
617  // they are not already in results and accumulated distance (for that node)
618  // is not greater than 'd'
619  for (size_t i = 0; i < prev_node_distances.size(); ++i) {
620  TNodeType& n = phylo_tree.GetNode(prev_node_distances[i].first);
621  float accumulated_dist = prev_node_distances[i].second;
622 
623  if (n.HasParent()) {
624  TTreeIdx parent_idx = n.GetParent();
625  float parent_dist = n.GetValue().GetDistance();
626  if (accumulated_dist + parent_dist <= d && visited_nodes.find(parent_idx) == visited_nodes.end()) {
627  node_distances.push_back(TNodeDist(parent_idx, accumulated_dist + parent_dist));
628  results.insert(parent_idx);
629  }
630  }
631 
632  TNodeType::TNodeList_I child_iter = n.GetChildren().begin();
633  for (; child_iter != n.GetChildren().end(); ++child_iter) {
634  TTreeIdx child_idx = *child_iter;
635  float child_dist = phylo_tree.GetNode(child_idx).GetValue().GetDistance();
636  if (accumulated_dist + child_dist <= d && visited_nodes.find(child_idx) == visited_nodes.end()) {
637  node_distances.push_back(TNodeDist(child_idx, accumulated_dist + child_dist));
638  results.insert(child_idx);
639  }
640  }
641 
642  visited_nodes.insert(prev_node_distances[i].first);
643  }
644  }
645 
646  return results;
647 }
648 
649 
650 /// Convert ASN.1 BioTree container to phylo tree
651 /// @param phylo_tree Ouput phylo tree
652 /// @param tree_container Input tree container
653 /// @param preserve_node_ids If true, node ids in the resulting phylo tree
654 /// will be the same is in the input tree container
655 ///
656 template<class TBioTreeContainer, class TPhyloTree>
657 void BioTreeConvertContainer2Tree(TPhyloTree& phylo_tree,
658  const TBioTreeContainer& tree_container,
659  CBioTreeFeatureDictionary* dictionary,
660  bool preserve_node_ids = true,
661  bool expand_all = false)
662 {
663  phylo_tree.Clear();
664 
665  int node_id = 1;
666 
667  // Convert feature dictionary
668 
669  typedef typename TBioTreeContainer::TFdict TContainerDict;
670 
671  CBioTreeFeatureDictionary& dict = phylo_tree.GetFeatureDict();
672  const TContainerDict& fd = tree_container.GetFdict();
673  const typename TContainerDict::Tdata& feat_list = fd.Get();
674  TBioTreeFeatureId expand_collapse_id = -1;
675  //TBioTreeFeatureId max_id = 0;
676 
677  ITERATE(typename TContainerDict::Tdata, it, feat_list) {
678  TBioTreeFeatureId fid = (*it)->GetId();
679  const string& fvalue = (*it)->GetName();
680  if (fvalue == "$NODE_COLLAPSED")
681  expand_collapse_id = fid;
682  //max_id = std::max(fid, max_id);
683 
684  dict.Register(fid, fvalue);
685  }
686 
687  // Vector allows us to remove unused features from dictionary. Really
688  // only important for "dist" which we want to remove from the dictinoary
689  // if it does not occur in any nodes. If we don't, we may default to
690  // distance-based layout of trees with no distance data. (If even 1 node has
691  // has 'dist' property, we keep it and assign 0 distance to all other nodes).
692  // --This has now been fixed via MakeDistanceSensitiveBioTreeContainer
693  //vector<bool> has_property(size_t(max_id+1), false);
694 
695  // convert tree data (nodes)
696  typedef typename TBioTreeContainer::TNodes TCNodeSet;
697  typedef typename TCNodeSet::Tdata TNodeList;
698  typedef typename TNodeList::value_type::element_type TCNode;
699 
700  const TNodeList node_list = tree_container.GetNodes().Get();
701 
702  std::map<TBioTreeNodeId, typename TPhyloTree::TTreeIdx> pmap;
703 
704  phylo_tree.Reserve(node_list.size());
705 
706  ITERATE(typename TNodeList, it, node_list) {
707  const CRef<TCNode>& cnode = *it;
708 
709  TBioTreeNodeId uid = cnode->GetId();
710 
711  typedef typename TPhyloTree::TNodeType TNodeType;
712  typedef typename TNodeType::TValueType TNodeValueType;
713 
714  TNodeValueType v;
715  if (preserve_node_ids) {
716  v.SetId(uid);
717  }
718 
719  typedef typename TCNode::TFeatures TCNodeFeatureSet;
720 
721  if (cnode->CanGetFeatures()) {
722  const TCNodeFeatureSet& fset = cnode->GetFeatures();
723 
724  const typename TCNodeFeatureSet::Tdata& flist = fset.Get();
725 
726  ITERATE(typename TCNodeFeatureSet::Tdata, fit, flist) {
727  unsigned int fid = (*fit)->GetFeatureid();
728  const string& fvalue = (*fit)->GetValue();
729 
730  // Should always be true unless tree was corrupted
731  //if (size_t(fid) < has_property.size())
732  // has_property[size_t(fid)] = true; //indicate property is in-use
733 
734  if (expand_all && fid == expand_collapse_id) {
735  v.GetBioTreeFeatureList().SetFeature(fid, "0");
736  continue;
737  }
738 
739  v.GetBioTreeFeatureList().SetFeature(fid, fvalue);
740  } // ITERATE
741  }
742 
743  if (cnode->CanGetParent()) {
744  TBioTreeNodeId parent_id = cnode->GetParent();
745  typename TPhyloTree::TTreeIdx parent_node_idx = pmap[parent_id];
746 
747  typename TPhyloTree::TTreeIdx node_idx = TPhyloTree::Null();
748 
749  if (parent_node_idx != TPhyloTree::Null()) {
750  node_idx = phylo_tree.AddNode();
751  phylo_tree[node_idx].SetValue(v);
752  phylo_tree.AddChild(parent_node_idx, node_idx);
753  if (!preserve_node_ids) {
754  phylo_tree[node_idx].GetValue().SetId(++node_id);
755  }
756  }
757  else {
758  NCBI_THROW(CException, eUnknown, "Parent not found");
759  }
760 
761  pmap[uid] = node_idx;
762  } else {
763  typename TPhyloTree::TTreeIdx node_idx = phylo_tree.AddNode();
764  phylo_tree[node_idx].SetValue(v);
765  phylo_tree.SetRootIdx(node_idx);
766 
767  if (!preserve_node_ids) {
768  phylo_tree[node_idx].GetValue().SetId(++node_id);
769  }
770  pmap[uid] = node_idx;
771  }
772  } // ITERATE TNodeList
773 
774  // Problem of empty distance property is now taken care of in Newick to Biotree conversion
775  // function (MakeDistanceSensitiveBioTreeContainer)
776  //for (size_t i = 0; i < has_property.size(); ++i) {
777  // if (!has_property[i] && dict.HasFeature(TBioTreeFeatureId(i))) {
778  // dict.Unregister(TBioTreeFeatureId(i));
779  // }
780  //}
781 }
782 
783 
784 // --------------------------------------------------------------------------
785 
786 /// Visitor functor to convert phylo tree nodes to ASN.1 BioTree container
787 ///
788 /// @internal
789 template<class TBioTreeContainer, class TTreeType>
791 {
792 protected:
793  typedef typename TTreeType::TNodeType TTreeNodeType;
794  typedef typename TTreeType::TTreeIdx TTreeIdx;
795  typedef typename TTreeNodeType::TValueType TNodeValueType;
796 
797  typedef typename TBioTreeContainer::TNodes TCNodeSet;
798  typedef typename TCNodeSet::Tdata TNodeList;
799  typedef typename TNodeList::value_type::element_type TCNode;
800  typedef typename TCNode::TFeatures TCNodeFeatureSet;
801  typedef typename TCNodeFeatureSet::Tdata TNodeFeatureList;
802  typedef typename
803  TNodeFeatureList::value_type::element_type TCNodeFeature;
804 public:
805  CTreeConvert2ContainerFunc(TBioTreeContainer* tree_container,
806  TTreeIdx root_idx)
807  : m_Container(tree_container)
808  , m_RootIdx(root_idx)
809  {
810  m_NodeList = &(tree_container->SetNodes().Set());
811  }
812 
814  operator()(TTreeType& tree, TTreeIdx node_idx, int delta_level)
815  {
816  if (delta_level < 0) {
817  return eTreeTraverse;
818  }
819 
820  TTreeNodeType& node = tree[node_idx];
821 
822  const TNodeValueType& v = node.GetValue();
823  TBioTreeNodeId uid = v.GetId();
824 
825  CRef<TCNode> cnode(new TCNode);
826  cnode->SetId(uid);
827 
828  if (node_idx != m_RootIdx && node.HasParent()) {
829  const TTreeNodeType& node_parent =
830  (TTreeNodeType&) tree.GetParent(node);
831  cnode->SetParent(node_parent.GetValue().GetId());
832  }
833 
834  typedef typename
835  TNodeValueType::TNodeFeaturesType::TFeatureList TFList;
836  const TFList& flist = v.GetBioTreeFeatureList().GetFeatureList();
837 
838  if (!flist.empty()) {
839 
840  TCNodeFeatureSet& fset = cnode->SetFeatures();
841 
842  ITERATE(typename TFList, it, flist) {
843  TBioTreeFeatureId fid = it->id;
844  const string fvalue = it->value;
845 
847  cfeat->SetFeatureid(fid);
848  cfeat->SetValue(fvalue);
849 
850  fset.Set().push_back(cfeat);
851  } // ITERATE
852  }
853 
854  m_NodeList->push_back(cnode);
855 
856  return eTreeTraverse;
857  }
858 
859 private:
860  TBioTreeContainer* m_Container;
863 };
864 
865 template<class TBioTreeContainer, class TTreeType>
867 {
868 protected:
869  typedef typename TTreeType::TNodeType TTreeNodeType;
870  typedef typename TTreeType::TTreeIdx TTreeIdx;
871  typedef typename TTreeNodeType::TValueType TNodeValueType;
872 
873  typedef typename TBioTreeContainer::TNodes TCNodeSet;
874  typedef typename TCNodeSet::Tdata TNodeList;
875  typedef typename TNodeList::value_type::element_type TCNode;
876  typedef typename TCNode::TFeatures TCNodeFeatureSet;
877  typedef typename TCNodeFeatureSet::Tdata TNodeFeatureList;
878  typedef typename
879  TNodeFeatureList::value_type::element_type TCNodeFeature;
880 public:
881  CTreeConvertSelected2ContainerFunc(TBioTreeContainer* tree_container,
882  TTreeIdx root_idx)
883  : m_Container(tree_container)
884  , m_RootIdx(root_idx)
885  {
886  m_NodeList = &(tree_container->SetNodes().Set());
887  }
888 
890  operator()(TTreeType& tree, TTreeIdx node_idx, int delta_level)
891  {
892  if (delta_level < 0) {
893  return eTreeTraverse;
894  }
895 
896  TTreeNodeType& node = tree[node_idx];
897  if (!((*node).GetSelectedState() == CPhyloNodeData::eSelected) &&
898  !((*node).GetSelectedState() == CPhyloNodeData::eTraced) &&
899  !((*node).GetSelectedState() == CPhyloNodeData::eShared))
900  return eTreeTraverseStepOver;
901 
902  const TNodeValueType& v = node.GetValue();
903  TBioTreeNodeId uid = v.GetId();
904 
905  CRef<TCNode> cnode(new TCNode);
906  cnode->SetId(uid);
907 
908  if (node_idx != m_RootIdx && node.HasParent()) {
909  const TTreeNodeType& node_parent =
910  (TTreeNodeType&)tree.GetParent(node);
911  cnode->SetParent(node_parent.GetValue().GetId());
912  }
913 
914  typedef typename
915  TNodeValueType::TNodeFeaturesType::TFeatureList TFList;
916  const TFList& flist = v.GetBioTreeFeatureList().GetFeatureList();
917 
918  if (!flist.empty()) {
919 
920  TCNodeFeatureSet& fset = cnode->SetFeatures();
921 
922  ITERATE(typename TFList, it, flist) {
923  TBioTreeFeatureId fid = it->id;
924  const string fvalue = it->value;
925 
927  cfeat->SetFeatureid(fid);
928  cfeat->SetValue(fvalue);
929 
930  fset.Set().push_back(cfeat);
931  } // ITERATE
932  }
933 
934  m_NodeList->push_back(cnode);
935 
936  return eTreeTraverse;
937  }
938 
939 private:
940  TBioTreeContainer* m_Container;
943 };
944 
945 template<class TBioTreeContainer, class TTreeType>
947 {
948 protected:
949  typedef typename TTreeType::TNodeType TTreeNodeType;
950  typedef typename TTreeType::TTreeIdx TTreeIdx;
951  typedef typename TTreeNodeType::TValueType TNodeValueType;
952 
953  typedef typename TBioTreeContainer::TNodes TCNodeSet;
954  typedef typename TCNodeSet::Tdata TNodeList;
955  typedef typename TNodeList::value_type::element_type TCNode;
956  typedef typename TCNode::TFeatures TCNodeFeatureSet;
957  typedef typename TCNodeFeatureSet::Tdata TNodeFeatureList;
958  typedef typename
959  TNodeFeatureList::value_type::element_type TCNodeFeature;
960 public:
962  TBioTreeContainer* tree_container,
963  TTreeIdx root_idx)
964  : m_Container(tree_container)
965  , m_RootIdx(root_idx)
966  , m_ParentDist(0)
967  , m_HasDist(false)
968  , m_DistFeatureId(-1)
969  , m_ParentID(-1)
971  {
972  m_NodeList = &(tree_container->SetNodes().Set());
973  if (tree.GetFeatureDict().HasFeature("dist")) {
974  m_HasDist = true;
975  m_DistFeatureId = tree.GetFeatureDict().GetId("dist");
976  }
977  }
978 
980  operator()(TTreeType& tree, TTreeIdx node_idx, int delta_level)
981  {
982  if (delta_level < 0) {
983  m_ParentDist = 0.0f;
984  m_ParentID = -1;
985  m_SkippedParent = false;
986  return eTreeTraverse;
987  }
988 
989  TTreeNodeType& node = tree[node_idx];
990 
991  const TNodeValueType& v = node.GetValue();
992  TBioTreeNodeId uid = v.GetId();
993 
994  // If this node only has one child, record the parent ID
995  // (unless its parent also only had a single child, and
996  // then skip over it (visit its children recursively until
997  // a leaf or non-single child is found)
998  if (node.GetChildren().size() == 1) {
999  if (m_HasDist) {
1000  m_ParentDist += v.GetDistance();
1001  }
1002  if (!m_SkippedParent && node.HasParent()) {
1003  const TTreeNodeType& node_parent =
1004  (TTreeNodeType&)tree.GetParent(node);
1005  m_ParentID = node_parent.GetValue().GetId();
1006  }
1007  m_SkippedParent = true;
1008  return eTreeTraverse;
1009  }
1010 
1011  CRef<TCNode> cnode(new TCNode);
1012  cnode->SetId(uid);
1013 
1014  if (node_idx != m_RootIdx && node.HasParent()) {
1015  if (m_SkippedParent) {
1016  // If m_ParentID is -1, then the skipped parent
1017  // was the root so we do not set ay value for
1018  // cnode->SetParent(..) in this case
1019  if (m_ParentID != -1) {
1020  cnode->SetParent(m_ParentID);
1021  }
1022  }
1023  else {
1024  const TTreeNodeType& node_parent =
1025  (TTreeNodeType&)tree.GetParent(node);
1026  cnode->SetParent(node_parent.GetValue().GetId());
1027  }
1028  }
1029 
1030  typedef typename
1031  TNodeValueType::TNodeFeaturesType::TFeatureList TFList;
1032  const TFList& flist = v.GetBioTreeFeatureList().GetFeatureList();
1033 
1034  if (!flist.empty()) {
1035 
1036  TCNodeFeatureSet& fset = cnode->SetFeatures();
1037 
1038  ITERATE(typename TFList, it, flist) {
1039  TBioTreeFeatureId fid = it->id;
1040  string fvalue = it->value;
1041 
1042  // We may update distances here when we skip parents (removing them from
1043  // the tree) we want to retain their distance information
1044  if (fid == m_DistFeatureId){
1045  if (!fvalue.empty()) {
1046  try {
1047  double ddist = NStr::StringToDouble(fvalue);
1048  if (ddist < 0.0)
1049  ddist = 0.0;
1050  ddist += (double)m_ParentDist;
1051  fvalue = NStr::DoubleToString(ddist);
1052  }
1053  catch (std::exception&) {}
1054  }
1055  }
1056 
1058  cfeat->SetFeatureid(fid);
1059  cfeat->SetValue(fvalue);
1060 
1061  fset.Set().push_back(cfeat);
1062  } // ITERATE
1063  }
1064 
1065  m_NodeList->push_back(cnode);
1066 
1067  m_ParentDist = 0.0f;
1068  m_ParentID = -1;
1069  m_SkippedParent = false;
1070 
1071  return eTreeTraverse;
1072  }
1073 
1074 private:
1075  TBioTreeContainer* m_Container;
1083 };
1084 
1085 
1086 /// Convert tree to ASN.1 BioTree container
1087 ///
1088 template<class TBioTreeContainer, class TPhyloTree>
1089 void TreeConvert2Container(TBioTreeContainer& tree_container,
1090  TPhyloTree& phylo_tree,
1091  typename TPhyloTree::TTreeIdx node_idx=TPhyloTree::Null())
1092 {
1093  // Convert feature dictionary
1094 
1095  typedef typename TBioTreeContainer::TFdict TContainerDict;
1096 
1097  const CBioTreeFeatureDictionary& dict = phylo_tree.GetFeatureDict();
1098  const CBioTreeFeatureDictionary::TFeatureDict& dict_map =
1099  dict.GetFeatureDict();
1100 
1101  TContainerDict& fd = tree_container.SetFdict();
1102  typename TContainerDict::Tdata& feat_list = fd.Set();
1103  typedef
1104  typename TContainerDict::Tdata::value_type::element_type TCFeatureDescr;
1105 
1107  TBioTreeFeatureId fid = it->first;
1108  const string& fvalue = it->second;
1109 
1110  {{
1111  CRef<TCFeatureDescr> d(new TCFeatureDescr);
1112  d->SetId(fid);
1113  d->SetName(fvalue);
1114 
1115  feat_list.push_back(d);
1116  }}
1117  } // ITERATE
1118 
1120  func(&tree_container, node_idx);
1121 
1122  if (node_idx==TPhyloTree::Null())
1123  TreeDepthFirst(phylo_tree, func);
1124  else
1125  TreeDepthFirst(phylo_tree, node_idx, func);
1126 }
1127 
1128 /// Convert selected nodes from tree to ASN.1 BioTree container
1129 ///
1130 template<class TBioTreeContainer, class TPhyloTree>
1131 void TreeConvertSelected2Container(TBioTreeContainer& tree_container,
1132  TPhyloTree& phylo_tree,
1133  typename TPhyloTree::TTreeIdx node_idx = TPhyloTree::Null())
1134 {
1135  // Convert feature dictionary
1136 
1137  typedef typename TBioTreeContainer::TFdict TContainerDict;
1138 
1139  const CBioTreeFeatureDictionary& dict = phylo_tree.GetFeatureDict();
1140  const CBioTreeFeatureDictionary::TFeatureDict& dict_map =
1141  dict.GetFeatureDict();
1142 
1143  TContainerDict& fd = tree_container.SetFdict();
1144  typename TContainerDict::Tdata& feat_list = fd.Set();
1145  typedef
1146  typename TContainerDict::Tdata::value_type::element_type TCFeatureDescr;
1147 
1149  TBioTreeFeatureId fid = it->first;
1150  const string& fvalue = it->second;
1151 
1152  {{
1153  CRef<TCFeatureDescr> d(new TCFeatureDescr);
1154  d->SetId(fid);
1155  d->SetName(fvalue);
1156 
1157  feat_list.push_back(d);
1158  }}
1159  } // ITERATE
1160 
1162  func(&tree_container, node_idx);
1163 
1164  if (node_idx == TPhyloTree::Null())
1165  TreeDepthFirst(phylo_tree, func);
1166  else
1167  TreeDepthFirst(phylo_tree, node_idx, func);
1168 }
1169 
1170 /// Convert selected nodes from tree to ASN.1 BioTree container
1171 ///
1172 template<class TBioTreeContainer, class TPhyloTree>
1173 void TreeConvertNonSingleChild2Container(TBioTreeContainer& tree_container,
1174  TPhyloTree& phylo_tree,
1175  typename TPhyloTree::TTreeIdx node_idx = TPhyloTree::Null())
1176 {
1177  // Convert feature dictionary
1178 
1179  typedef typename TBioTreeContainer::TFdict TContainerDict;
1180 
1181  const CBioTreeFeatureDictionary& dict = phylo_tree.GetFeatureDict();
1182  const CBioTreeFeatureDictionary::TFeatureDict& dict_map =
1183  dict.GetFeatureDict();
1184 
1185  TContainerDict& fd = tree_container.SetFdict();
1186  typename TContainerDict::Tdata& feat_list = fd.Set();
1187  typedef
1188  typename TContainerDict::Tdata::value_type::element_type TCFeatureDescr;
1189 
1191  TBioTreeFeatureId fid = it->first;
1192  const string& fvalue = it->second;
1193 
1194  {{
1195  CRef<TCFeatureDescr> d(new TCFeatureDescr);
1196  d->SetId(fid);
1197  d->SetName(fvalue);
1198 
1199  feat_list.push_back(d);
1200  }}
1201  } // ITERATE
1202 
1204  func(phylo_tree, &tree_container, node_idx);
1205 
1206  if (node_idx == TPhyloTree::Null())
1207  TreeDepthFirst(phylo_tree, func);
1208  else
1209  TreeDepthFirst(phylo_tree, node_idx, func);
1210 }
1211 
1212 /// Visitor functor to convert phylo tree nodes to ASN.1 BioTree container
1213 /// not including all features
1214 /// @internal
1215 template<class TBioTreeContainer, class TTreeType>
1217 {
1218 protected:
1219  typedef typename TTreeType::TNodeType TTreeNodeType;
1220  typedef typename TTreeType::TTreeIdx TTreeIdx;
1221  typedef typename TTreeNodeType::TValueType TNodeValueType;
1222 
1223  typedef typename TBioTreeContainer::TNodes TCNodeSet;
1224  typedef typename TCNodeSet::Tdata TNodeList;
1225  typedef typename TNodeList::value_type::element_type TCNode;
1226  typedef typename TCNode::TFeatures TCNodeFeatureSet;
1227  typedef typename TCNodeFeatureSet::Tdata TNodeFeatureList;
1228  typedef typename
1229  TNodeFeatureList::value_type::element_type TCNodeFeature;
1230 public:
1231  CTreeConvert2ContainerPartialFunc(TBioTreeContainer* tree_container,
1232  TTreeIdx root_idx,
1233  const CBioTreeFeatureDictionary& return_dict)
1234  : m_Container(tree_container)
1235  , m_RootIdx(root_idx)
1236  , m_ReturnDict(return_dict)
1237  {
1238  m_NodeList = &(tree_container->SetNodes().Set());
1239  }
1240 
1242  operator()(TTreeType& tree, TTreeIdx node_idx, int delta_level)
1243  {
1244  if (delta_level < 0) {
1245  return eTreeTraverse;
1246  }
1247 
1248  TTreeNodeType& node = tree[node_idx];
1249 
1250  const TNodeValueType& v = node.GetValue();
1251  TBioTreeNodeId uid = v.GetId();
1252 
1253  CRef<TCNode> cnode(new TCNode);
1254  cnode->SetId(uid);
1255 
1256  if (node_idx != m_RootIdx && node.HasParent()) {
1257  const TTreeNodeType& node_parent =
1258  (TTreeNodeType&) tree.GetParent(node);
1259  cnode->SetParent(node_parent.GetValue().GetId());
1260  }
1261 
1262  typedef typename
1263  TNodeValueType::TNodeFeaturesType::TFeatureList TFList;
1264  const TFList& flist = v.GetBioTreeFeatureList().GetFeatureList();
1265 
1266  if (!flist.empty()) {
1267 
1268  TCNodeFeatureSet& fset = cnode->SetFeatures();
1269 
1270  // Only get features already in the dictionary. That allows us to export
1271  // trees with restricted sets of features (TreeConvert2ContainerPartial).
1272  ITERATE(typename TFList, it, flist) {
1273  TBioTreeFeatureId fid = it->id;
1274  const string fvalue = it->value;
1275 
1276  if (m_ReturnDict.HasFeature(fid)) {
1278  cfeat->SetFeatureid(fid);
1279  cfeat->SetValue(fvalue);
1280 
1281  fset.Set().push_back(cfeat);
1282  }
1283  } // ITERATE
1284  }
1285 
1286  m_NodeList->push_back(cnode);
1287 
1288  return eTreeTraverse;
1289  }
1290 
1291 private:
1292  TBioTreeContainer* m_Container;
1296 };
1297 
1298 /// Convert tree to ASN.1 BioTree container but only include the requested features
1299 ///
1300 template<class TBioTreeContainer, class TPhyloTree>
1301 void TreeConvert2ContainerPartial(TBioTreeContainer& tree_container,
1302  TPhyloTree& phylo_tree,
1303  const set<string>& features,
1304  typename TPhyloTree::TTreeIdx node_idx = TPhyloTree::Null())
1305 {
1306  // Convert feature dictionary
1307  typedef typename TBioTreeContainer::TFdict TContainerDict;
1308 
1309  const CBioTreeFeatureDictionary& dict = phylo_tree.GetFeatureDict();
1310  const CBioTreeFeatureDictionary::TFeatureDict& dict_map =
1311  dict.GetFeatureDict();
1312  CBioTreeFeatureDictionary return_dict;
1313 
1314  TContainerDict& fd = tree_container.SetFdict();
1315  typename TContainerDict::Tdata& feat_list = fd.Set();
1316  typedef
1317  typename TContainerDict::Tdata::value_type::element_type TCFeatureDescr;
1318 
1320  TBioTreeFeatureId fid = it->first;
1321  const string& fvalue = it->second;
1322  if (features.find(fvalue) != features.end()) {
1323  CRef<TCFeatureDescr> d(new TCFeatureDescr);
1324  d->SetId(fid);
1325  d->SetName(fvalue);
1326  return_dict.Register(fid, fvalue);
1327 
1328  feat_list.push_back(d);
1329  }
1330  } // ITERATE
1331 
1333  func(&tree_container, node_idx, return_dict);
1334 
1335  if (node_idx == TPhyloTree::Null())
1336  TreeDepthFirst(phylo_tree, func);
1337  else
1338  TreeDepthFirst(phylo_tree, node_idx, func);
1339 }
1340 
1341 /// Convert CBioTreeFeatureDictionary to ASN.1 BioTree dictionary
1342 ///
1343 template<class TContainerDict>
1344 void DictConvert2ContainerFeatureDict(TContainerDict& fd,
1346 {
1347  // Convert feature dictionary
1348  const CBioTreeFeatureDictionary::TFeatureDict& dict_map =
1349  dict.GetFeatureDict();
1350 
1351  typename TContainerDict::Tdata& feat_list = fd.Set();
1352  typedef typename TContainerDict::Tdata::value_type::element_type TCFeatureDescr;
1353 
1355  TBioTreeFeatureId fid = it->first;
1356  const string& fvalue = it->second;
1357 
1358  {{
1359  CRef<TCFeatureDescr> d(new TCFeatureDescr);
1360  d->SetId(fid);
1361  d->SetName(fvalue);
1362 
1363  feat_list.push_back(d);
1364  }}
1365  } // ITERATE
1366 }
1367 
1368 
1370 
1371 #endif
Things for representing and manipulating bio trees.
Feature dictionary.
Definition: bio_tree.hpp:176
Template class to create a table with custom row-column access.
Definition: ncbi_table.hpp:66
CObject –.
Definition: ncbiobj.hpp:180
objects::CNode::TId TID
CRgbaGradColorTable * m_ColorTable
void x_UpdateProperties(TNodeType &node, int row_idx)
Updates node properties using values from m_AttrTable.
void SetClusters(const TClusterHash &clst)
virtual ETreeTraverseCode x_OnStepDown(TTreeIdx x_node)
CPhyloTreeNode::TTreeIdx m_CollapsedParentIdx
CPhyloTreeCalculator(TTreeType *tree, CRgbaGradColorTable *color_table)
map< TClusterID, vector< TTreeIdx > > TClusterHash
virtual ETreeTraverseCode x_OnStep(TTreeIdx x_node, int delta)
void SetLabelFormat(string labelFmt)
void SetAttrTable(const TAttrTable &attr)
virtual ETreeTraverseCode x_OnStepRight(TTreeIdx x_node)
TBioTreeFeatureId m_AttrKeyId
const TClusterHash & GetClusters()
string m_LabelFormat
label calculation
const TAttrTable * m_AttrTable
Attributes with seq-ids optionally provided to update tree properties.
CPhyloTree::TClusterID TClusterID
TClusterID GetMaxClusterID() const
CNcbiTable< string, unsigned, string > TAttrTable
void Init(CRgbaGradColorTable *ct)
vector< AttrKey > m_AttrKeys
Mapping for efficient lookup of seq-ids in m_AttrTable.
virtual ETreeTraverseCode x_OnStepLeft(TTreeIdx x_node)
TTreeIdx m_MaxDistNode
Index of node that is furthest from the root.
vector< float > & GetDistances()
virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta)
CPhyloTreeDistFromRoot(TTreeType *tree)
vector< float > m_Distances
Distance of each node from root.
virtual bool x_Allowed(TNodeType &node)
CPhyloTreeFilter_Depth(TTreeType *tree, int x_depth)
virtual bool x_Allowed(TNodeType &node)
CPhyloTreeFilter_Distance(TTreeType *tree, float x_dist)
CPhyloTreeFilter_Export(TTreeType *tree)
virtual bool x_Allowed(TNodeType &node)
virtual bool x_Allowed(TNodeType &node)
CPhyloTreeFilter_Selector(TTreeType *tree)
CPhyloTreeLabelRange(TTreeType *tree, bool x_order)
virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta)
vector< pair< string, string > > & GetLabelRanges()
vector< pair< string, string > > m_LabelRanges
Min and max label values (according to lexicographic.
For each node, this returns the maximum distances of any of its children (recursively searched) from ...
vector< float > m_Distances
Max distace of any child of a node from the root, saved in same order as node array in tree.
virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta)
vector< float > & GetDistances()
CPhyloTreeMaxChildDist(TTreeType *tree)
float m_MaxDist
Keep track of overall max and min distances.
For each node this finds the maximum distance of any of its immediate (not recursively searched) chil...
CPhyloTreeMaxDirectChildDist(TTreeType *tree, SCollapsable *collapsable_func=new SCollapsable())
virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta)
CRef< SCollapsable > m_CheckCollapseFunc
vector< SChildMaxDist > m_Distances
Max distace of any direct child of a node from the root, saved in same order as node array in tree.
vector< SChildMaxDist > & GetDistances()
virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta)
CPhyloNodeData::TID GetMaxId() const
CPhyloTreeMaxIdCalculator(TTreeType *tree)
CPhyloTreeMidpointDist(TTreeType *tree, vector< float > &distances, TTreeIdx max_dist_node_idx)
virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta)
float m_MaxDist
Total distance along m_MaxPath.
vector< TTreeIdx > m_MaxDistPathToRoot
vector< TTreeIdx > m_SortedMaxDistPathToRoot
vector< float > m_Distances
Distance of each node from root node.
void GetLongest(vector< TTreeIdx > &path, float &length)
TTreeIdx m_MaxDistNode
Node at greatest distance from root, its distance and vector of nodes from root to m_MaxDistNode (sor...
vector< TTreeIdx > m_MaxPath
Path (set of nodes) that is the longest path in the tree.
float m_LeafMidpoint
Index of leaf at center of subtree (leaves in subtree/2)
TTreeIdx m_PriorityLeafIdx
Leaf with highest priority number.
TTreeIdx GetMaxPriorityNode() const
virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta)
size_t m_MaxPriorityLeafNum
Leaf index of node with m_MaxPriority.
CPhyloTreePriorityNode(TTreeType *tree, TTreeIdx node_idx)
void Init(TTreeIdx node_idx)
int m_MaxPriority
Max priority value found in priority field in subtree.
TBioTreeFeatureId m_PriorityId
Id of priority feature in tree.
size_t m_LeafCount
Current leaf count (as we iterate over the subtree)
const TModelRect & GetRect() const
virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta)
CPhyloTreeRectCalculator(TTreeType *tree)
virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta)
const vector< pair< string, string > > & m_LabelRanges
CPhyloTreeSorterLabelRange(TTreeType *tree, const vector< pair< string, string > > &label_ranges, bool x_order)
CPhyloTreeSorterLabel(TTreeType *tree, bool x_order)
virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta)
CPhyloTreeSorterSubtreeDist(TTreeType *tree, const vector< float > &distances, bool x_order)
virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta)
const vector< float > & m_Distances
CPhyloTreeSorter(TTreeType *tree, bool x_order)
virtual ETreeTraverseCode x_OnStep(TTreeIdx node_idx, int delta)
Tree subclass also has functions and data needed for rendering and selection.
Definition: phylo_tree.hpp:52
CPhyloNodeData::TClusterID TClusterID
Definition: phylo_tree.hpp:54
CRgbaGradColorTable Provides a storage for colors (to eliminate color creation overhead) and Function...
Visitor functor to convert phylo tree nodes to ASN.1 BioTree container.
ETreeTraverseCode operator()(TTreeType &tree, TTreeIdx node_idx, int delta_level)
TNodeFeatureList::value_type::element_type TCNodeFeature
TCNodeFeatureSet::Tdata TNodeFeatureList
TTreeNodeType::TValueType TNodeValueType
TBioTreeContainer::TNodes TCNodeSet
CTreeConvert2ContainerFunc(TBioTreeContainer *tree_container, TTreeIdx root_idx)
TNodeList::value_type::element_type TCNode
TTreeType::TNodeType TTreeNodeType
Visitor functor to convert phylo tree nodes to ASN.1 BioTree container not including all features.
TNodeFeatureList::value_type::element_type TCNodeFeature
ETreeTraverseCode operator()(TTreeType &tree, TTreeIdx node_idx, int delta_level)
const CBioTreeFeatureDictionary & m_ReturnDict
TTreeNodeType::TValueType TNodeValueType
TNodeList::value_type::element_type TCNode
CTreeConvert2ContainerPartialFunc(TBioTreeContainer *tree_container, TTreeIdx root_idx, const CBioTreeFeatureDictionary &return_dict)
CTreeConvertNonSingleChild2ContainerFunc(TTreeType &tree, TBioTreeContainer *tree_container, TTreeIdx root_idx)
TNodeList::value_type::element_type TCNode
ETreeTraverseCode operator()(TTreeType &tree, TTreeIdx node_idx, int delta_level)
TNodeFeatureList::value_type::element_type TCNodeFeature
TNodeList::value_type::element_type TCNode
CTreeConvertSelected2ContainerFunc(TBioTreeContainer *tree_container, TTreeIdx root_idx)
TNodeFeatureList::value_type::element_type TCNodeFeature
TTreeNodeType::TValueType TNodeValueType
ETreeTraverseCode operator()(TTreeType &tree, TTreeIdx node_idx, int delta_level)
TNodeList & GetChildren()
Return the indices of this node's child nodes.
Definition: tree_model.hpp:126
static TTreeIdx Null()
Static function that returns the null value.
Definition: tree_model.hpp:636
static TTreeIdx Null()
Return the index value that represents a NULL node.
Definition: tree_model.hpp:678
TNodeType & GetNode(TTreeIdx idx)
Return a reference to the node at the given index.
Definition: tree_model.hpp:207
virtual bool x_Allowed(TNodeType &)
IPhyloTreeFilter(TTreeType *tree)
virtual ETreeTraverseCode x_OnStep(TTreeIdx x_node, int delta)
vector< TTreeIdx > m_TreeStack
virtual ETreeTraverseCode x_OnStepDown(TTreeIdx x_node)
ETreeTraverseCode operator()(TTreeType &tree, TTreeIdx tree_node, int delta)
virtual ETreeTraverseCode x_OnStep(TTreeIdx x_node, int delta)
virtual ETreeTraverseCode x_OnStepRight(TTreeIdx x_node)
IPhyloTreeVisitor(TTreeType *tree)
CPhyloTree::TTreeIdx TTreeIdx
CPhyloTree::TNodeType TNodeType
virtual ETreeTraverseCode x_OnStepLeft(TTreeIdx x_node)
Definition: map.hpp:338
Definition: set.hpp:45
iterator_bool insert(const value_type &val)
Definition: set.hpp:149
void clear()
Definition: set.hpp:153
const_iterator find(const key_type &key) const
Definition: set.hpp:137
const_iterator end() const
Definition: set.hpp:136
Include a standard set of the NCBI C++ Toolkit most basic headers.
#define false
Definition: bool.h:36
static DLIST_TYPE *DLIST_NAME() first(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:46
#define ITERATE(Type, Var, Cont)
ITERATE macro to sequence through container elements.
Definition: ncbimisc.hpp:815
#define NCBI_THROW(exception_class, err_code, message)
Generic macro to throw an exception, given the exception class, error code and message string.
Definition: ncbiexpt.hpp:704
@ eUnknown
Definition: app_popup.hpp:72
void Reset(void)
Reset reference object.
Definition: ncbiobj.hpp:773
bool IsNull(void) const THROWS_NONE
Check if pointer is null – same effect as Empty().
Definition: ncbiobj.hpp:735
#define numeric_limits
Pre-declaration of the "numeric_limits<>" template Forcibly overrides (using preprocessor) the origin...
Definition: ncbi_limits.hpp:92
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
static string DoubleToString(double value, int precision=-1, TNumToStringFlags flags=0)
Convert double to string.
Definition: ncbistr.hpp:5187
static double StringToDouble(const CTempStringEx str, TStringToNumFlags flags=0)
Convert string to double.
Definition: ncbistr.cpp:1387
ETreeTraverseCode
Tree traverse code returned by the traverse predicate function.
Definition: ncbi_tree.hpp:51
unsigned int TBioTreeNodeId
Tree node id. Every node has its unique id in the tree.
Definition: bio_tree.hpp:63
unsigned int TBioTreeFeatureId
Feature Id.
Definition: bio_tree.hpp:60
TBioTreeFeatureId Register(const string &feature_name)
Register new feature, return its id.
Definition: bio_tree.cpp:160
bool HasFeature(const string &feature_name) const
Check if feature is listed in the dictionary.
Definition: bio_tree.cpp:146
const TFeatureDict & GetFeatureDict() const
Get reference on the internal map.
Definition: bio_tree.hpp:219
@ eTreeTraverse
Keep traversal.
Definition: ncbi_tree.hpp:52
@ eTreeTraverseStepOver
Do not traverse current node (pick the next one)
Definition: ncbi_tree.hpp:54
int i
yy_size_t n
constexpr auto sort(_Init &&init)
Portable reference counted smart and weak pointers using CWeakRef, CRef, CObject and CObjectEx.
T max(T x_, T y_)
Int4 delta(size_t dimension_, const Int4 *score_)
void TreeConvertNonSingleChild2Container(TBioTreeContainer &tree_container, TPhyloTree &phylo_tree, typename TPhyloTree::TTreeIdx node_idx=TPhyloTree::Null())
Convert selected nodes from tree to ASN.1 BioTree container.
void TreeConvert2Container(TBioTreeContainer &tree_container, TPhyloTree &phylo_tree, typename TPhyloTree::TTreeIdx node_idx=TPhyloTree::Null())
Convert tree to ASN.1 BioTree container.
void TreeConvertSelected2Container(TBioTreeContainer &tree_container, TPhyloTree &phylo_tree, typename TPhyloTree::TTreeIdx node_idx=TPhyloTree::Null())
Convert selected nodes from tree to ASN.1 BioTree container.
void TreeConvert2ContainerPartial(TBioTreeContainer &tree_container, TPhyloTree &phylo_tree, const set< string > &features, typename TPhyloTree::TTreeIdx node_idx=TPhyloTree::Null())
Convert tree to ASN.1 BioTree container but only include the requested features.
void BioTreeConvertContainer2Tree(TPhyloTree &phylo_tree, const TBioTreeContainer &tree_container, CBioTreeFeatureDictionary *dictionary, bool preserve_node_ids=true, bool expand_all=false)
Convert ASN.1 BioTree container to phylo tree.
set< CPhyloTree::TTreeIdx > GetTreeNeighborhood(TPhyloTree &phylo_tree, const vector< CPhyloTree::TID > &node_ids, float d)
Find all nodes within 'd' distance of the nodes 'node_ids' If tree does not have distance information...
void DictConvert2ContainerFeatureDict(TContainerDict &fd, CBioTreeFeatureDictionary &dict)
Convert CBioTreeFeatureDictionary to ASN.1 BioTree dictionary.
Structure allows us to more efficiently store and look up keys (usually seq-ids) in m_AttrTable.
AttrKey(const string &id, unsigned int idx)
bool operator<(const AttrKey &rhs) const
Sort keys on seq-id string value.
SChildMaxDist(TTreeIdx idx, float dist)
bool operator<(const SChildMaxDist &rhs) const
Sort keys on seq-id string value.
virtual bool operator()(const CPhyloTreeNode &n)
Fun TreeDepthFirst(TTreeModel &tree_model, typename TTreeModel::TTreeIdx node_idx, Fun func)
Depth-first tree traversal algorithm.
Definition: tree_model.hpp:355
size_t TTreeIdx
Bi-directionaly linked N way tree allocated in a contiguous memory block.
Definition: tree_model.hpp:48
Modified on Tue May 21 11:00:48 2024 by modify_doxy.py rev. 669887