Tulip  5.2.1
Large graphs analysis and drawing
GraphUpdatesRecorder.h
1 /*
2  *
3  * This file is part of Tulip (http://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 TLPGRAPHRECORDER_H
22 #define TLPGRAPHRECORDER_H
23 
24 #include <string>
25 #include <set>
26 #include <vector>
27 
28 //#include <tulip/tuliphash.h>
29 #include <tulip/Node.h>
30 //#include <tulip/Edge.h>
31 #include <tulip/Graph.h>
32 //#include <tulip/Observable.h>
33 #include <tulip/MutableContainer.h>
34 
35 namespace std {
36 template <>
37 struct less<tlp::Graph *> {
38  size_t operator()(const tlp::Graph *g1, const tlp::Graph *g2) const {
39  // the id order corresponds to the creation order
40  // so when dealing with a set<Graph*> this will ensure that
41  // we encounter a supergraph before its subgraphs
42  return g1->getId() < g2->getId();
43  }
44 };
45 } // namespace std
46 
47 namespace tlp {
48 
49 struct EdgeRecord {
50  node source;
51  node target;
52  std::set<tlp::Graph *> graphs;
53 
54  EdgeRecord() {}
55  EdgeRecord(Graph *g, node s, node t) : source(s), target(t) {
56  graphs.insert(g);
57  }
58 };
59 
60 struct GraphEltsRecord {
61  Graph *graph;
62  MutableContainer<bool> elts;
63 
64  GraphEltsRecord(Graph *g) : graph(g) {}
65 };
66 
67 } // end of namespace tlp
68 
69 namespace std {
70 template <>
71 struct less<tlp::GraphEltsRecord *> {
72  size_t operator()(const tlp::GraphEltsRecord *g1, const tlp::GraphEltsRecord *g2) const {
73  return g1->graph->getId() < g2->graph->getId();
74  }
75 };
76 } // namespace std
77 
78 namespace tlp {
79 class GraphImpl;
80 class GraphStorageIdsMemento;
81 
82 // various type declarations to ensure correct deletion
83 // of some MutableContainer used as data members
84 // see below
85 typedef GraphEltsRecord *GraphEltsRecordPtr;
86 DECL_STORED_PTR(GraphEltsRecordPtr);
87 typedef std::pair<node, node> *NodePairPtr;
88 DECL_STORED_PTR(NodePairPtr);
89 typedef std::vector<edge> *EdgeVectPtr;
90 DECL_STORED_PTR(EdgeVectPtr);
91 
92 class GraphUpdatesRecorder : public Observable {
93  friend class GraphImpl;
94 //
95 #if !defined(NDEBUG)
96  bool recordingStopped;
97 #endif
98  bool updatesReverted;
99  bool restartAllowed;
100  bool newValuesRecorded;
101  const bool oldIdsStateRecorded;
102 
103  // one 'set' of added nodes per graph
104  MutableContainer<GraphEltsRecordPtr> graphAddedNodes;
105  // the whole 'set' of added nodes
106  MutableContainer<bool> addedNodes;
107  // one 'set' of deleted nodes per graph
108  MutableContainer<GraphEltsRecordPtr> graphDeletedNodes;
109  // one 'set' of added edges per graph
110  MutableContainer<GraphEltsRecord *> graphAddedEdges;
111  // ends of all added edges
112  MutableContainer<NodePairPtr> addedEdgesEnds;
113  // one 'set' of deleted edges per graph
114  MutableContainer<GraphEltsRecord *> graphDeletedEdges;
115  // ends of all deleted edges
116  MutableContainer<NodePairPtr> deletedEdgesEnds;
117  // one set of reverted edges
118  std::set<edge> revertedEdges;
119  // source + target per updated edge
120  TLP_HASH_MAP<edge, std::pair<node, node>> oldEdgesEnds;
121  // source + target per updated edge
122  TLP_HASH_MAP<edge, std::pair<node, node>> newEdgesEnds;
123  // one set for old edge containers
124  MutableContainer<EdgeVectPtr> oldContainers;
125  // one set for new edge containers
126  MutableContainer<EdgeVectPtr> newContainers;
127 
128  // copy of nodes/edges id manager state at start time
129  const GraphStorageIdsMemento *oldIdsState;
130  // copy of nodes/edges id manager state at stop time
131  const GraphStorageIdsMemento *newIdsState;
132 
133  // one list of (parent graph, added subgraph)
134  std::list<std::pair<Graph *, Graph *>> addedSubGraphs;
135  // one list of (parent graph, deleted subgraph)
136  std::list<std::pair<Graph *, Graph *>> deletedSubGraphs;
137 
138  // one set of added properties per graph
139  TLP_HASH_MAP<Graph *, std::set<PropertyInterface *>> addedProperties;
140  // one set of deleted properties per graph
141  TLP_HASH_MAP<Graph *, std::set<PropertyInterface *>> deletedProperties;
142  // one set of old attribute values per graph
143  TLP_HASH_MAP<Graph *, DataSet> oldAttributeValues;
144  // one set of new attribute values per graph
145  TLP_HASH_MAP<Graph *, DataSet> newAttributeValues;
146 
147  // one set of updated addNodes per property
148  TLP_HASH_MAP<PropertyInterface *, std::set<node>> updatedPropsAddedNodes;
149 
150  // one set of updated addEdges per property
151  TLP_HASH_MAP<PropertyInterface *, std::set<edge>> updatedPropsAddedEdges;
152 
153  // the old default node value for each updated property
154  TLP_HASH_MAP<PropertyInterface *, DataMem *> oldNodeDefaultValues;
155  // the new default node value for each updated property
156  TLP_HASH_MAP<PropertyInterface *, DataMem *> newNodeDefaultValues;
157  // the old default edge value for each updated property
158  TLP_HASH_MAP<PropertyInterface *, DataMem *> oldEdgeDefaultValues;
159  // the new default edge value for each updated property
160  TLP_HASH_MAP<PropertyInterface *, DataMem *> newEdgeDefaultValues;
161  // the old name for each renamed property
162  TLP_HASH_MAP<PropertyInterface *, std::string> renamedProperties;
163 
164  struct RecordedValues {
165  PropertyInterface *values;
166  MutableContainer<bool> *recordedNodes;
167  MutableContainer<bool> *recordedEdges;
168 
169  RecordedValues(PropertyInterface *prop = nullptr, MutableContainer<bool> *rn = nullptr,
170  MutableContainer<bool> *re = nullptr)
171  : values(prop), recordedNodes(rn), recordedEdges(re) {}
172  };
173 
174  // the old nodes/edges values for each updated property
175  TLP_HASH_MAP<PropertyInterface *, RecordedValues> oldValues;
176  // the new node value for each updated property
177  TLP_HASH_MAP<PropertyInterface *, RecordedValues> newValues;
178 
179  // real deletion of deleted objects (properties, sub graphs)
180  // during the recording of updates these objects are removed from graph
181  // structures but not really 'deleted'
182  void deleteDeletedObjects();
183  // deletion of recorded values
184  void deleteValues(TLP_HASH_MAP<PropertyInterface *, RecordedValues> &values);
185  // deletion of DataMem default values
186  void deleteDefaultValues(TLP_HASH_MAP<PropertyInterface *, DataMem *> &values);
187  // record of a node's edges container before/after modification
188  void recordEdgeContainer(MutableContainer<std::vector<edge> *> &, GraphImpl *, node);
189  // remove an edge from a node's edges container
190  void removeFromEdgeContainer(MutableContainer<std::vector<edge> *> &containers, edge e, node n);
191 
192  void removeGraphData(Graph *);
193 
194  // record new values for all updated properties
195  // restartAllowed must be true
196  void recordNewValues(GraphImpl *);
197  void recordNewNodeValues(PropertyInterface *p);
198  void recordNewEdgeValues(PropertyInterface *p);
199 
200  // start of recording (push)
201  void startRecording(GraphImpl *);
202  // end of recording
203  // push an other recorder or pop this one
204  void stopRecording(Graph *);
205  // restart of recording (unpop)
206  void restartRecording(Graph *);
207  // perform undo/redo updates
208  void doUpdates(GraphImpl *, bool undo);
209  // check for recorded updates
210  bool hasUpdates();
211  // remove a property from the observed ones
212  // only if nothing is yet recorded for that property
213  bool dontObserveProperty(PropertyInterface *);
214  // check if the property is newly added or deleted
215  bool isAddedOrDeletedProperty(Graph *, PropertyInterface *);
216 
217 public:
218  GraphUpdatesRecorder(bool allowRestart = true,
219  const GraphStorageIdsMemento *prevIdsMemento = nullptr);
220  ~GraphUpdatesRecorder() override;
221 
222  // old GraphObserver interface
223  // graphAddedNodes
224  void addNode(Graph *g, const node n);
225 
226  // graphAddedEdges
227  void addEdge(Graph *g, const edge e);
228 
229  // graphDeletedNodes
230  void delNode(Graph *g, const node n);
231 
232  // graphDeletedEdges
233  void delEdge(Graph *g, const edge e);
234 
235  // revertedEdges
236  void reverseEdge(Graph *g, const edge e);
237 
238  // oldEdgesEnds
239  void beforeSetEnds(Graph *g, const edge e);
240 
241  // newEdgesEnds
242  void afterSetEnds(Graph *g, const edge e);
243 
244  // addedSubGraphs
245  void addSubGraph(Graph *g, Graph *sg);
246 
247  // deletedSubGraphs
248  void delSubGraph(Graph *g, Graph *sg);
249 
250  // addedProperties
251  void addLocalProperty(Graph *g, const std::string &name);
252 
253  // deletedProperties
254  void delLocalProperty(Graph *g, const std::string &name);
255 
256  // beforeSetAttribute
257  void beforeSetAttribute(Graph *g, const std::string &name);
258 
259  // removeAttribute
260  void removeAttribute(Graph *g, const std::string &name);
261 
262  // old PropertyObserver Interface
263  // oldValues
264  void beforeSetNodeValue(PropertyInterface *p, const node n);
265 
266  // oldNodeDefaultValues
267  void beforeSetAllNodeValue(PropertyInterface *p);
268 
269  // oldValues
270  void beforeSetEdgeValue(PropertyInterface *p, const edge e);
271 
272  // oldEdgeDefaultValues
273  void beforeSetAllEdgeValue(PropertyInterface *p);
274 
275  // renamedProperties
276  void propertyRenamed(PropertyInterface *p);
277 
278 protected:
279  // override Observable::treatEvent
280  void treatEvent(const Event &ev) override;
281 };
282 } // namespace tlp
283 
284 #endif // TLPGRAPHRECORDER_H
285 
286 ///@endcond
unsigned int getId() const
Gets the unique identifier of the graph.
Definition: Graph.h:1073