hyper_graph.h

Go to the documentation of this file.

// g2o - General Graph Optimization
// Copyright (C) 2011 R. Kuemmerle, G. Grisetti, W. Burgard
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// * Redistributions of source code must retain the above copyright notice,
//   this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright
//   notice, this list of conditions and the following disclaimer in the
//   documentation and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
// TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
// PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
// TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#ifndef G2O_AIS_HYPER_GRAPH_HH
#define G2O_AIS_HYPER_GRAPH_HH

#include <map>
#include <set>
#include <bitset>
#include <cassert>
#include <vector>
#include <limits>
#include <cstddef>

#include <unordered_map>

#include "g2o_core_api.h"

namespace g2o {

  class G2O_CORE_API HyperGraph
  {
    public:

      enum G2O_CORE_API HyperGraphElementType {
        HGET_VERTEX,
        HGET_EDGE,
        HGET_PARAMETER,
        HGET_CACHE,
        HGET_DATA,
        HGET_NUM_ELEMS // keep as last elem
      };

      static const int UnassignedId = -1;
      static const int InvalidId = -2;

      typedef std::bitset<HyperGraph::HGET_NUM_ELEMS> GraphElemBitset;

      class G2O_CORE_API Data;
      class G2O_CORE_API DataContainer;
      class G2O_CORE_API Vertex;
      class G2O_CORE_API Edge;
      
      struct G2O_CORE_API HyperGraphElement {
        virtual ~HyperGraphElement() {}
        virtual HyperGraphElementType elementType() const = 0;
        HyperGraphElement* clone() const { return 0; }
      };

      class G2O_CORE_API Data : public HyperGraph::HyperGraphElement {
        public:
          Data();
          ~Data();
          virtual bool read(std::istream& is) = 0;
          virtual bool write(std::ostream& os) const = 0;
          virtual HyperGraph::HyperGraphElementType elementType() const { return HyperGraph::HGET_DATA;}
          inline const Data* next() const {return _next;}
          inline Data* next() {return _next;}
          inline void setNext(Data* next_) { _next = next_; }
          inline DataContainer* dataContainer() { return _dataContainer;}
          inline const DataContainer* dataContainer() const { return _dataContainer;}
          inline void setDataContainer(DataContainer * dataContainer_){ _dataContainer = dataContainer_;}
        protected:
          Data* _next; // linked list of multiple data;
          DataContainer* _dataContainer;
      };

      class G2O_CORE_API DataContainer {
        public:
          DataContainer() {_userData = 0;}
          virtual ~DataContainer() { delete _userData;}
          const Data* userData() const { return _userData; }
          Data* userData() { return _userData; }
          void setUserData(Data* obs) { _userData = obs;}
          void addUserData(Data* obs) { if (obs) { obs->setNext(_userData); _userData=obs; } }
        protected:
          Data* _userData;
      };


      typedef std::set<Edge*>                           EdgeSet;
      typedef std::set<Vertex*>                         VertexSet;

      typedef std::unordered_map<int, Vertex*>     VertexIDMap;
      typedef std::vector<Vertex*>                      VertexContainer;

      class G2O_CORE_API Vertex : public HyperGraphElement {
        public:
          explicit Vertex(int id=InvalidId);
          virtual ~Vertex();
          int id() const {return _id;}
          virtual void setId( int newId) { _id=newId; }
          const EdgeSet& edges() const {return _edges;}
          EdgeSet& edges() {return _edges;}
          virtual HyperGraphElementType elementType() const { return HGET_VERTEX;}
        protected:
          int _id;
          EdgeSet _edges;
      };


      class G2O_CORE_API Edge : public HyperGraphElement {
        public:
          explicit Edge(int id = InvalidId);
          virtual ~Edge();

          virtual void resize(size_t size);
          const VertexContainer& vertices() const { return _vertices;}
          VertexContainer& vertices() { return _vertices;}
          const Vertex* vertex(size_t i) const { assert(i < _vertices.size() && "index out of bounds"); return _vertices[i];}
          Vertex* vertex(size_t i) { assert(i < _vertices.size() && "index out of bounds"); return _vertices[i];}
          void setVertex(size_t i, Vertex* v) { assert(i < _vertices.size() && "index out of bounds"); _vertices[i]=v;}

          int id() const {return _id;}
          void setId(int id);
          virtual HyperGraphElementType elementType() const { return HGET_EDGE;}

          int numUndefinedVertices() const;
        protected:
          VertexContainer _vertices;
          int _id; 
      };

    public:
      HyperGraph();
      virtual ~HyperGraph();

      Vertex* vertex(int id);
      const Vertex* vertex(int id) const;

      virtual bool removeVertex(Vertex* v, bool detach=false);
      virtual bool removeEdge(Edge* e);
      virtual void clear();

      const VertexIDMap& vertices() const {return _vertices;}
      VertexIDMap& vertices() {return _vertices;}

      const EdgeSet& edges() const {return _edges;}
      EdgeSet& edges() {return _edges;}

      virtual bool addVertex(Vertex* v);

      virtual bool addEdge(Edge* e);


      virtual bool setEdgeVertex(Edge* e, int pos, Vertex* v);

      virtual bool mergeVertices(Vertex* vBig, Vertex* vSmall, bool erase);

      virtual bool detachVertex(Vertex* v);

      virtual bool changeId(Vertex* v, int newId);

    protected:
      VertexIDMap _vertices;
      EdgeSet _edges;

    private:
      // Disable the copy constructor and assignment operator
      HyperGraph(const HyperGraph&) { }
      HyperGraph& operator= (const HyperGraph&) { return *this; }
  };

} // end namespace


#endif