IMP  2.0.0
The Integrative Modeling Platform
merge_tree_utils.h
Go to the documentation of this file.
1 /**
2  * \file 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<Particle *, DGVertex> PVMAP;
30  typedef base::map<DGVertex,Particle *> VPMAP;
31 };
32 
33 class IMPMULTIFITEXPORT DummyRestraint : public Restraint {
34 public:
35  DummyRestraint(Particle *a,Particle *b) : p1_(a),p2_(b){}
36  IMP_RESTRAINT(DummyRestraint);
37 protected:
38  Particle *p1_,*p2_;
39 };
40 
41 class IMPMULTIFITEXPORT MergeTreeBuilder {
42 public:
43  MergeTreeBuilder(const atom::Hierarchies &mhs) : g_(mhs.size()),
44  mhs_(mhs) {
45  //add mapping from mol to node
46 
47  typedef boost::graph_traits<MTU::DependencyGraph>::vertex_iterator
48  VertexIterator;
49  VertexIterator v_it, v_it_end;
50  boost::tie(v_it, v_it_end) = boost::vertices(g_);
51  int ind=0;
52  for (; v_it != v_it_end; ++v_it) {
53  mol2node_[mhs_[ind]]=*v_it;
54  node2mol_[*v_it]=mhs_[ind];
55  ind=ind+1;
56  }
57  }//end constructor
58 
59  //add +1 to the edge weight, creates the edge if does not exist
60  void increase_edge(atom::Hierarchy mh1,atom::Hierarchy mh2) {
61  //do not add self edges
62  if (mh1.get_particle()==mh2.get_particle())
63  return;
64  //get the corresponding nodes
65  MTU::DGVertex u,v;
66  u=mol2node_[mh1.get_particle()];
67  v=mol2node_[mh2.get_particle()];
68  if (!boost::edge(u,v,g_).second) {//edge does not exist
69  boost::add_edge(u,v,MTU::DGWeight(0.),g_);
70  }
71  //increase edge by one
72  MTU::DGEdge e;
73  e=boost::edge(u,v,g_).first;
74  boost::put(boost::edge_weight_t(),g_,e,
75  boost::get(boost::edge_weight_t(),g_,e)-1);
76  }
77  void show(std::ostream& out=std::cout) const {
78  out << "vertices:";
79  typedef boost::graph_traits<MTU::DependencyGraph>::vertex_iterator
80  vertex_iter;
81  std::pair<vertex_iter, vertex_iter> vp;
82  for (vp = vertices(g_); vp.first != vp.second; ++vp.first) {
83  out << node2mol_.find(*vp.first)->second->get_name() << " ";
84  }
85  out << std::endl;
86  out << "edges:";
87  boost::graph_traits<MTU::DependencyGraph>::edge_iterator ei, ei_end;
88  for (boost::tie(ei, ei_end) = edges(g_); ei != ei_end; ++ei)
89  out << "(" << node2mol_.find(source(*ei, g_))->second->get_name()
90  << "," << node2mol_.find(target(*ei, g_))->second->get_name()
91  << ","<<boost::get(boost::edge_weight_t(),g_,*ei)<<")"<<std::endl;
92  out << std::endl;
93  }
94  ParticlePairsTemp get_mst_dependency() const {
95  std::vector<MTU::DGEdge> mst;
96  boost::kruskal_minimum_spanning_tree(g_, std::back_inserter(mst));
97  //go over the edges and get the pairs
99  for(int i=0;i<(int)mst.size();i++) {
100  ParticlePair pp;
101  pp[0]=node2mol_.find(boost::source(mst[i],g_))->second;
102  pp[1]=node2mol_.find(boost::target(mst[i],g_))->second;
103  ret.push_back(pp);
104  }
105  return ret;
106  }
107 protected:
108  //the graph
110  atom::Hierarchies mhs_;
111  MTU::PVMAP mol2node_;
112  MTU::VPMAP node2mol_;
113 };
114 
115 IMPMULTIFIT_END_NAMESPACE
116 
117 #endif /* IMPMULTIFIT_MERGE_TREE_UTILS_H */