Tulip  5.0.0
Large graphs analysis and drawing
GraphUpdatesRecorder.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 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 }
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 }
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 sub-graph)
134  std::list<std::pair<Graph*, Graph*> > addedSubGraphs;
135  // one list of (parent graph, deleted sub-graph)
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 = NULL,
170  MutableContainer<bool>* rn = NULL,
171  MutableContainer<bool>* re = NULL):
172  values(prop), recordedNodes(rn), recordedEdges(re) {}
173  };
174 
175  // the old nodes/edges values for each updated property
176  TLP_HASH_MAP<PropertyInterface*, RecordedValues> oldValues;
177  // the new node value for each updated property
178  TLP_HASH_MAP<PropertyInterface*, RecordedValues> newValues;
179 
180  // real deletion of deleted objects (properties, sub graphs)
181  // during the recording of updates these objects are removed from graph
182  // structures but not really 'deleted'
183  void deleteDeletedObjects();
184  // deletion of recorded values
185  void deleteValues(TLP_HASH_MAP<PropertyInterface*, RecordedValues>& values);
186  // deletion of DataMem default values
187  void deleteDefaultValues(TLP_HASH_MAP<PropertyInterface*, DataMem*>& values);
188  // record of a node's edges container before/after modification
189  void recordEdgeContainer(MutableContainer<std::vector<edge>*>&,
190  GraphImpl*, node);
191  // remove an edge from a node's edges container
192  void removeFromEdgeContainer(MutableContainer<std::vector<edge>*>& containers,
193  edge e, node n);
194 
195  void removeGraphData(Graph *);
196 
197  // record new values for all updated properties
198  // restartAllowed must be true
199  void recordNewValues(GraphImpl*);
200  void recordNewNodeValues(PropertyInterface* p);
201  void recordNewEdgeValues(PropertyInterface* p);
202 
203  // start of recording (push)
204  void startRecording(GraphImpl*);
205  // end of recording
206  // push an other recorder or pop this one
207  void stopRecording(Graph*);
208  // restart of recording (unpop)
209  void restartRecording(Graph*);
210  // perform undo/redo updates
211  void doUpdates(GraphImpl*, bool undo);
212  // check for recorded updates
213  bool hasUpdates();
214  // remove a property from the observed ones
215  // only if nothing is yet recorded for that property
216  bool dontObserveProperty(PropertyInterface *);
217  // check if the property is newly added or deleted
218  bool isAddedOrDeletedProperty(Graph*, PropertyInterface *);
219 
220 public:
221  GraphUpdatesRecorder(bool allowRestart = true,
222  const GraphStorageIdsMemento* prevIdsMemento = NULL);
223  ~GraphUpdatesRecorder();
224 
225  // old GraphObserver interface
226  // graphAddedNodes
227  void addNode(Graph* g, const node n);
228 
229  // graphAddedEdges
230  void addEdge(Graph* g, const edge e);
231 
232  // graphDeletedNodes
233  void delNode(Graph* g, const node n);
234 
235  // graphDeletedEdges
236  void delEdge(Graph* g, const edge e);
237 
238  // revertedEdges
239  void reverseEdge(Graph* g, const edge e);
240 
241  // oldEdgesEnds
242  void beforeSetEnds(Graph* g, const edge e);
243 
244  // newEdgesEnds
245  void afterSetEnds(Graph* g, const edge e);
246 
247  // addedSubGraphs
248  void addSubGraph(Graph* g, Graph* sg);
249 
250  // deletedSubGraphs
251  void delSubGraph(Graph* g, Graph* sg);
252 
253  // addedProperties
254  void addLocalProperty(Graph* g, const std::string& name);
255 
256  // deletedProperties
257  void delLocalProperty(Graph* g, const std::string& name);
258 
259  // beforeSetAttribute
260  void beforeSetAttribute(Graph* g, const std::string& name);
261 
262  // removeAttribute
263  void removeAttribute(Graph* g, const std::string& name);
264 
265  // old PropertyObserver Interface
266  // oldValues
267  void beforeSetNodeValue(PropertyInterface* p, const node n);
268 
269  // oldNodeDefaultValues
270  void beforeSetAllNodeValue(PropertyInterface* p);
271 
272  // oldValues
273  void beforeSetEdgeValue(PropertyInterface* p, const edge e);
274 
275  // oldEdgeDefaultValues
276  void beforeSetAllEdgeValue(PropertyInterface* p);
277 
278  // renamedProperties
279  void propertyRenamed(PropertyInterface* p);
280 
281 protected:
282  // override Observable::treatEvent
283  virtual void treatEvent(const Event& ev);
284 };
285 }
286 
287 #endif // TLPGRAPHRECORDER_H
288 
289 ///@endcond
unsigned int getId() const
Gets the unique identifier of the graph.
Definition: Graph.h:1012