gtsam  4.0.0
gtsam
SubgraphBuilder.h
Go to the documentation of this file.
1 /* ----------------------------------------------------------------------------
2 
3  * GTSAM Copyright 2010-2019, Georgia Tech Research Corporation,
4  * Atlanta, Georgia 30332-0415
5  * All Rights Reserved
6  * Authors: Frank Dellaert, et al. (see THANKS for the full author list)
7 
8  * See LICENSE for the license information
9 
10  * -------------------------------------------------------------------------- */
11 
18 #pragma once
19 
20 #include <gtsam/base/FastMap.h>
21 #include <gtsam/base/types.h>
22 #include <gtsam/dllexport.h>
23 
24 #include <boost/serialization/nvp.hpp>
25 #include <boost/shared_ptr.hpp>
26 
27 #include <vector>
28 
29 namespace boost {
30 namespace serialization {
31 class access;
32 } /* namespace serialization */
33 } /* namespace boost */
34 
35 namespace gtsam {
36 
37 // Forward declarations
38 class GaussianFactorGraph;
39 struct PreconditionerParameters;
40 
41 /**************************************************************************/
42 class GTSAM_EXPORT Subgraph {
43  public:
44  struct GTSAM_EXPORT Edge {
45  size_t index; /* edge id */
46  double weight; /* edge weight */
47  inline bool isUnitWeight() const { return (weight == 1.0); }
48  friend std::ostream &operator<<(std::ostream &os, const Edge &edge);
49 
50  private:
51  friend class boost::serialization::access;
52  template <class Archive>
53  void serialize(Archive &ar, const unsigned int /*version*/) {
54  ar &BOOST_SERIALIZATION_NVP(index);
55  ar &BOOST_SERIALIZATION_NVP(weight);
56  }
57  };
58 
59  typedef std::vector<Edge> Edges;
60  typedef std::vector<size_t> EdgeIndices;
61  typedef Edges::iterator iterator;
62  typedef Edges::const_iterator const_iterator;
63 
64  protected:
65  Edges edges_; /* index to the factors */
66 
67  public:
68  Subgraph() {}
69  Subgraph(const Subgraph &subgraph) : edges_(subgraph.edges()) {}
70  Subgraph(const Edges &edges) : edges_(edges) {}
71  Subgraph(const std::vector<size_t> &indices);
72 
73  inline const Edges &edges() const { return edges_; }
74  inline size_t size() const { return edges_.size(); }
75  EdgeIndices edgeIndices() const;
76 
77  iterator begin() { return edges_.begin(); }
78  const_iterator begin() const { return edges_.begin(); }
79  iterator end() { return edges_.end(); }
80  const_iterator end() const { return edges_.end(); }
81 
82  void save(const std::string &fn) const;
83  static Subgraph load(const std::string &fn);
84  friend std::ostream &operator<<(std::ostream &os, const Subgraph &subgraph);
85 
86  private:
87  friend class boost::serialization::access;
88  template <class Archive>
89  void serialize(Archive &ar, const unsigned int /*version*/) {
90  ar &BOOST_SERIALIZATION_NVP(edges_);
91  }
92 };
93 
94 /****************************************************************************/
95 struct GTSAM_EXPORT SubgraphBuilderParameters {
96  typedef boost::shared_ptr<SubgraphBuilderParameters> shared_ptr;
97 
98  enum Skeleton {
99  /* augmented tree */
100  NATURALCHAIN = 0, /* natural ordering of the graph */
101  BFS, /* breadth-first search tree */
102  KRUSKAL, /* maximum weighted spanning tree */
103  } skeletonType;
104 
105  enum SkeletonWeight { /* how to weigh the graph edges */
106  EQUAL = 0, /* every block edge has equal weight */
107  RHS_2NORM, /* use the 2-norm of the rhs */
108  LHS_FNORM, /* use the frobenius norm of the lhs */
109  RANDOM, /* bounded random edge weight */
110  } skeletonWeight;
111 
112  enum AugmentationWeight { /* how to weigh the graph edges */
113  SKELETON = 0, /* use the same weights in building
114  the skeleton */
115  // STRETCH, /* stretch in the
116  // laplacian sense */ GENERALIZED_STRETCH /*
117  // the generalized stretch defined in
118  // jian2013iros */
119  } augmentationWeight;
120 
122  double augmentationFactor;
123 
124  SubgraphBuilderParameters()
125  : skeletonType(KRUSKAL),
126  skeletonWeight(RANDOM),
127  augmentationWeight(SKELETON),
128  augmentationFactor(1.0) {}
129  virtual ~SubgraphBuilderParameters() {}
130 
131  /* for serialization */
132  void print() const;
133  virtual void print(std::ostream &os) const;
134  friend std::ostream &operator<<(std::ostream &os,
135  const PreconditionerParameters &p);
136 
137  static Skeleton skeletonTranslator(const std::string &s);
138  static std::string skeletonTranslator(Skeleton s);
139  static SkeletonWeight skeletonWeightTranslator(const std::string &s);
140  static std::string skeletonWeightTranslator(SkeletonWeight w);
141  static AugmentationWeight augmentationWeightTranslator(const std::string &s);
142  static std::string augmentationWeightTranslator(AugmentationWeight w);
143 };
144 
145 /*****************************************************************************/
146 class GTSAM_EXPORT SubgraphBuilder {
147  public:
148  typedef SubgraphBuilder Base;
149  typedef std::vector<double> Weights;
150 
151  SubgraphBuilder(
152  const SubgraphBuilderParameters &p = SubgraphBuilderParameters())
153  : parameters_(p) {}
154  virtual ~SubgraphBuilder() {}
155  virtual Subgraph operator()(const GaussianFactorGraph &jfg) const;
156 
157  private:
158  std::vector<size_t> buildTree(const GaussianFactorGraph &gfg,
159  const FastMap<Key, size_t> &ordering,
160  const std::vector<double> &weights) const;
161  std::vector<size_t> unary(const GaussianFactorGraph &gfg) const;
162  std::vector<size_t> natural_chain(const GaussianFactorGraph &gfg) const;
163  std::vector<size_t> bfs(const GaussianFactorGraph &gfg) const;
164  std::vector<size_t> kruskal(const GaussianFactorGraph &gfg,
165  const FastMap<Key, size_t> &ordering,
166  const std::vector<double> &weights) const;
167  std::vector<size_t> sample(const std::vector<double> &weights,
168  const size_t t) const;
169  Weights weights(const GaussianFactorGraph &gfg) const;
170  SubgraphBuilderParameters parameters_;
171 };
172 
174 boost::shared_ptr<GaussianFactorGraph> buildFactorSubgraph(
175  const GaussianFactorGraph &gfg, const Subgraph &subgraph, const bool clone);
176 
179 std::pair<boost::shared_ptr<GaussianFactorGraph>, boost::shared_ptr<GaussianFactorGraph> >
180 splitFactorGraph(const GaussianFactorGraph &factorGraph, const Subgraph &subgraph);
181 
182 } // namespace gtsam
gtsam::Subgraph::Edge
Definition: SubgraphBuilder.h:44
gtsam::SubgraphBuilderParameters::augmentationFactor
double augmentationFactor
factor multiplied with n, yields number of extra edges.
Definition: SubgraphBuilder.h:122
gtsam::print
void print(const Matrix &A, const string &s, ostream &stream)
print without optional string, must specify cout yourself
Definition: Matrix.cpp:141
gtsam::GaussianFactorGraph
A Linear Factor Graph is a factor graph where all factors are Gaussian, i.e.
Definition: GaussianFactorGraph.h:65
gtsam::save
void save(const Matrix &A, const string &s, const string &filename)
save a matrix to file, which can be loaded by matlab
Definition: Matrix.cpp:162
gtsam::SubgraphBuilder
Definition: SubgraphBuilder.h:146
gtsam::Subgraph
Definition: SubgraphBuilder.h:42
FastMap.h
A thin wrapper around std::map that uses boost's fast_pool_allocator.
gtsam::buildFactorSubgraph
GaussianFactorGraph::shared_ptr buildFactorSubgraph(const GaussianFactorGraph &gfg, const Subgraph &subgraph, const bool clone)
Select the factors in a factor graph according to the subgraph.
Definition: SubgraphBuilder.cpp:514
gtsam::SubgraphBuilderParameters
Definition: SubgraphBuilder.h:95
gtsam::splitFactorGraph
std::pair< GaussianFactorGraph::shared_ptr, GaussianFactorGraph::shared_ptr > splitFactorGraph(const GaussianFactorGraph &factorGraph, const Subgraph &subgraph)
Split the graph into a subgraph and the remaining edges.
Definition: SubgraphBuilder.cpp:528
gtsam
Global functions in a separate testing namespace.
Definition: chartTesting.h:28
types.h
Typedefs for easier changing of types.