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


gtsam
Author(s):
autogenerated on Fri Nov 1 2024 03:36:27