GraphInt.hh

Go to the documentation of this file.

#ifndef __DIADES__GRAPH__GRAPHDATA__HH
#define __DIADES__GRAPH__GRAPHDATA__HH

#include <list>
#include <diades/graph/GraphGen.hh>
#include <diades/graph/EdgeData.hh>
#include <diades/graph/NodeData.hh>
#include <diades/graph/Edge.hh>
#include <diades/graph/Node.hh>


 


namespace Diades {
    namespace Graph {

        template<typename Any>
        struct GraphIterator {

            static string typeName() {
                return "Graph::GraphIterator";
            }
            typedef Diades::Utils::Exception<GraphIterator> Exception;
            


            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;

            typedef typename vector<value_type>::size_type SizeType;

            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(Exception, (_index == _pVect->size()) || (_index < _pVect->size() && (*_pVect)[_index].valid()),
                        "constructor()");
            }

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

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

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

            self operator++(int) {
                self tmp = *this;
                ++_index;
                while ((_index < _pVect->size()) && !((*_pVect)[_index].valid())) {
                    ++_index;
                }
                ensure(Exception, (_index == _pVect->size()) || (_index < _pVect->size() && (*_pVect)[_index].valid()),
                        "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 GraphIterator<Node> NodeIterator;
        typedef GraphIterator<Edge> EdgeIterator;

        class Graph {
        public:
             static string typeName() {
                return "Graph::Graph";
            }
            typedef Diades::Utils::Exception<Graph> Exception;
            typedef vector<Edge>::size_type EdgeSizeType;
            typedef vector<Node>::size_type NodeSizeType;
            typedef Edge::EdgeId EdgeId;
            typedef Node::NodeId NodeId;
            
            
            
            
        private:
            mutable vector<Edge> _vEdges; // list of edges
            mutable vector<Node> _vNodes; // list of nodes
            list<EdgeSizeType> _listEdgeId; // list of unused identifers for edges
            list<NodeSizeType> _listNodeId; // list of unused identifiers for nodes
            NodeSizeType _nbNodes;
            EdgeSizeType _nbEdges;
            unsigned _id;
            
            void copyGraph(const Graph & graph);

        public: // for serialization

            vector<Edge> & vEdges() {
                return _vEdges;
            }

            vector<Node> & vNodes() {
                return _vNodes;
            }

            list<EdgeSizeType> & listEdgeId() {
                return _listEdgeId;
            }

            list<NodeSizeType> & listNodeId() {
                return _listNodeId;
            }

            const vector<Edge> & vEdges() const {
                return _vEdges;
            }

            const vector<Node> & vNodes() const {
                return _vNodes;
            }

            const list<EdgeSizeType> & listEdgeId() const {
                return _listEdgeId;
            }

            const list<NodeSizeType> & listNodeId() const {
                return _listNodeId;
            }

            unsigned id() const {
                return _id;
            }

        public:


            Graph();

            Graph(const Graph & graph);
           

            virtual ~Graph();
            
            
            Graph & operator=(const Graph & graph)
            {
                if(this != &graph)
                {
                    copyGraph(graph);
                }
                return (*this);
            }




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


            bool succeeds(const Node & n1, const Node & n2) const;

            NodeSizeType numberOfNodes() const {
                return _nbNodes;
            }

            EdgeSizeType numberOfEdges() const {
                return _nbEdges;
            }

            bool empty() const {
                return numberOfNodes() == 0;
            }


            Node target(const Edge & edge) const;
            

            Node source(const Edge & edge) const;



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

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





            bool cycleDetection(const Node & n) const;




            Node newNode();


            Node newNode(NodeSizeType index);

            Node getNode(NodeSizeType index) const;

            Edge getEdge(EdgeSizeType index) const;


            Edge newEdge(Node source, Node target);



            Edge newEdge(EdgeSizeType 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


            // /** 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;

            EdgeSizeType edgeCapacity() const {
                return _vEdges.size();
            }

            NodeSizeType nodeCapacity() const {
                return _vNodes.size();
            }


            bool sanityCheck(string & log) const;

            ostream & toDot(ostream & os);


            void transitiveClosure(Edge edge);

        };

        template<typename InputIterator>
        inline void deleteEdge(Graph & g, InputIterator first, InputIterator last) {
            for (; first != last; ++first) {
                g.deleteEdge(*first);
            }
        }

        template<typename InputIterator>
        inline void deleteNode(Graph & g, InputIterator first, InputIterator last) {
            for (; first != last; ++first) {
                g.deleteNode(*first);
            }
        }

        template<typename InputIterator, typename Predicate>
        inline void deleteNode(Graph & g, InputIterator first, InputIterator last, Predicate pred) {
            for (; first != last; ++first) {
                if (pred()(*first)) {
                    g.deleteNode(*first);
                }
            }
        }
                
                
                
                

    };
};

#endif