Tulip  4.2.0
Better Visualization Through Research
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Groups Pages
GraphImpl.h
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux 1 and Inria Bordeaux - Sud Ouest
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 ///@cond DOXYGEN_HIDDEN
20 
21 #ifndef Tulip_SUPERGRAPHIMPL_H
22 #define Tulip_SUPERGRAPHIMPL_H
23 
24 #ifndef DOXYGEN_NOTFOR_USER
25 
26 #include <set>
27 
28 #include <vector>
29 #include <list>
30 #include <tulip/GraphAbstract.h>
31 #include <tulip/GraphStorage.h>
32 #include <tulip/IdManager.h>
33 
34 namespace tlp {
35 template<class itType >
36 struct Iterator;
37 class GraphView;
38 class GraphUpdatesRecorder;
39 
40 ///Implementation of the graph support of the Graph.
41 class TLP_SCOPE GraphImpl:public GraphAbstract {
42 
43  friend class GraphUpdatesRecorder;
44  friend class TLPExport;
45 
46 public:
47  GraphImpl();
48  ~GraphImpl();
49  void clear();
50  //=========================================================================
51  bool isElement(const node ) const;
52  bool isElement(const edge ) const;
53  edge existEdge(const node source, const node target,
54  bool directed = true) const;
55  node addNode();
56  void addNodes(unsigned int nb, std::vector<node>& addedNodes);
57  void addNode(const node);
58  void addNodes(Iterator<node>* nodes);
59  edge addEdge(const node ,const node);
60  void addEdges(const std::vector<std::pair<node, node> >& edges,
61  std::vector<edge>& addedEdges);
62  void addEdge(const edge);
63  void addEdges(Iterator<edge>* edges);
64  void delNode(const tlp::node n, bool deleteInAllGraphs = false);
65  void delEdge(const tlp::edge e, bool deleteInAllGraphs = false);
66  void setEdgeOrder(const node,const std::vector<edge> & );
67  void swapEdgeOrder(const node,const edge , const edge );
68  //=========================================================================
69  Iterator<node>* getNodes() const;
70  Iterator<node>* getInNodes(const node )const;
71  Iterator<node>* getOutNodes(const node )const;
72  Iterator<node>* getInOutNodes(const node )const;
73  Iterator<edge>* getEdges()const;
74  Iterator<edge>* getInEdges(const node )const;
75  Iterator<edge>* getOutEdges(const node )const;
76  Iterator<edge>* getInOutEdges(const node )const;
77  std::vector<edge> getEdges(const node source, const node target,
78  bool directed = true) const;
79  bool getEdges(const node source, const node target, bool directed,
80  std::vector<edge>& edges) const {
81  return storage.getEdges(source, target, directed, edges);
82  }
83  // to ensure that loops appear only once
84  void getInOutEdges(const node, std::vector<edge>& edges,
85  bool loopsOnlyOnce = false)const;
86  //========================================================================
87  unsigned int deg(const node ) const;
88  unsigned int indeg(const node) const;
89  unsigned int outdeg(const node) const;
90  //========================================================================
91  virtual node source(const edge) const;
92  virtual node target(const edge) const;
93  virtual node opposite(const edge, const node n) const;
94  virtual const std::pair<node, node>& ends(const edge e) const;
95  virtual void setEnds(const edge, const node, const node);
96  virtual void reverse(const edge);
97  //=======================================================================
98  unsigned int numberOfEdges()const;
99  unsigned int numberOfNodes()const;
100  //=======================================================================
101  // updates management
102  virtual void push(bool unpopAllowed = true,
103  std::vector<PropertyInterface*>* propertiesToPreserveOnPop= NULL);
104  virtual void pop(bool unpopAllowed = true);
105  virtual void unpop();
106  virtual bool canPop();
107  virtual bool canUnpop();
108  virtual bool canPopThenUnpop();
109 
110  // observer interface
111  void treatEvents(const std::vector<Event> &);
112 
113  // for subgraph id management
114  unsigned int getSubGraphId(unsigned int id);
115  void freeSubGraphId(unsigned int id);
116 
117  // to improve memory allocation
118  // attempt to reserve enough space to store nodes/edges
119  virtual void reserveNodes(unsigned int nbNodes);
120  virtual void reserveEdges(unsigned int nbEdges);
121 
122 protected:
123  // designed to reassign an id to a previously deleted elt
124  // used by GraphUpdatesRecorder
125  virtual node restoreNode(node);
126  virtual void restoreNodes(const std::vector<node>&);
127  virtual edge restoreEdge(edge, node source, node target);
128  virtual void restoreEdges(const std::vector<edge>& edges,
129  const std::vector<std::pair<node, node> >& ends);
130  // designed to only update own structures
131  // used by GraphUpdatesRecorder
132  virtual void removeNode(const node);
133  virtual void removeEdge(const edge);
134  // used by PropertyManager
135  virtual bool canDeleteProperty(Graph* g, PropertyInterface *prop);
136 
137 private :
138  GraphStorage storage;
139  IdManager graphIds;
140  std::list<GraphUpdatesRecorder*> previousRecorders;
141  std::list<Graph *> observedGraphs;
142  std::list<PropertyInterface*> observedProps;
143  std::list<GraphUpdatesRecorder*> recorders;
144 
145  void restoreAdj(node, std::vector<edge>&);
146  void observeUpdates(Graph*);
147  void unobserveUpdates();
148  void delPreviousRecorders();
149 };
150 
151 }
152 #endif
153 
154 #endif
155 ///@endcond