IMP  2.1.1
The Integrative Modeling Platform
subset_graphs.h
Go to the documentation of this file.
1 /**
2  * \file IMP/domino/subset_graphs.h
3  * \brief A beyesian infererence-based sampler.
4  *
5  * Copyright 2007-2013 IMP Inventors. All rights reserved.
6  *
7  */
8 
9 #ifndef IMPDOMINO_SUBSET_GRAPHS_H
10 #define IMPDOMINO_SUBSET_GRAPHS_H
11 
12 #include "particle_states.h"
13 #include "Subset.h"
14 #include <IMP/ScoringFunction.h>
16 #include <boost/graph/adjacency_list.hpp>
17 
18 IMPDOMINO_BEGIN_NAMESPACE
19 
20 /** An undirected graph on subsets of vertices. Each vertex is
21  named with an Subset.
22  */
23 IMP_GRAPH(SubsetGraph, undirected, Subset, int, out << vertex);
24 
25 /** An undirected graph with one vertex per particle of interest.
26  Two particles are connected by an edge if a kernel::Restraint
27  or ScoreState creates and interaction between the two particles.
28 
29  See \ref graphs "Graphs in IMP" for more information.
30  */
33  out << vertex->get_name() << "\n[" << vertex->get_index() << "]");
34 
35 //! Gets all of the Subsets of a SubsetGraph
36 IMPDOMINOEXPORT Subsets get_subsets(const SubsetGraph &g);
37 
38 /** Compute the exact
39  \external{http://en.wikipedia.org/wiki/Junction_tree,junction tree}
40  for an interaction graph. The resulting graph has the junction tree
41  properties
42  - it is a tree
43  - for any two vertices whose subsets both contain a vertex, that vertex
44  is contained in all subsets along the path connecting those two vertices.
45 
46  \note the junction tree is not nececessarily deterministic (you can
47  get different answers if you run it different times with the same inputs).
48 */
49 IMPDOMINOEXPORT SubsetGraph get_junction_tree(const InteractionGraph &ig);
50 
51 #ifndef IMP_DOXYGEN
52 /** \name Debugging Junction Trees
53  @{ */
54 IMPDOMINOEXPORT InteractionGraph
55  get_triangulated(const InteractionGraph &input);
56 
57 IMP_WEIGHTED_GRAPH(CliqueGraph, undirected, Subset, out << vertex);
58 
59 IMPDOMINOEXPORT CliqueGraph get_clique_graph(const InteractionGraph &input);
60 
61 IMPDOMINOEXPORT SubsetGraph get_minimum_spanning_tree(const CliqueGraph &input);
62 
63 /** @} */
64 #endif
65 
66 /** The restraint graph is formed by having one node per restraint
67  and an edge connecting two restraints if they share input
68  particles. The associated Subsets are the set of input particles
69  for the restraint, projected onto ps.
70 
71  \note The graph for the optimized restraints (after temporary
72  application of OptimizeContainers and OptimizeRestraints) is
73  returned.
74 */
75 IMPDOMINOEXPORT SubsetGraph get_restraint_graph(ScoringFunctionAdaptor rs,
76  const ParticleStatesTable *pst);
77 
78 /** Compute the interaction graph of the restraints and the specified
79  particles. The dependency graph in the model is traversed to
80  determine how the passed particles relate to the actual particles
81  read as input by the model. For example, if particles contains a
82  rigid body, then an restraint which uses a member of the rigid
83  body will have an edge from the rigid body particle.
84 
85  \note You may want to create an OptimizeRestraints object before
86  calling this function.
87 
88  \note These functions are here to aid in debugging of optimization
89  protocols that use Domino2. As a result, its signature and
90  functionality may change without notice.
91  @{
92  */
93 IMPDOMINOEXPORT InteractionGraph
94  get_interaction_graph(ScoringFunctionAdaptor rs,
95  const ParticleStatesTable *pst);
96 
97 IMPDOMINOEXPORT InteractionGraph
98  get_interaction_graph(ScoringFunctionAdaptor rs,
99  const kernel::ParticlesTemp &pst);
100 
101 /** Assuming that all the particles have Cartesian coordinates,
102  output edges corresponding to the edges in the interaction graph.
103  The edges are named by the restraint which induces them.
104 */
106  const InteractionGraph &ig);
107 
108 /** Display the subsets of a subset graph, superimposed on the 3D
109  coordinates of the particles.
110 */
112  const SubsetGraph &ig);
113 
114 /** A directed graph on subsets of vertices. Each vertex is
115  named with an Subset.
116  */
117 IMP_GRAPH(MergeTree, bidirectional, Subset, int, out << vertex);
118 
119 /** \see get_merge_tree(const SubsetGraph&)
120 
121  Compute the merge tree for a given restraint set and
122  particle states table. An OptimizeRestraints object is
123  created to improve the InteractionGraph used internally.
124  */
125 IMPDOMINOEXPORT MergeTree get_merge_tree(ScoringFunctionAdaptor input,
126  const ParticleStatesTable *pst);
127 
128 /** \see get_merge_tree(kernel::RestraintSet*,const ParticleStatesTable*)
129 
130  Compute the merge tree from a junction tree.
131 
132  \note the merge tree is not nececessarily deterministic (you can
133  get different answers if you run it different times with the same inputs).
134  */
135 IMPDOMINOEXPORT MergeTree get_merge_tree(const SubsetGraph &junction_tree);
136 
137 /** \see get_merge_tree(kernel::RestraintSet*,const ParticleStatesTable*)
138 
139  Compute the merge tree from a junction tree, attempting to keep it fairly
140  balanced.
141 
142  \note the merge tree is not nececessarily deterministic (you can
143  get different answers if you run it different times with the same inputs).
144  */
145 IMPDOMINOEXPORT MergeTree
146  get_balanced_merge_tree(const SubsetGraph &junction_tree);
147 
148 IMPDOMINOEXPORT bool get_is_merge_tree(const MergeTree &tree, Subset all,
149  bool verbose = true);
150 
151 /** \name Read and write merge trees
152  Merge trees can be written to an read from a text stream. As always,
153  this requires a canonical particles list whose order is the same
154  for the reading and writing.
155  @{
156 */
157 
158 IMPDOMINOEXPORT void write_merge_tree(const MergeTree &tree,
159  const kernel::ParticlesTemp &ps,
160  std::ostream &out);
161 IMPDOMINOEXPORT MergeTree
162  read_merge_tree(std::istream &input, const kernel::ParticlesTemp &ps);
163 /** @} */
164 
165 IMPDOMINO_END_NAMESPACE
166 
167 #endif /* IMPDOMINO_SUBSET_GRAPHS_H */
#define IMP_WEIGHTED_GRAPH(Name, directionality, VertexData, ShowVertex)
Define a graph object in IMP.
SubsetGraph get_junction_tree(const InteractionGraph &ig)
Subsets get_subsets(const SubsetGraph &g)
Gets all of the Subsets of a SubsetGraph.
boost::graph SubsetGraph
Definition: subset_graphs.h:23
Represent a subset of the particles being optimized.
Definition: Subset.h:33
MergeTree get_balanced_merge_tree(const SubsetGraph &junction_tree)
Implement geometry for the basic shapes from IMP.algebra.
display::Geometries get_subset_graph_geometry(const SubsetGraph &ig)
InteractionGraph get_interaction_graph(ScoringFunctionAdaptor rs, const ParticleStatesTable *pst)
MergeTree get_merge_tree(ScoringFunctionAdaptor input, const ParticleStatesTable *pst)
boost::graph MergeTree
Class to handle individual model particles.
A beyesian infererence-based sampler.
#define IMP_GRAPH(Name, directionality, VertexData, EdgeData, ShowVertex)
Define a graph object in IMP.
Import IMP/kernel/ScoringFunction.h in the namespace.
SubsetGraph get_restraint_graph(ScoringFunctionAdaptor rs, const ParticleStatesTable *pst)
display::Geometries get_interaction_graph_geometry(const InteractionGraph &ig)
A beyesian infererence-based sampler.
boost::graph InteractionGraph
Definition: subset_graphs.h:33