Tulip  5.0.0
Large graphs analysis and drawing
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
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 #include <set>
25 
26 #include <vector>
27 #include <list>
28 #include <tulip/GraphAbstract.h>
29 #include <tulip/GraphStorage.h>
30 #include <tulip/IdManager.h>
31 
32 namespace tlp {
33 template<class itType >
34 struct Iterator;
35 class GraphView;
36 class GraphUpdatesRecorder;
37 
38 ///Implementation of the graph support of the Graph.
39 class TLP_SCOPE GraphImpl:public GraphAbstract {
40 
41  friend class GraphUpdatesRecorder;
42  friend class TLPExport;
43 
44 public:
45  GraphImpl();
46  ~GraphImpl();
47  void clear();
48  //=========================================================================
49  inline bool isElement(const node n) const {
50  return storage.isElement(n);
51  }
52  bool isElement(const edge e) const {
53  return storage.isElement(e);
54  }
55  edge existEdge(const node source, const node target,
56  bool directed = true) const;
57  node addNode();
58  void addNodes(unsigned int nb);
59  void addNodes(unsigned int nb, std::vector<node>& addedNodes);
60  void addNode(const node);
61  void addNodes(Iterator<node>* nodes);
62  edge addEdge(const node ,const node);
63  void addEdges(const std::vector<std::pair<node, node> >& edges);
64  void addEdges(const std::vector<std::pair<node, node> >& edges,
65  std::vector<edge>& addedEdges);
66  void addEdge(const edge);
67  void addEdges(Iterator<edge>* edges);
68  void delNode(const tlp::node n, bool deleteInAllGraphs = false);
69  void delEdge(const tlp::edge e, bool deleteInAllGraphs = false);
70  inline void setEdgeOrder(const node n,const std::vector<edge> &v) {
71  storage.setEdgeOrder(n, v);
72  }
73  inline void swapEdgeOrder(const node n, const edge e1, const edge e2) {
74  storage.swapEdgeOrder(n, e1, e2);
75  }
76  //=========================================================================
77  inline const std::vector<node>& nodes() const {
78  return storage.nodes();
79  }
80  inline unsigned int nodePos(const node n) const {
81  return storage.nodePos(n);
82  }
83  Iterator<node>* getNodes() const;
84  Iterator<node>* getInNodes(const node) const;
85  Iterator<node>* getOutNodes(const node) const;
86  Iterator<node>* getInOutNodes(const node) const;
87  inline const std::vector<edge>& edges() const {
88  return storage.edges();
89  }
90  inline unsigned int edgePos(const edge e) const {
91  return storage.edgePos(e);
92  }
93  Iterator<edge>* getEdges() const;
94  Iterator<edge>* getInEdges(const node) const;
95  Iterator<edge>* getOutEdges(const node) const;
96  Iterator<edge>* getInOutEdges(const node) const;
97  std::vector<edge> getEdges(const node source, const node target,
98  bool directed = true) const;
99  bool getEdges(const node source, const node target, bool directed,
100  std::vector<edge>& edges, const Graph* sg = NULL,
101  bool onlyFirst = false) const {
102  return storage.getEdges(source, target, directed, edges, sg, onlyFirst);
103  }
104  inline const std::vector<edge>& allEdges(const node n) const {
105  return storage.adj(n);
106  }
107  //========================================================================
108  inline unsigned int deg(const node n) const {
109  assert(isElement(n));
110  return storage.deg(n);
111  }
112  inline unsigned int indeg(const node n) const {
113  assert(isElement(n));
114  return storage.indeg(n);
115  }
116  inline unsigned int outdeg(const node n) const {
117  assert(isElement(n));
118  return storage.outdeg(n);
119  }
120  //========================================================================
121  inline node source(const edge e) const {
122  assert(isElement(e));
123  return storage.source(e);
124  }
125  inline node target(const edge e) const {
126  assert(isElement(e));
127  return storage.target(e);
128  }
129  inline node opposite(const edge e, const node n) const {
130  assert(isElement(e));
131  return storage.opposite(e, n);
132  }
133  inline const std::pair<node, node>& ends(const edge e) const {
134  return storage.ends(e);
135  }
136  inline void setSource(const edge e, const node newSrc) {
137  assert(isElement(e));
138  this->setEnds(e, newSrc, node());
139  }
140  inline void setTarget(const edge e, const node newTgt) {
141  assert(isElement(e));
142  this->setEnds(e, node(), newTgt);
143  }
144  void setEnds(const edge, const node, const node);
145  void reverse(const edge);
146  //=======================================================================
147  inline unsigned int numberOfEdges() const {
148  return storage.numberOfEdges();
149  }
150  inline unsigned int numberOfNodes() const {
151  return storage.numberOfNodes();
152  }
153  inline void sortElts() {
154  storage.sortElts();
155  }
156  //=======================================================================
157  // updates management
158  virtual void push(bool unpopAllowed = true,
159  std::vector<PropertyInterface*>* propertiesToPreserveOnPop= NULL);
160  virtual void pop(bool unpopAllowed = true);
161  virtual void popIfNoUpdates();
162  virtual void unpop();
163  virtual bool canPop();
164  virtual bool canUnpop();
165  virtual bool canPopThenUnpop();
166 
167  // observer interface
168  void treatEvents(const std::vector<Event> &);
169 
170  // for subgraph id management
171  unsigned int getSubGraphId(unsigned int id);
172  void freeSubGraphId(unsigned int id);
173 
174  // to improve memory allocation
175  // attempt to reserve enough space to store nodes/edges
176  virtual void reserveNodes(unsigned int nbNodes);
177  virtual void reserveEdges(unsigned int nbEdges);
178 
179 protected:
180  // designed to reassign an id to a previously deleted elt
181  // used by GraphUpdatesRecorder
182  virtual void restoreNode(node);
183  virtual void restoreEdge(edge, node source, node target);
184  // designed to only update own structures
185  // used by GraphUpdatesRecorder
186  virtual void removeNode(const node);
187  virtual void removeEdge(const edge);
188  // used by PropertyManager
189  virtual bool canDeleteProperty(Graph* g, PropertyInterface *prop);
190 
191 private :
192  GraphStorage storage;
193  IdManager graphIds;
194  std::list<GraphUpdatesRecorder*> previousRecorders;
195  std::list<Graph *> observedGraphs;
196  std::list<PropertyInterface*> observedProps;
197  std::list<GraphUpdatesRecorder*> recorders;
198 
199  void observeUpdates(Graph*);
200  void unobserveUpdates();
201  void delPreviousRecorders();
202 };
203 
204 }
205 #endif
206 
207 ///@endcond
Interface for Tulip iterators. Allows basic iteration operations only.
Definition: Iterator.h:39
The edge struct represents an edge in a Graph object.
Definition: Edge.h:39
The node struct represents a node in a Graph object.
Definition: Node.h:39