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