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() {
  }
 
  template<typename KEYS>
  explicit Ordering(const KEYS& keys) :
      Base(keys.begin(), keys.end()) {
  }
 
  template<typename ITERATOR>
  Ordering(ITERATOR firstKey, ITERATOR lastKey) :
      Base(firstKey, lastKey) {
  }
 
  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);
  }
 
  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);
  }
 
  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> {
};
 
}