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