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
12/**
13 * @file SubgraphBuilder.h
14 * @date Dec 31, 2009
15 * @author Frank Dellaert, Yong-Dian Jian
16 */
17
18#pragma once
19
20#include <gtsam/base/FastMap.h>
21#include <gtsam/base/types.h>
22#include <gtsam/dllexport.h>
23
24#if 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
32namespace boost {
33namespace serialization {
34class access;
35} /* namespace serialization */
36} /* namespace boost */
37
38namespace gtsam {
39
40// Forward declarations
41class GaussianFactorGraph;
42struct PreconditionerParameters;
43
44/**************************************************************************/
45class 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#if 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#if 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/****************************************************************************/
102struct 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
128 /// factor multiplied with n, yields number of extra edges.
129 double augmentationFactor;
130
131 SubgraphBuilderParameters()
132 : skeletonType(KRUSKAL),
133 skeletonWeight(RANDOM),
134 augmentationWeight(SKELETON),
135 augmentationFactor(1.0) {}
136 virtual ~SubgraphBuilderParameters() {}
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/*****************************************************************************/
153class GTSAM_EXPORT SubgraphBuilder {
154 public:
155 typedef SubgraphBuilder Base;
156 typedef std::vector<double> Weights;
157
158 SubgraphBuilder(
159 const SubgraphBuilderParameters &p = SubgraphBuilderParameters())
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;
175 SubgraphBuilderParameters parameters_;
176};
177
178/** Select the factors in a factor graph according to the subgraph. */
179GaussianFactorGraph buildFactorSubgraph(const GaussianFactorGraph &gfg,
180 const Subgraph &subgraph,
181 const bool clone);
182
183/** Split the graph into a subgraph and the remaining edges.
184 * Note that the remaining factorgraph has null factors. */
185std::pair<GaussianFactorGraph, GaussianFactorGraph> GTSAM_EXPORT splitFactorGraph(
186 const GaussianFactorGraph &factorGraph, const Subgraph &subgraph);
187
188} // namespace gtsam
189