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/version.hpp>
25 #include <boost/serialization/nvp.hpp>
26 #include <boost/shared_ptr.hpp>
27 
28 #include <vector>
29 
30 namespace boost {
31 namespace serialization {
32 class access;
33 } /* namespace serialization */
34 } /* namespace boost */
35 
36 namespace gtsam {
37 
38 // Forward declarations
39 class GaussianFactorGraph;
40 struct PreconditionerParameters;
41 
42 /**************************************************************************/
43 class GTSAM_EXPORT Subgraph {
44  public:
45  struct GTSAM_EXPORT Edge {
46  size_t index; /* edge id */
47  double weight; /* edge weight */
48  inline bool isUnitWeight() const { return (weight == 1.0); }
49  friend std::ostream &operator<<(std::ostream &os, const Edge &edge);
50 
51  private:
52  friend class boost::serialization::access;
53  template <class Archive>
54  void serialize(Archive &ar, const unsigned int /*version*/) {
55  ar &BOOST_SERIALIZATION_NVP(index);
56  ar &BOOST_SERIALIZATION_NVP(weight);
57  }
58  };
59 
60  typedef std::vector<Edge> Edges;
61  typedef std::vector<size_t> EdgeIndices;
62  typedef Edges::iterator iterator;
63  typedef Edges::const_iterator const_iterator;
64 
65  protected:
66  Edges edges_; /* index to the factors */
67 
68  public:
69  Subgraph() {}
70  Subgraph(const Subgraph &subgraph) : edges_(subgraph.edges()) {}
71  Subgraph(const Edges &edges) : edges_(edges) {}
72  Subgraph(const std::vector<size_t> &indices);
73 
74  inline const Edges &edges() const { return edges_; }
75  inline size_t size() const { return edges_.size(); }
76  EdgeIndices edgeIndices() const;
77 
78  iterator begin() { return edges_.begin(); }
79  const_iterator begin() const { return edges_.begin(); }
80  iterator end() { return edges_.end(); }
81  const_iterator end() const { return edges_.end(); }
82 
83  void save(const std::string &fn) const;
84  static Subgraph load(const std::string &fn);
85  friend std::ostream &operator<<(std::ostream &os, const Subgraph &subgraph);
86 
87  private:
88  friend class boost::serialization::access;
89  template <class Archive>
90  void serialize(Archive &ar, const unsigned int /*version*/) {
91  ar &BOOST_SERIALIZATION_NVP(edges_);
92  }
93 };
94 
95 /****************************************************************************/
96 struct GTSAM_EXPORT SubgraphBuilderParameters {
97  typedef boost::shared_ptr<SubgraphBuilderParameters> shared_ptr;
98 
99  enum Skeleton {
100  /* augmented tree */
101  NATURALCHAIN = 0, /* natural ordering of the graph */
102  BFS, /* breadth-first search tree */
103  KRUSKAL, /* maximum weighted spanning tree */
104  } skeletonType;
105 
106  enum SkeletonWeight { /* how to weigh the graph edges */
107  EQUAL = 0, /* every block edge has equal weight */
108  RHS_2NORM, /* use the 2-norm of the rhs */
109  LHS_FNORM, /* use the frobenius norm of the lhs */
110  RANDOM, /* bounded random edge weight */
111  } skeletonWeight;
112 
113  enum AugmentationWeight { /* how to weigh the graph edges */
114  SKELETON = 0, /* use the same weights in building
115  the skeleton */
116  // STRETCH, /* stretch in the
117  // laplacian sense */ GENERALIZED_STRETCH /*
118  // the generalized stretch defined in
119  // jian2013iros */
120  } augmentationWeight;
121 
124 
126  : skeletonType(KRUSKAL),
127  skeletonWeight(RANDOM),
128  augmentationWeight(SKELETON),
129  augmentationFactor(1.0) {}
131 
132  /* for serialization */
133  void print() const;
134  virtual void print(std::ostream &os) const;
135  friend std::ostream &operator<<(std::ostream &os,
136  const PreconditionerParameters &p);
137 
138  static Skeleton skeletonTranslator(const std::string &s);
139  static std::string skeletonTranslator(Skeleton s);
140  static SkeletonWeight skeletonWeightTranslator(const std::string &s);
141  static std::string skeletonWeightTranslator(SkeletonWeight w);
142  static AugmentationWeight augmentationWeightTranslator(const std::string &s);
143  static std::string augmentationWeightTranslator(AugmentationWeight w);
144 };
145 
146 /*****************************************************************************/
147 class GTSAM_EXPORT SubgraphBuilder {
148  public:
150  typedef std::vector<double> Weights;
151 
154  : parameters_(p) {}
155  virtual ~SubgraphBuilder() {}
156  virtual Subgraph operator()(const GaussianFactorGraph &jfg) const;
157 
158  private:
159  std::vector<size_t> buildTree(const GaussianFactorGraph &gfg,
161  const std::vector<double> &weights) const;
162  std::vector<size_t> unary(const GaussianFactorGraph &gfg) const;
163  std::vector<size_t> natural_chain(const GaussianFactorGraph &gfg) const;
164  std::vector<size_t> bfs(const GaussianFactorGraph &gfg) const;
165  std::vector<size_t> kruskal(const GaussianFactorGraph &gfg,
166  const FastMap<Key, size_t> &ordering,
167  const std::vector<double> &weights) const;
168  std::vector<size_t> sample(const std::vector<double> &weights,
169  const size_t t) const;
170  Weights weights(const GaussianFactorGraph &gfg) const;
172 };
173 
175 boost::shared_ptr<GaussianFactorGraph> buildFactorSubgraph(
176  const GaussianFactorGraph &gfg, const Subgraph &subgraph, const bool clone);
177 
180 std::pair<boost::shared_ptr<GaussianFactorGraph>, boost::shared_ptr<GaussianFactorGraph> >
181 splitFactorGraph(const GaussianFactorGraph &factorGraph, const Subgraph &subgraph);
182 
183 } // namespace gtsam
void print(const Matrix &A, const string &s, ostream &stream)
Definition: Matrix.cpp:155
GaussianFactorGraph::shared_ptr buildFactorSubgraph(const GaussianFactorGraph &gfg, const Subgraph &subgraph, const bool clone)
vector< MFAS::KeyPair > edges
Definition: testMFAS.cpp:25
void save(Archive &ar, const Eigen::Matrix< Scalar_, Rows_, Cols_, Ops_, MaxRows_, MaxCols_ > &m, const unsigned int)
Definition: base/Matrix.h:557
Typedefs for easier changing of types.
bool isUnitWeight() const
static enum @843 ordering
const_iterator begin() const
size_t size() const
std::pair< GaussianFactorGraph::shared_ptr, GaussianFactorGraph::shared_ptr > splitFactorGraph(const GaussianFactorGraph &factorGraph, const Subgraph &subgraph)
Subgraph(const Edges &edges)
std::vector< Edge > Edges
std::vector< size_t > EdgeIndices
std::ostream & operator<<(std::ostream &s, const Jet< T, N > &z)
Definition: jet.h:631
double augmentationFactor
factor multiplied with n, yields number of extra edges.
std::vector< double > Weights
SubgraphBuilder(const SubgraphBuilderParameters &p=SubgraphBuilderParameters())
Subgraph(const Subgraph &subgraph)
RealScalar s
boost::shared_ptr< SubgraphBuilderParameters > shared_ptr
const_iterator end() const
Edges::const_iterator const_iterator
const Edges & edges() const
RowVector3d w
Edges::iterator iterator
traits
Definition: chartTesting.h:28
A thin wrapper around std::map that uses boost&#39;s fast_pool_allocator.
ofstream os("timeSchurFactors.csv")
iterator begin()
float * p
SubgraphBuilderParameters parameters_
void load(Archive &ar, Eigen::Matrix< Scalar_, Rows_, Cols_, Ops_, MaxRows_, MaxCols_ > &m, const unsigned int)
Definition: base/Matrix.h:573
void serialize(Archive &ar, const unsigned int)
void serialize(Archive &ar, const unsigned int)
Point2 t(10, 10)


gtsam
Author(s):
autogenerated on Sat May 8 2021 02:44:50