Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/GraphImpl.h
00001 /*
00002  *
00003  * This file is part of Tulip (www.tulip-software.org)
00004  *
00005  * Authors: David Auber and the Tulip development Team
00006  * from LaBRI, University of Bordeaux
00007  *
00008  * Tulip is free software; you can redistribute it and/or modify
00009  * it under the terms of the GNU Lesser General Public License
00010  * as published by the Free Software Foundation, either version 3
00011  * of the License, or (at your option) any later version.
00012  *
00013  * Tulip is distributed in the hope that it will be useful,
00014  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00015  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
00016  * See the GNU General Public License for more details.
00017  *
00018  */
00019 ///@cond DOXYGEN_HIDDEN
00020 
00021 #ifndef Tulip_SUPERGRAPHIMPL_H
00022 #define Tulip_SUPERGRAPHIMPL_H
00023 
00024 #ifndef DOXYGEN_NOTFOR_USER
00025 
00026 #include <set>
00027 
00028 #include <vector>
00029 #include <list>
00030 #include <tulip/GraphAbstract.h>
00031 #include <tulip/GraphStorage.h>
00032 #include <tulip/IdManager.h>
00033 
00034 namespace tlp {
00035 template<class itType >
00036 struct Iterator;
00037 class GraphView;
00038 class GraphUpdatesRecorder;
00039 
00040 ///Implementation of the graph support of the Graph.
00041 class TLP_SCOPE GraphImpl:public GraphAbstract {
00042 
00043   friend class GraphUpdatesRecorder;
00044   friend class TLPExport;
00045 
00046 public:
00047   GraphImpl();
00048   ~GraphImpl();
00049   void clear();
00050   //=========================================================================
00051   bool isElement(const node ) const;
00052   bool isElement(const edge ) const;
00053   edge existEdge(const node source, const node target,
00054                  bool directed = true) const;
00055   node addNode();
00056   void addNodes(unsigned int nb, std::vector<node>& addedNodes);
00057   void addNode(const node);
00058   void addNodes(Iterator<node>* nodes);
00059   edge addEdge(const node ,const node);
00060   void addEdges(const std::vector<std::pair<node, node> >& edges,
00061                 std::vector<edge>& addedEdges);
00062   void addEdge(const edge);
00063   void addEdges(Iterator<edge>* edges);
00064   void delNode(const tlp::node n, bool deleteInAllGraphs = false);
00065   void delEdge(const tlp::edge e, bool deleteInAllGraphs = false);
00066   void setEdgeOrder(const node,const std::vector<edge> & );
00067   void swapEdgeOrder(const node,const edge , const edge );
00068   //=========================================================================
00069   Iterator<node>* getNodes() const;
00070   Iterator<node>* getInNodes(const node )const;
00071   Iterator<node>* getOutNodes(const node )const;
00072   Iterator<node>* getInOutNodes(const node )const;
00073   Iterator<edge>* getEdges()const;
00074   Iterator<edge>* getInEdges(const node )const;
00075   Iterator<edge>* getOutEdges(const node )const;
00076   Iterator<edge>* getInOutEdges(const node )const;
00077   std::vector<edge> getEdges(const node source, const node target,
00078                              bool directed = true) const;
00079   bool getEdges(const node source, const node target, bool directed,
00080                 std::vector<edge>& edges) const {
00081     return storage.getEdges(source, target, directed, edges);
00082   }
00083   // to ensure that loops appear only once
00084   void getInOutEdges(const node, std::vector<edge>& edges,
00085                      bool loopsOnlyOnce = false)const;
00086   //========================================================================
00087   unsigned int deg(const node ) const;
00088   unsigned int indeg(const node) const;
00089   unsigned int outdeg(const node) const;
00090   //========================================================================
00091   virtual node source(const edge) const;
00092   virtual node target(const edge) const;
00093   virtual node opposite(const edge, const node n) const;
00094   virtual const std::pair<node, node>& ends(const edge e) const;
00095   virtual void setEnds(const edge, const node, const node);
00096   virtual void reverse(const edge);
00097   //=======================================================================
00098   unsigned int numberOfEdges()const;
00099   unsigned int numberOfNodes()const;
00100   //=======================================================================
00101   // updates management
00102   virtual void push(bool unpopAllowed = true,
00103                     std::vector<PropertyInterface*>* propertiesToPreserveOnPop= NULL);
00104   virtual void pop(bool unpopAllowed = true);
00105   virtual void unpop();
00106   virtual bool canPop();
00107   virtual bool canUnpop();
00108   virtual bool canPopThenUnpop();
00109 
00110   // observer interface
00111   void treatEvents(const std::vector<Event> &);
00112 
00113   // for subgraph id management
00114   unsigned int getSubGraphId(unsigned int id);
00115   void freeSubGraphId(unsigned int id);
00116 
00117   // to improve memory allocation
00118   // attempt to reserve enough space to store nodes/edges
00119   virtual void reserveNodes(unsigned int nbNodes);
00120   virtual void reserveEdges(unsigned int nbEdges);
00121 
00122 protected:
00123   // designed to reassign an id to a previously deleted elt
00124   // used by GraphUpdatesRecorder
00125   virtual node restoreNode(node);
00126   virtual void restoreNodes(const std::vector<node>&);
00127   virtual edge restoreEdge(edge, node source, node target);
00128   virtual void restoreEdges(const std::vector<edge>& edges,
00129                             const std::vector<std::pair<node, node> >& ends);
00130   // designed to only update own structures
00131   // used by GraphUpdatesRecorder
00132   virtual void removeNode(const node);
00133   virtual void removeEdge(const edge);
00134   // used by PropertyManager
00135   virtual bool canDeleteProperty(Graph* g, PropertyInterface *prop);
00136 
00137 private :
00138   GraphStorage storage;
00139   IdManager graphIds;
00140   std::list<GraphUpdatesRecorder*> previousRecorders;
00141   std::list<Graph *> observedGraphs;
00142   std::list<PropertyInterface*> observedProps;
00143   std::list<GraphUpdatesRecorder*> recorders;
00144 
00145   void restoreAdj(node, std::vector<edge>&);
00146   void observeUpdates(Graph*);
00147   void unobserveUpdates();
00148   void delPreviousRecorders();
00149 };
00150 
00151 }
00152 #endif
00153 
00154 #endif
00155 ///@endcond
 All Classes Files Functions Variables Enumerations Enumerator Properties