inference/Ordering.h
Go to the documentation of this file.
1 /* ----------------------------------------------------------------------------
2 
3  * GTSAM Copyright 2010, 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 
21 #pragma once
22 
23 #include <gtsam/inference/Key.h>
26 #include <gtsam/base/FastSet.h>
27 
28 #include <algorithm>
29 #include <vector>
30 
31 namespace gtsam {
32 
33 class GTSAM_EXPORT Ordering: public KeyVector {
34 protected:
35  typedef KeyVector Base;
36 
37 public:
38 
40  enum OrderingType {
41  COLAMD, METIS, NATURAL, CUSTOM
42  };
43 
44  typedef Ordering This;
45  typedef std::shared_ptr<This> shared_ptr;
46 
49  }
50 
51  using KeyVector::KeyVector; // Inherit the KeyVector's constructors
52 
54  template<typename KEYS>
55  explicit Ordering(const KEYS& keys) :
56  Base(keys.begin(), keys.end()) {
57  }
58 
62 
64  // e.g. keys += key1, key2
66 
74 
76  bool contains(const Key& key) const;
77 
84  FastMap<Key, size_t> invert() const;
85 
88 
92  template<class FACTOR_GRAPH>
93  static Ordering Colamd(const FACTOR_GRAPH& graph) {
94  if (graph.empty())
95  return Ordering();
96  else
97  return Colamd(VariableIndex(graph));
98  }
99 
101  static Ordering Colamd(const VariableIndex& variableIndex);
102 
111  template<class FACTOR_GRAPH>
112  static Ordering ColamdConstrainedLast(const FACTOR_GRAPH& graph,
113  const KeyVector& constrainLast, bool forceOrder = false) {
114  if (graph.empty())
115  return Ordering();
116  else
117  return ColamdConstrainedLast(VariableIndex(graph), constrainLast, forceOrder);
118  }
119 
126  static Ordering ColamdConstrainedLast(
127  const VariableIndex& variableIndex, const KeyVector& constrainLast,
128  bool forceOrder = false);
129 
138  template<class FACTOR_GRAPH>
139  static Ordering ColamdConstrainedFirst(const FACTOR_GRAPH& graph,
140  const KeyVector& constrainFirst, bool forceOrder = false) {
141  if (graph.empty())
142  return Ordering();
143  else
144  return ColamdConstrainedFirst(VariableIndex(graph), constrainFirst, forceOrder);
145  }
146 
154  static Ordering ColamdConstrainedFirst(
155  const VariableIndex& variableIndex,
156  const KeyVector& constrainFirst, bool forceOrder = false);
157 
167  template<class FACTOR_GRAPH>
168  static Ordering ColamdConstrained(const FACTOR_GRAPH& graph,
169  const FastMap<Key, int>& groups) {
170  if (graph.empty())
171  return Ordering();
172  else
173  return ColamdConstrained(VariableIndex(graph), groups);
174  }
175 
183  static Ordering ColamdConstrained(
184  const VariableIndex& variableIndex, const FastMap<Key, int>& groups);
185 
187  template<class FACTOR_GRAPH>
188  static Ordering Natural(const FACTOR_GRAPH &fg) {
189  KeySet src = fg.keys();
190  KeyVector keys(src.begin(), src.end());
191  std::stable_sort(keys.begin(), keys.end());
192  return Ordering(keys.begin(), keys.end());
193  }
194 
196  template<class FACTOR_GRAPH>
197  static void CSRFormat(std::vector<int>& xadj,
198  std::vector<int>& adj, const FACTOR_GRAPH& graph);
199 
201  static Ordering Metis(const MetisIndex& met);
202 
203  template<class FACTOR_GRAPH>
204  static Ordering Metis(const FACTOR_GRAPH& graph) {
205  if (graph.empty())
206  return Ordering();
207  else
208  return Metis(MetisIndex(graph));
209  }
210 
212 
215 
216  template<class FACTOR_GRAPH>
217  static Ordering Create(OrderingType orderingType,
218  const FACTOR_GRAPH& graph) {
219  if (graph.empty())
220  return Ordering();
221 
222  switch (orderingType) {
223  case COLAMD:
224  return Colamd(graph);
225  case METIS:
226  return Metis(graph);
227  case NATURAL:
228  return Natural(graph);
229  case CUSTOM:
230  throw std::runtime_error(
231  "Ordering::Create error: called with CUSTOM ordering type.");
232  default:
233  throw std::runtime_error(
234  "Ordering::Create error: called with unknown ordering type.");
235  }
236  }
237 
239 
242 
243  void print(const std::string& str = "", const KeyFormatter& keyFormatter =
244  DefaultKeyFormatter) const;
245 
246  bool equals(const Ordering& other, double tol = 1e-9) const;
247 
249 
250 private:
252  static Ordering ColamdConstrained(
253  const VariableIndex& variableIndex, std::vector<int>& cmember);
254 
255 #ifdef GTSAM_ENABLE_BOOST_SERIALIZATION
256 
257  friend class boost::serialization::access;
258  template<class ARCHIVE>
259  void serialize(ARCHIVE & ar, const unsigned int version) {
260  ar & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Base);
261  }
262 #endif
263 };
264 
266 template<> struct traits<Ordering> : public Testable<Ordering> {
267 };
268 
269 }
270 
gtsam::Ordering::ColamdConstrainedLast
static Ordering ColamdConstrainedLast(const FACTOR_GRAPH &graph, const KeyVector &constrainLast, bool forceOrder=false)
Definition: inference/Ordering.h:112
operator,
Eigen::CommaInitializer< XprType > & operator,(Eigen::CommaInitializer< XprType > &ci, double v)
Definition: special_functions.cpp:21
gtsam::Ordering::This
Ordering This
Typedef to this class.
Definition: inference/Ordering.h:44
gtsam::Ordering::Ordering
Ordering(const KEYS &keys)
Create from a container.
Definition: inference/Ordering.h:55
e
Array< double, 1, 3 > e(1./3., 0.5, 2.)
gtsam::Ordering::Ordering
Ordering()
Create an empty ordering
Definition: inference/Ordering.h:48
keys
const KeyVector keys
Definition: testRegularImplicitSchurFactor.cpp:40
gtsam::Ordering::Create
static Ordering Create(OrderingType orderingType, const FACTOR_GRAPH &graph)
Definition: inference/Ordering.h:217
gtsam::FastMap< Key, size_t >
gtsam::FastSet< Key >
gtsam::Ordering::NATURAL
@ NATURAL
Definition: inference/Ordering.h:41
gtsam::KeyVector
FastVector< Key > KeyVector
Define collection type once and for all - also used in wrappers.
Definition: Key.h:92
gtsam::Ordering::shared_ptr
std::shared_ptr< This > shared_ptr
shared_ptr to this class
Definition: inference/Ordering.h:45
gtsam::DefaultKeyFormatter
KeyFormatter DefaultKeyFormatter
Assign default key formatter.
Definition: Key.cpp:30
Key.h
gtsam::print
void print(const Matrix &A, const string &s, ostream &stream)
Definition: Matrix.cpp:155
FastSet.h
A thin wrapper around std::set that uses boost's fast_pool_allocator.
gtsam::Ordering::ColamdConstrainedFirst
static Ordering ColamdConstrainedFirst(const FACTOR_GRAPH &graph, const KeyVector &constrainFirst, bool forceOrder=false)
Definition: inference/Ordering.h:139
gtsam::Ordering::Colamd
static Ordering Colamd(const FACTOR_GRAPH &graph)
Definition: inference/Ordering.h:93
gtsam::KeyFormatter
std::function< std::string(Key)> KeyFormatter
Typedef for a function to format a key, i.e. to convert it to a string.
Definition: Key.h:35
gtsam::Ordering::Base
KeyVector Base
Definition: inference/Ordering.h:35
gtsam::MetisIndex
Definition: MetisIndex.h:37
gtsam::Ordering::ColamdConstrained
static Ordering ColamdConstrained(const FACTOR_GRAPH &graph, const FastMap< Key, int > &groups)
Definition: inference/Ordering.h:168
conf.version
version
Definition: gtsam/3rdparty/GeographicLib/python/doc/conf.py:67
gtsam::VariableIndex
Definition: VariableIndex.h:41
gtsam::equals
Definition: Testable.h:112
str
Definition: pytypes.h:1524
key
const gtsam::Symbol key('X', 0)
gtsam::Ordering::OrderingType
OrderingType
Type of ordering to use.
Definition: inference/Ordering.h:40
gtsam::Ordering::Metis
static Ordering Metis(const FACTOR_GRAPH &graph)
Definition: inference/Ordering.h:204
xadj
idx_t idx_t * xadj
Definition: include/metis.h:197
gtsam
traits
Definition: chartTesting.h:28
gtsam::Testable
Definition: Testable.h:152
gtsam::traits
Definition: Group.h:36
VariableIndex.h
This
#define This
Definition: ActiveSetSolver-inl.h:27
gtsam::tol
const G double tol
Definition: Group.h:79
gtsam::Ordering::Natural
static Ordering Natural(const FACTOR_GRAPH &fg)
Return a natural Ordering. Typically used by iterative solvers.
Definition: inference/Ordering.h:188
MetisIndex.h
Eigen::placeholders::end
static const EIGEN_DEPRECATED end_t end
Definition: IndexedViewHelper.h:181
Base
Definition: test_virtual_functions.cpp:156
graph
NonlinearFactorGraph graph
Definition: doc/Code/OdometryExample.cpp:2
gtsam::Key
std::uint64_t Key
Integer nonlinear key type.
Definition: types.h:97
Eigen::bfloat16_impl::operator+=
EIGEN_STRONG_INLINE EIGEN_DEVICE_FUNC bfloat16 & operator+=(bfloat16 &a, const bfloat16 &b)
Definition: BFloat16.h:184
gtsam::Ordering
Definition: inference/Ordering.h:33
pybind_wrapper_test_script.other
other
Definition: pybind_wrapper_test_script.py:42


gtsam
Author(s):
autogenerated on Thu Jun 13 2024 03:03:52