IMP logo
IMP Reference Guide  2.20.2
The Integrative Modeling Platform
merge_tree_utils.h
Go to the documentation of this file.
1 /**
2  * \file IMP/multifit/merge_tree_utils.h
3  *
4  * Copyright 2007-2022 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/functional/hash.hpp>
11 
12 // Work around Boost bug with adjacency_matrix in 1.60:
13 // https://svn.boost.org/trac/boost/ticket/11880
14 #include <boost/version.hpp>
15 #if BOOST_VERSION == 106000
16 # include <boost/type_traits/ice.hpp>
17 #endif
18 
19 #include <boost/graph/adjacency_matrix.hpp>
20 #include <boost/graph/adjacency_list.hpp>
21 #include <boost/pending/disjoint_sets.hpp>
22 #include <boost/graph/graph_utility.hpp>
23 #include <IMP/multifit/multifit_config.h>
24 #include <IMP/atom/Hierarchy.h>
25 #include <boost/unordered_map.hpp>
26 #include <boost/graph/kruskal_min_spanning_tree.hpp>
27 #include <boost/graph/prim_minimum_spanning_tree.hpp>
28 
29 IMPMULTIFIT_BEGIN_NAMESPACE
30 
31 namespace MTU {
32 typedef boost::adjacency_matrix<boost::undirectedS, boost::no_property,
33  boost::property<boost::edge_weight_t, double> >
35 typedef boost::graph_traits<DependencyGraph>::edge_descriptor DGEdge;
36 typedef DependencyGraph::edge_property_type DGWeight;
37 typedef boost::graph_traits<DependencyGraph>::vertex_descriptor DGVertex;
38 typedef boost::unordered_map<Particle *, DGVertex> PVMAP;
39 typedef boost::unordered_map<DGVertex, Particle *> VPMAP;
40 };
41 
42 //! A simple Restraint that always returns a score of zero.
43 class IMPMULTIFITEXPORT DummyRestraint : public Restraint {
44  public:
46  : Restraint(a->get_model(), "DummyRestraint%1%"),
47  p1_(a),
48  p2_(b) {}
50  const override;
51  virtual IMP::ModelObjectsTemp do_get_inputs() const override;
53 
54  protected:
55  Particle *p1_, *p2_;
56 };
57 
58 //! Utility class for building merge trees.
59 class IMPMULTIFITEXPORT MergeTreeBuilder {
60  public:
61  MergeTreeBuilder(const atom::Hierarchies &mhs) : g_(mhs.size()), mhs_(mhs) {
62  // add mapping from mol to node
63 
64  typedef boost::graph_traits<MTU::DependencyGraph>::vertex_iterator
65  VertexIterator;
66  VertexIterator v_it, v_it_end;
67  boost::tie(v_it, v_it_end) = boost::vertices(g_);
68  int ind = 0;
69  for (; v_it != v_it_end; ++v_it) {
70  mol2node_[mhs_[ind]] = *v_it;
71  node2mol_[*v_it] = mhs_[ind];
72  ind = ind + 1;
73  }
74  } // end constructor
75 
76  // add +1 to the edge weight, creates the edge if does not exist
77  void increase_edge(atom::Hierarchy mh1, atom::Hierarchy mh2) {
78  // do not add self edges
79  if (mh1.get_particle() == mh2.get_particle()) return;
80  // get the corresponding nodes
81  MTU::DGVertex u, v;
82  u = mol2node_[mh1.get_particle()];
83  v = mol2node_[mh2.get_particle()];
84  if (!boost::edge(u, v, g_).second) { // edge does not exist
85  boost::add_edge(u, v, MTU::DGWeight(0.), g_);
86  }
87  // increase edge by one
88  MTU::DGEdge e;
89  e = boost::edge(u, v, g_).first;
90  boost::put(boost::edge_weight_t(), g_, e,
91  boost::get(boost::edge_weight_t(), g_, e) - 1);
92  }
93  void show(std::ostream &out = std::cout) const {
94  out << "vertices:";
95  typedef boost::graph_traits<MTU::DependencyGraph>::vertex_iterator
96  vertex_iter;
97  std::pair<vertex_iter, vertex_iter> vp;
98  for (vp = vertices(g_); vp.first != vp.second; ++vp.first) {
99  out << node2mol_.find(*vp.first)->second->get_name() << " ";
100  }
101  out << std::endl;
102  out << "edges:";
103  boost::graph_traits<MTU::DependencyGraph>::edge_iterator ei, ei_end;
104  for (boost::tie(ei, ei_end) = edges(g_); ei != ei_end; ++ei)
105  out << "(" << node2mol_.find(source(*ei, g_))->second->get_name() << ","
106  << node2mol_.find(target(*ei, g_))->second->get_name() << ","
107  << boost::get(boost::edge_weight_t(), g_, *ei) << ")" << std::endl;
108  out << std::endl;
109  }
110  ParticlePairsTemp get_mst_dependency() const {
111  std::vector<MTU::DGEdge> mst;
112  boost::kruskal_minimum_spanning_tree(g_, std::back_inserter(mst));
113  // go over the edges and get the pairs
114  ParticlePairsTemp ret;
115  for (int i = 0; i < (int)mst.size(); i++) {
116  ParticlePair pp;
117  pp[0] = node2mol_.find(boost::source(mst[i], g_))->second;
118  pp[1] = node2mol_.find(boost::target(mst[i], g_))->second;
119  ret.push_back(pp);
120  }
121  return ret;
122  }
123 
124  protected:
125  // the graph
126  MTU::DependencyGraph g_;
127  atom::Hierarchies mhs_;
128  MTU::PVMAP mol2node_;
129  MTU::VPMAP node2mol_;
130 };
131 
132 IMPMULTIFIT_END_NAMESPACE
133 
134 #endif /* IMPMULTIFIT_MERGE_TREE_UTILS_H */
Utility class for building merge trees.
boost::graph DependencyGraph
Directed graph on the interactions between the various objects in the model.
A class to store a fixed array of same-typed values.
Definition: Array.h:35
#define IMP_OBJECT_METHODS(Name)
Define the basic things needed by any Object.
Definition: object_macros.h:25
virtual double unprotected_evaluate(DerivativeAccumulator *da) const
Return the unweighted score for the restraint.
A more IMP-like version of the std::vector.
Definition: Vector.h:42
Restraint()
Default constructor.
Decorator for helping deal with a hierarchy of molecules.
The standard decorator for manipulating molecular structures.
Particle * get_particle() const
Returns the particle decorated by this decorator.
Definition: Decorator.h:194
std::ostream & show(Hierarchy h, std::ostream &out=std::cout)
Print the hierarchy using a given decorator to display each node.
Class to handle individual particles of a Model object.
Definition: Particle.h:43
A simple Restraint that always returns a score of zero.
virtual ModelObjectsTemp do_get_inputs() const =0
Class for adding derivatives from restraints to the model.
A restraint is a term in an IMP ScoringFunction.
Definition: Restraint.h:56