GraphData.hh

Go to the documentation of this file.

#ifndef __DIADES__GRAPH__GRAPHDATA__HH
#define __DIADES__GRAPH__GRAPHDATA__HH

#include <sstream>
#include <list>
#include <boost/serialization/split_free.hpp>
#include <boost/archive/text_oarchive.hpp>
#include <boost/archive/text_iarchive.hpp>
#include <boost/serialization/list.hpp>
#include <boost/serialization/vector.hpp>
#include "GraphGen.hh"
#include "EdgeData.hh"
#include "NodeData.hh"
#include "Edge.hh"
#include "Node.hh"


namespace std
{

  template<> struct hash<Diades::Graph::Node>
  {
        size_t operator()(const Diades::Graph::Node & node) const { if(node.valid()) { return node.id(); } return 0; }
  };

  template<> struct hash<Diades::Graph::Edge>
  {
        size_t operator()(const  Diades::Graph::Edge & edge) const { if(edge.valid()) { return edge.id(); } return 0; }
  };

};




namespace Diades
{
  namespace Graph
  {
        

        template<typename Any>
        struct GraphIterator
        {
          typedef GraphIterator<Any>   self;
          typedef ptrdiff_t            difference_type;
          typedef std::forward_iterator_tag    iterator_category;
          typedef Any   value_type;
          typedef Any*  pointer;
          typedef Any&  reference;
        

          vector<value_type> * _pVect;
          SizeType _index;

          GraphIterator() : _pVect(),_index() { }
        
          explicit GraphIterator(vector<value_type> * pVect, SizeType index) : _pVect(pVect), _index(index) {
                if(_index < _pVect->size())
                  {
                        if( !(*_pVect)[_index].valid() )
                          {
                                operator++();
                          }
                  }
                else
                  {
                        _index = _pVect->size();
                  }
                ensure(GraphInvalid, (_index == _pVect->size())  ||  (_index < _pVect->size() &&   (*_pVect)[_index].valid()),
                           "GraphIterator::constructor()");
          }

          reference operator*() const
          {
                assertion(GraphInvalid, (_index < _pVect->size() &&   (*_pVect)[_index].valid()), "operator*()");
                return (*_pVect)[_index];
          }

          pointer operator->() const
          {
                assertion(GraphInvalid, (_index < _pVect->size() &&   (*_pVect)[_index].valid()), "operator*()");
                return &(*_pVect)[_index];
          }

          self & operator++()
          {
                ++_index;
                while( (_index <  _pVect->size())
                           && !((*_pVect)[_index].valid()))
                  {       
                        ++_index;
                  }
                ensure(GraphInvalid, (_index == _pVect->size())  ||  (_index < _pVect->size() &&   (*_pVect)[_index].valid()),
                           "GraphIterator::operator++()");
                return *this;
          }

          self operator++(int)
          {
                self tmp = *this;
                ++_index;
                while( (_index <  _pVect->size()) && !((*_pVect)[_index].valid()))
                  {
                        ++_index;
                  }
                ensure(GraphInvalid, (_index == _pVect->size())  ||  (_index < _pVect->size() &&   (*_pVect)[_index].valid()),
                           "GraphIterator::operator++()");
                return tmp;
          }

        

          bool operator==(const self & it) const
          {
                return (_pVect == it._pVect) && (_index == it._index);
          }

          bool operator !=(const self & it) const
          {
                return !(*this == it);
          }

        };
          

  
        //  typedef GraphConstIterator<Node> NodeConstIterator;
        //  typedef GraphConstIterator<Edge> EdgeConstIterator;
        typedef GraphIterator<Node> NodeIterator;
        typedef GraphIterator<Edge> EdgeIterator;
        class Graph;

        class GraphData
        {

        private:
          mutable vector<Edge> _vEdges; // list of edges
          mutable vector<Node> _vNodes; // list of nodes
          list<SizeType> _listEdgeId; // list of unused identifers for edges
          list<SizeType> _listNodeId; // list of unused identifiers for nodes
          SizeType _nbNodes;
          SizeType _nbEdges;
          unsigned _id;

