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 <algorithm>
#include <vector>
 
namespace gtsam {
 
class GTSAM_EXPORT Ordering: public KeyVector {
protected:
  typedef KeyVector Base;
 
public:

  enum OrderingType {
    COLAMD, METIS, NATURAL, CUSTOM
  };
 
  typedef Ordering This; 
  typedef std::shared_ptr<This> shared_ptr; 

  Ordering() {
  }
 
  using KeyVector::KeyVector;  // Inherit the KeyVector's constructors

  template<typename KEYS>
  explicit Ordering(const KEYS& keys) :
      Base(keys.begin(), keys.end()) {
  }

  This& operator+=(Key key);

  // e.g. keys += key1, key2
  This& operator,(Key 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 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 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 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 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 void CSRFormat(std::vector<int>& xadj,
      std::vector<int>& adj, const FACTOR_GRAPH& graph);

  static Ordering Metis(const MetisIndex& met, int seed = 4321);
 
  template<class FACTOR_GRAPH>
  static Ordering Metis(const FACTOR_GRAPH& graph, int seed = 4321) {
    if (graph.empty())
      return Ordering();
    else
      return Metis(MetisIndex(graph), seed);
  }


 
  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.");
    }
  }


 
  void print(const std::string& str = "", const KeyFormatter& keyFormatter =
      DefaultKeyFormatter) const;
 
  bool equals(const Ordering& other, double tol = 1e-9) const;

 
private:
  static Ordering ColamdConstrained(
      const VariableIndex& variableIndex, std::vector<int>& cmember);
 
#if GTSAM_ENABLE_BOOST_SERIALIZATION
  friend class boost::serialization::access;
  template<class ARCHIVE>
  void serialize(ARCHIVE & ar, const unsigned int version) {
    ar & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Base);
  }
#endif
};

template<> struct traits<Ordering> : public Testable<Ordering> {
};
 
}