Loading...
Searching...
No Matches
Ordering.h
Go to the documentation of this file.
/* ----------------------------------------------------------------------------
* GTSAM Copyright 2010, Georgia Tech Research Corporation,
* Atlanta, Georgia 30332-0415
* All Rights Reserved
* Authors: Frank Dellaert, et al. (see THANKS for the full author list)
* See LICENSE for the license information
* -------------------------------------------------------------------------- */
#pragma once
#include <gtsam/inference/Key.h>
#include <gtsam/inference/VariableIndex.h>
#include <gtsam/inference/MetisIndex.h>
#include <gtsam/base/FastSet.h>
#include <boost/assign/list_inserter.hpp>
#include <algorithm>
#include <vector>
namespace gtsam {
class Ordering: public KeyVector {
protected:
typedef KeyVector Base;
public:
enum OrderingType {
COLAMD, METIS, NATURAL, CUSTOM
};
typedef Ordering This;
typedef boost::shared_ptr<This> shared_ptr;
GTSAM_EXPORT
Ordering() {
}
using KeyVector::KeyVector; // Inherit the KeyVector's constructors
template<typename KEYS>
explicit Ordering(const KEYS& keys) :
Base(keys.begin(), keys.end()) {
}
boost::assign::list_inserter<boost::assign_detail::call_push_back<This> > operator+=(
Key key) {
return boost::assign::make_list_inserter(
boost::assign_detail::call_push_back<This>(*this))(key);
}
This& operator+=(KeyVector& keys);
bool contains(const Key& key) const;
FastMap<Key, size_t> invert() const;
template<class FACTOR_GRAPH>
static Ordering Colamd(const FACTOR_GRAPH& graph) {
if (graph.empty())
return Ordering();
else
return Colamd(VariableIndex(graph));
}
static GTSAM_EXPORT Ordering Colamd(const VariableIndex& variableIndex);
template<class FACTOR_GRAPH>
static Ordering ColamdConstrainedLast(const FACTOR_GRAPH& graph,
const KeyVector& constrainLast, bool forceOrder = false) {
if (graph.empty())
return Ordering();
else
return ColamdConstrainedLast(VariableIndex(graph), constrainLast, forceOrder);
}
static GTSAM_EXPORT Ordering ColamdConstrainedLast(
const VariableIndex& variableIndex, const KeyVector& constrainLast,
bool forceOrder = false);
template<class FACTOR_GRAPH>
static Ordering ColamdConstrainedFirst(const FACTOR_GRAPH& graph,
const KeyVector& constrainFirst, bool forceOrder = false) {
if (graph.empty())
return Ordering();
else
return ColamdConstrainedFirst(VariableIndex(graph), constrainFirst, forceOrder);
}
static GTSAM_EXPORT Ordering ColamdConstrainedFirst(
const VariableIndex& variableIndex,
const KeyVector& constrainFirst, bool forceOrder = false);
template<class FACTOR_GRAPH>
static Ordering ColamdConstrained(const FACTOR_GRAPH& graph,
const FastMap<Key, int>& groups) {
if (graph.empty())
return Ordering();
else
return ColamdConstrained(VariableIndex(graph), groups);
}
static GTSAM_EXPORT Ordering ColamdConstrained(
const VariableIndex& variableIndex, const FastMap<Key, int>& groups);
template<class FACTOR_GRAPH>
static Ordering Natural(const FACTOR_GRAPH &fg) {
KeySet src = fg.keys();
KeyVector keys(src.begin(), src.end());
std::stable_sort(keys.begin(), keys.end());
return Ordering(keys.begin(), keys.end());
}
template<class FACTOR_GRAPH>
static GTSAM_EXPORT void CSRFormat(std::vector<int>& xadj,
std::vector<int>& adj, const FACTOR_GRAPH& graph);
static GTSAM_EXPORT Ordering Metis(const MetisIndex& met);
template<class FACTOR_GRAPH>
static Ordering Metis(const FACTOR_GRAPH& graph) {
if (graph.empty())
return Ordering();
else
return Metis(MetisIndex(graph));
}
template<class FACTOR_GRAPH>
static Ordering Create(OrderingType orderingType,
const FACTOR_GRAPH& graph) {
if (graph.empty())
return Ordering();
switch (orderingType) {
case COLAMD:
return Colamd(graph);
case METIS:
return Metis(graph);
case NATURAL:
return Natural(graph);
case CUSTOM:
throw std::runtime_error(
"Ordering::Create error: called with CUSTOM ordering type.");
default:
throw std::runtime_error(
"Ordering::Create error: called with unknown ordering type.");
}
}
GTSAM_EXPORT
void print(const std::string& str = "", const KeyFormatter& keyFormatter =
DefaultKeyFormatter) const;
GTSAM_EXPORT
bool equals(const Ordering& other, double tol = 1e-9) const;
private:
static GTSAM_EXPORT Ordering ColamdConstrained(
const VariableIndex& variableIndex, std::vector<int>& cmember);
friend class boost::serialization::access;
template<class ARCHIVE>
void serialize(ARCHIVE & ar, const unsigned int version) {
ar & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Base);
}
};
template<> struct traits<Ordering> : public Testable<Ordering> {
};
}
FastSet.h
A thin wrapper around std::set that uses boost's fast_pool_allocator.
MetisIndex.h
VariableIndex.h
Key.h
gtsam
Global functions in a separate testing namespace.
Definition chartTesting.h:28
gtsam::KeyVector
FastVector< Key > KeyVector
Define collection type once and for all - also used in wrappers.
Definition Key.h:86
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::Key
std::uint64_t Key
Integer nonlinear key type.
Definition types.h:100
gtsam::traits
A manifold defines a space in which there is a notion of a linear tangent space that can be centered ...
Definition concepts.h:30
gtsam::FastMap
FastMap is a thin wrapper around std::map that uses the boost fast_pool_allocator instead of the defa...
Definition FastMap.h:38
gtsam::Testable
A helper that implements the traits interface for GTSAM types.
Definition Testable.h:151
gtsam::MetisIndex
The MetisIndex class converts a factor graph into the Compressed Sparse Row format for use in METIS a...
Definition MetisIndex.h:45
gtsam::Ordering
Definition Ordering.h:34
gtsam::Ordering::Natural
static Ordering Natural(const FACTOR_GRAPH &fg)
Return a natural Ordering. Typically used by iterative solvers.
Definition Ordering.h:190
gtsam::Ordering::ColamdConstrained
static Ordering ColamdConstrained(const FACTOR_GRAPH &graph, const FastMap< Key, int > &groups)
Compute a fill-reducing ordering using constrained COLAMD from a factor graph (see details for note o...
Definition Ordering.h:170
gtsam::Ordering::Ordering
Ordering(const KEYS &keys)
Create from a container.
Definition Ordering.h:57
gtsam::Ordering::Colamd
static Ordering Colamd(const FACTOR_GRAPH &graph)
Compute a fill-reducing ordering using COLAMD from a factor graph (see details for note on performanc...
Definition Ordering.h:95
gtsam::Ordering::OrderingType
OrderingType
Type of ordering to use.
Definition Ordering.h:41
gtsam::Ordering::ColamdConstrainedLast
static Ordering ColamdConstrainedLast(const FACTOR_GRAPH &graph, const KeyVector &constrainLast, bool forceOrder=false)
Compute a fill-reducing ordering using constrained COLAMD from a factor graph (see details for note o...
Definition Ordering.h:114
gtsam::Ordering::shared_ptr
boost::shared_ptr< This > shared_ptr
shared_ptr to this class
Definition Ordering.h:46
gtsam::Ordering::operator+=
boost::assign::list_inserter< boost::assign_detail::call_push_back< This > > operator+=(Key key)
Add new variables to the ordering as ordering += key1, key2, ... Equivalent to calling push_back.
Definition Ordering.h:63
gtsam::Ordering::ColamdConstrainedFirst
static Ordering ColamdConstrainedFirst(const FACTOR_GRAPH &graph, const KeyVector &constrainFirst, bool forceOrder=false)
Compute a fill-reducing ordering using constrained COLAMD from a factor graph (see details for note o...
Definition Ordering.h:141
gtsam::Ordering::Ordering
GTSAM_EXPORT Ordering()
Create an empty ordering.
Definition Ordering.h:50
gtsam::Ordering::Metis
static GTSAM_EXPORT Ordering Metis(const MetisIndex &met)
Compute an ordering determined by METIS from a VariableIndex.
Definition Ordering.cpp:212
gtsam::Ordering::invert
FastMap< Key, size_t > invert() const
Invert (not reverse) the ordering - returns a map from key to order position.
Definition Ordering.cpp:36
gtsam::Ordering::access
friend class boost::serialization::access
Serialization function.
Definition Ordering.h:260
gtsam::Ordering::This
Ordering This
Typedef to this class.
Definition Ordering.h:45
gtsam::Ordering::contains
bool contains(const Key &key) const
Check if key exists in ordering.
Definition Ordering.cpp:293
gtsam::Ordering::CSRFormat
static GTSAM_EXPORT void CSRFormat(std::vector< int > &xadj, std::vector< int > &adj, const FACTOR_GRAPH &graph)
METIS Formatting function.
gtsam::VariableIndex
The VariableIndex class computes and stores the block column structure of a factor graph.
Definition VariableIndex.h:43