inference/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> {
};

}