IMP  2.1.0
The Integrative Modeling Platform
merge_tree_utils.h
Go to the documentation of this file.
1 /**
2  * \file multifit/merge_tree_utils.h
3  *
4  * Copyright 2007-2013 IMP Inventors. All rights reserved.
5  */
6 
7 #ifndef IMPMULTIFIT_MERGE_TREE_UTILS_H
8 #define IMPMULTIFIT_MERGE_TREE_UTILS_H
9 
10 #include <boost/graph/adjacency_matrix.hpp>
11 #include <boost/graph/adjacency_list.hpp>
12 #include <boost/pending/disjoint_sets.hpp>
13 #include <boost/graph/graph_utility.hpp>
14 #include <IMP/multifit/multifit_config.h>
15 #include <IMP/atom/Hierarchy.h>
16 #include <IMP/base/map.h>
17 #include <boost/graph/kruskal_min_spanning_tree.hpp>
18 #include <boost/graph/prim_minimum_spanning_tree.hpp>
19 
20 IMPMULTIFIT_BEGIN_NAMESPACE
21 
22 namespace MTU {
23  typedef boost::adjacency_matrix<boost::undirectedS, boost::no_property,
24  boost::property<boost::edge_weight_t, double>
26  typedef boost::graph_traits<DependencyGraph>::edge_descriptor DGEdge;
27  typedef DependencyGraph::edge_property_type DGWeight;
28  typedef boost::graph_traits<DependencyGraph>::vertex_descriptor DGVertex;
29  typedef base::map<kernel::Particle *, DGVertex> PVMAP;
30  typedef base::map<DGVertex,Particle *> VPMAP;
31 };
32 
33 //! A simple Restraint that always returns a score of zero.
34 class IMPMULTIFITEXPORT DummyRestraint : public kernel::Restraint {
35 public:
37  kernel::Restraint(a->get_model(), "DummyRestraint%1%"), p1_(a),p2_(b){}
38  virtual double
39  unprotected_evaluate(IMP::kernel::DerivativeAccumulator *accum)
40  const IMP_OVERRIDE;
41  virtual IMP::kernel::ModelObjectsTemp do_get_inputs() const IMP_OVERRIDE;
43 protected:
44  kernel::Particle *p1_,*p2_;
45 };
46 
47 //! Utility class for building merge trees.
48 class IMPMULTIFITEXPORT MergeTreeBuilder {
49 public:
50  MergeTreeBuilder(const atom::Hierarchies &mhs) : g_(mhs.size()),
51  mhs_(mhs) {
52  //add mapping from mol to node
53 
54  typedef boost::graph_traits<MTU::DependencyGraph>::vertex_iterator
55  VertexIterator;
56  VertexIterator v_it, v_it_end;
57  boost::tie(v_it, v_it_end) = boost::vertices(g_);
58  int ind=0;
59  for (; v_it != v_it_end; ++v_it) {
60  mol2node_[mhs_[ind]]=*v_it;
61  node2mol_[*v_it]=mhs_[ind];
62  ind=ind+1;
63  }
64  }//end constructor
65 
66  //add +1 to the edge weight, creates the edge if does not exist
67  void increase_edge(atom::Hierarchy mh1,atom::Hierarchy mh2) {
68  //do not add self edges
69  if (mh1.get_particle()==mh2.get_particle())
70  return;
71  //get the corresponding nodes
72  MTU::DGVertex u,v;
73  u=mol2node_[mh1.get_particle()];
74  v=mol2node_[mh2.get_particle()];
75  if (!boost::edge(u,v,g_).second) {//edge does not exist
76  boost::add_edge(u,v,MTU::DGWeight(0.),g_);
77  }
78  //increase edge by one
79  MTU::DGEdge e;
80  e=boost::edge(u,v,g_).first;
81  boost::put(boost::edge_weight_t(),g_,e,
82  boost::get(boost::edge_weight_t(),g_,e)-1);
83  }
84  void show(std::ostream& out=std::cout) const {
85  out << "vertices:";
86  typedef boost::graph_traits<MTU::DependencyGraph>::vertex_iterator
87  vertex_iter;
88  std::pair<vertex_iter, vertex_iter> vp;
89  for (vp = vertices(g_); vp.first != vp.second; ++vp.first) {
90  out << node2mol_.find(*vp.first)->second->get_name() << " ";
91  }
92  out << std::endl;
93  out << "edges:";
94  boost::graph_traits<MTU::DependencyGraph>::edge_iterator ei, ei_end;
95  for (boost::tie(ei, ei_end) = edges(g_); ei != ei_end; ++ei)
96  out << "(" << node2mol_.find(source(*ei, g_))->second->get_name()
97  << "," << node2mol_.find(target(*ei, g_))->second->get_name()
98  << ","<<boost::get(boost::edge_weight_t(),g_,*ei)<<")"<<std::endl;
99  out << std::endl;
100  }
101  kernel::ParticlePairsTemp get_mst_dependency() const {
102  std::vector<MTU::DGEdge> mst;
103  boost::kruskal_minimum_spanning_tree(g_, std::back_inserter(mst));
104  //go over the edges and get the pairs
106  for(int i=0;i<(int)mst.size();i++) {
108  pp[0]=node2mol_.find(boost::source(mst[i],g_))->second;
109  pp[1]=node2mol_.find(boost::target(mst[i],g_))->second;
110  ret.push_back(pp);
111  }
112  return ret;
113  }
114 protected:
115  //the graph
116  MTU::DependencyGraph g_;
117  atom::Hierarchies mhs_;
118  MTU::PVMAP mol2node_;
119  MTU::VPMAP node2mol_;
120 };
121 
122 IMPMULTIFIT_END_NAMESPACE
123 
124 #endif /* IMPMULTIFIT_MERGE_TREE_UTILS_H */
boost::graph DependencyGraph
A directed graph on the interactions between the various objects in the model.
Class for adding derivatives from restraints to the model.
Particle * get_particle() const
Utility class for building merge trees.
A class to store an fixed array of same-typed values.
Definition: base/Array.h:33
Decorator for helping deal with a hierarchy of molecules.
The standard decorator for manipulating molecular structures.
A restraint is a term in an IMP ScoringFunction.
#define IMP_OBJECT_METHODS(Name)
Define the basic things needed by any Object.
Class to handle individual model particles.
void show(Hierarchy h, std::ostream &out=std::cout)
Print out a molecular hierarchy.
virtual ModelObjectsTemp do_get_inputs() const =0
IMP::kernel::Restraint Restraint
A simple Restraint that always returns a score of zero.
Declare an efficient stl-compatible map.