OrientedMatroid.h

//-----------------------------------------------------------------------------
//
// Module:       OrientedMatroid.h
//
// Author:       Feng Xie -- xief@mcmaster.ca
//
// Discription:  Oriented matroid.
//
// Note:
//   1) The index of oriented matroid elements starts from 0.
//
// Change log:
//   09-07-28    Created.
//   09-10-02    Fix memory leak bug by making destructor virtual.
//
// Todo:
//   *) Implement rank method. (Is it really necessary to specify rank in the
//      constructor?)
//   *) remove & contract methods may cause rank to decrease.
//      Currently contract will reduce the rank by 1, is it correct?
//   *) Improve the efficiency of equivalenc check.
//   *) Equality/equivalence check between different representations of OM. 
//      (Currently only the same representations can be compared.)
//
//-----------------------------------------------------------------------------

#ifndef OMC_ORIENTED_MATROID_H
#define OMC_ORIENTED_MATROID_H

#include "Core.h"
#include "Permutation.h"
#include "Combination.h"
#include <set>

namespace omc
{
  class OrientedMatroid
  {
  public:
    enum om_type { empty, alternating };         // oriented matroids types

    OrientedMatroid (size_t, size_t);            // constructor
    
    virtual ~OrientedMatroid () {};              // destructor

    virtual OrientedMatroid* clone () const = 0; // "virtual constructor"

    // Accessors for rank and the number of elements.
    size_t getRank () const;
    size_t getNumElements () const;

    // Interfaces for relabeling.    
    virtual void relabel (index_t, index_t) = 0;    
    virtual void relabel (const Permutation &) = 0;

    // Interfaces for reorientation.
    virtual void reorient (index_t) = 0;             
    virtual void reorient (const std::set<index_t> &) = 0;
    virtual void reorient (const Combination &) = 0;

    // Interfaces for deletion and contraction.
    virtual void remove (index_t);
    virtual void contract (index_t);

    // Interface for equality check.
    virtual bool operator== (const OrientedMatroid &) const = 0;

    // Equivalence check.
    bool equivalent (const OrientedMatroid &);

  protected:
    size_t m_rank, m_numElements;

  private:
    void shrink (index_t);                      // shrink ground set size by 1 
  };


  inline OrientedMatroid::OrientedMatroid (size_t r, size_t n)
    : m_rank (r), m_numElements (n)
  {}
  
  inline size_t OrientedMatroid::getRank () const {
    return m_rank;
  }

  inline size_t OrientedMatroid::getNumElements () const {
    return m_numElements;
  }

  inline void OrientedMatroid::remove (index_t i) {
    shrink (i);
  }

  inline void OrientedMatroid::contract (index_t i) {
    shrink (i);
    m_rank--; // reduce the rank by 1 (?)
  }

}; // namespace omc

#endif

---