        public: // for serialization
          vector<Edge> & vEdges() { return _vEdges; }
          vector<Node> & vNodes() { return _vNodes; }
          list<SizeType> & listEdgeId() { return _listEdgeId; }
          list<SizeType> & listNodeId() { return _listNodeId; }
          const vector<Edge> & vEdges() const { return _vEdges; }
          const vector<Node> & vNodes() const { return _vNodes; }
          const list<SizeType> & listEdgeId() const { return _listEdgeId; }
          const list<SizeType> & listNodeId() const { return _listNodeId; }
          unsigned id() const { return _id; }
          
        public:
          
          
          GraphData();
          
          virtual ~GraphData();




          //****************** Accessors *********************************


          SizeType numberOfNodes() const
          {
                return _nbNodes;
          }
  
          SizeType numberOfEdges() const
          {
                return _nbEdges;
          }
  
          bool empty() const
          {
                return numberOfNodes()==0;
          }


          const Node & target(const Edge & edge) const;

          const Node & source(const Edge & edge) const;

          



          bool cycleDetection(const Node & n) const;




          const Node & newNode();


          const Node & newNode(SizeType index);

          Node getNode(SizeType index) const;

          Edge getEdge(SizeType index) const;

          
          const Edge & newEdge(Node  source, Node  target);


          
          const Edge & newEdge(SizeType index, Node  source, Node  target);

          
        
          
          virtual void deleteNode(Node & node);




          virtual void deleteNode(NodeIterator start,NodeIterator end);



          virtual void deleteEdge(Edge & edge);



          virtual void deleteEdge(EdgeIterator start, EdgeIterator end);
          virtual void deleteEdge(LocalEdgeIterator start, LocalEdgeIterator end);



          virtual void deleteAllEdges();


          // /** Elimination of edge paths
          //  *  @param s a Node
          //  *  @pre s.valid() && s.owner()==this
          //  *  @post s.outDeg()==0
          //  *
          //  *  Elimination of transition paths from the state s in the current graph.
          //  */
          // virtual void eliminatePathsFrom(Node s);

          void clear();



          NodeIterator nodeBegin() {
                return NodeIterator(&_vNodes,0);
          }

          NodeIterator nodeEnd()  {
                return  NodeIterator(&_vNodes,_vNodes.size());
          }



          NodeIterator nodeBegin() const {
                return NodeIterator(&_vNodes,0);
          }

          NodeIterator nodeEnd()  const {
                return  NodeIterator(&_vNodes,_vNodes.size());
          }


  
 

          EdgeIterator edgeBegin()
          {
                return EdgeIterator(&_vEdges,0);
          }

          EdgeIterator edgeEnd()
          {
                return EdgeIterator(&_vEdges,_vEdges.size());
          }


          EdgeIterator edgeBegin() const
          {
                return EdgeIterator(&_vEdges,0);
          }

          EdgeIterator edgeEnd() const
          {
                return EdgeIterator(&_vEdges,_vEdges.size());
          }

  
          OutEdgeIterator outEdgeBegin(const Node & node) const;

          OutEdgeIterator outEdgeEnd(const Node &  node) const;
          

          InEdgeIterator inEdgeBegin(const Node & node) const;

          InEdgeIterator inEdgeEnd(const Node & node) const;

 

          //@name Others

          GraphData & operator=(const GraphData &);


          // /** Size of a graph
          //  *  @return the memory usage of a graph
          //  **/
          // SizeType memoryUsage() const;
        
          // /** Size of a sub-graph
          //  *  @param transitions to measure
          //  *  @return the memory usage of a sub-graph
          //  **/
          // SizeType memoryUsage(const unordered_set<Edge> & transitions) const;


          // /** Size of a graph (nodes)
          //  *  @return the memory usage of the graph nodes
          //  **/
          // SizeType nodeMemoryUsage() const;

          // /** Size of a graph (edges)
          //  *  @return the memory usage of the graph edges
          //  **/
          // SizeType edgeMemoryUsage() const;



          SizeType edgeCapacity() const { return _vEdges.size(); }
          SizeType nodeCapacity() const { return _vNodes.size(); }


          bool sanityCheck(string & log) const;


         
          friend class Graph;
        };
  };
};

#endif