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