gtsam 4.2.0
gtsam
Loading...
Searching...
No Matches
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
30namespace boost {
31namespace serialization {
32class access;
33} /* namespace serialization */
34} /* namespace boost */
35
36namespace gtsam {
37
38// Forward declarations
39class GaussianFactorGraph;
40struct PreconditionerParameters;
41
42/**************************************************************************/
43class 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/****************************************************************************/
96struct 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) {}
130 virtual ~SubgraphBuilderParameters() {}
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/*****************************************************************************/
147class GTSAM_EXPORT SubgraphBuilder {
148 public:
149 typedef SubgraphBuilder Base;
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,
160 const FastMap<Key, size_t> &ordering,
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;
171 SubgraphBuilderParameters parameters_;
172};
173
176 const Subgraph &subgraph,
177 const bool clone);
178
181std::pair<GaussianFactorGraph, GaussianFactorGraph> splitFactorGraph(
182 const GaussianFactorGraph &factorGraph, const Subgraph &subgraph);
183
184} // namespace gtsam
A thin wrapper around std::map that uses boost's fast_pool_allocator.
Typedefs for easier changing of types.
Global functions in a separate testing namespace.
Definition chartTesting.h:28
GaussianFactorGraph buildFactorSubgraph(const GaussianFactorGraph &gfg, const Subgraph &subgraph, const bool clone)
Select the factors in a factor graph according to the subgraph.
Definition SubgraphBuilder.cpp:447
std::pair< GaussianFactorGraph, GaussianFactorGraph > splitFactorGraph(const GaussianFactorGraph &factorGraph, const Subgraph &subgraph)
Split the graph into a subgraph and the remaining edges.
Definition SubgraphBuilder.cpp:460
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:167
FastMap is a thin wrapper around std::map that uses the boost fast_pool_allocator instead of the defa...
Definition FastMap.h:38
A Linear Factor Graph is a factor graph where all factors are Gaussian, i.e.
Definition GaussianFactorGraph.h:75
Definition SubgraphBuilder.h:43
Definition SubgraphBuilder.h:45
Definition SubgraphBuilder.h:96
double augmentationFactor
factor multiplied with n, yields number of extra edges.
Definition SubgraphBuilder.h:123
Definition SubgraphBuilder.h:147