Tulip  4.1.0
Better Visualization Through Research
 All Classes Files Functions Variables Enumerations Enumerator Properties Groups Pages
Graph.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 1 and Inria Bordeaux - Sud Ouest
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 
20 #ifndef Tulip_SUPERGRAPH_H
21 #define Tulip_SUPERGRAPH_H
22 
23 #include <iostream>
24 #include <string>
25 #include <vector>
26 
27 #include <climits>
28 #include <tulip/tulipconf.h>
29 #include <tulip/DataSet.h>
30 #include <tulip/Node.h>
31 #include <tulip/Edge.h>
32 #include <tulip/Observable.h>
33 
34 namespace tlp {
35 
36 class PropertyInterface;
37 class BooleanProperty;
38 class PluginProgress;
39 template<class C>struct Iterator;
40 
41 /**
42  * @enum This Enum describes the possible types of an element of the graph.
43  *
44  * It is used in functions that can return an edge or a node, to distinguish between the two cases.
45  **/
46 enum ElementType {
47  /** This element describes a node **/
48  NODE = 0,
49  /** This element describes an edge **/
50  EDGE = 1
51 };
52 
53 /**
54  * @ingroup Graph
55  * @brief Loads a graph in the tlp format from a file (extension can be .tlp or .tlp.gz).
56  * This function uses the "TLP Import" import plugin, and will fail if it is not loaded (By default this plugin is linked into the library and should be loaded).
57  *
58  * If the import fails (no such file, parse error, ...) NULL is returned.
59  *
60  * @param filename The file in tlp format to parse.
61  * @return :Graph* The imported Graph, NULL if the import failed.
62  **/
63 TLP_SCOPE Graph * loadGraph(const std::string &filename, tlp::PluginProgress* progress = NULL);
64 
65 /**
66  * @ingroup Graph
67  * @brief Saves the corresponding root graph and all its subgraphs to a file using the tlp format. Extension of the file can be either .tlp (human-readable text file) or .tlp.gz (gzipped text file).
68  *
69  * This function checks the file name for the '.gz' extension and uses a compressed output if found.
70  *
71  * This function uses the "TLP Export" export plugin, and will fail if it is not loaded (by default this plugin is linked into the library and should be loaded).
72  *
73  * @param graph the graph to save.
74  * @param filename the file to save the graph to.
75  * @return bool Whether the export was successfull or not.
76  **/
77 TLP_SCOPE bool saveGraph(Graph* graph, const std::string &filename, tlp::PluginProgress* progress = NULL);
78 
79 /**
80  * @ingroup Graph
81  * @brief Exports a graph using the specified export plugin with parameters stored in the DataSet.
82  *
83  * You determine the destination, whether by using a fstream, or by saving the contents of the stream to the destination of your choice.
84  *
85  * @param graph The graph to export.
86  * @param outputStream The stream to export to. Can be a standard ostream, an ofstream, or even a gzipped ostream.
87  * @param format The format to use to export the Graph.
88  * @param dataSet The parameters to pass to the export plugin (e.g. additional data, options for the format)
89  * @param progress A PluginProgress to report the progress of the operation, as well as final state. Defaults to NULL.
90  * @return bool Whether the export was successfull or not.
91  **/
92 TLP_SCOPE bool exportGraph(Graph *graph, std::ostream &outputStream, const std::string &format, DataSet &dataSet, PluginProgress *progress=NULL);
93 
94 /**
95  * @ingroup Graph
96  * @brief Imports a graph using the specified import plugin with the parameters stored in the DataSet.
97  *
98  * If no graph is passed, then a new graph will be created. You can pass a graph in order to import data into it.
99  * Returns the graph with imported data, or NULL if the import failed. In this case, the Pluginprogress should have an error that can be displayed.
100  *
101  * @param format The format to use to import the graph.
102  * @param dataSet The parameters to pass to the import plugin (file to read, ...)
103  * @param progress A PluginProgress to report the progress of the operation, as well as final state. Defaults to NULL.
104  * @param newGraph The graph to import the data into. This can be usefull to import data into a subgraph. Defaults to NULL.
105  * @return :Graph* The graph containing the imported data, or NULL in case of failure.
106  **/
107 TLP_SCOPE Graph* importGraph(const std::string &format, DataSet &dataSet, PluginProgress *progress=NULL,Graph *newGraph=NULL);
108 
109 /**
110  * @ingroup Graph
111  * @brief Creates a new, empty graph.
112  *
113  * This is a simple method factory to create a Graph implementation (remember, Graph is only an interface).
114  *
115  * This is the recommended way to create a new Graph.
116  *
117  * @return :Graph* A new, empty graph.
118  **/
119 TLP_SCOPE Graph* newGraph();
120 
121 /**
122  * @ingroup Graph
123  * @brief Creates and returns an empty subgraph of the given graph.
124  *
125  * @deprecated this function should not be used anymore, please use Graph::addSubGraph() instead.
126  *
127  * @param graph The graph to add an empty subgraph to.
128  * @param name The name of the new subgraph. Defaults to "unnamed".
129  * @return :Graph* The newly created subgraph.
130  **/
131 TLP_SCOPE _DEPRECATED Graph* newSubGraph(Graph *graph, std::string name = "unnamed");
132 
133 /**
134  * @ingroup Graph
135  * @brief Creates and returns a subgraph of the graph that is equal to root (a clone subgraph).
136  *
137  * @deprecated this function should not be used anymore, please use Graph::addCloneSubGraph() instead.
138  *
139  * @param graph The Graph on which to create a clone subgraph.
140  * @param name The name of the newly created subgraph. Defaults to "unnamed".
141  * @return :Graph* The newly created clone subgraph.
142  **/
143 TLP_SCOPE _DEPRECATED Graph* newCloneSubGraph(Graph *graph, std::string name = "unnamed");
144 
145 /**
146  * @ingroup Graph
147  * Appends the selected part of the graph inG (properties, nodes and edges) into the graph outG.
148  * If no selection is done (inSel=NULL), the whole inG graph is appended.
149  * The output selection is used to select the appended nodes & edges
150  * \warning The input selection is extended to all selected edge ends.
151  */
152 TLP_SCOPE void copyToGraph(Graph *outG, const Graph *inG, BooleanProperty* inSelection=NULL, BooleanProperty* outSelection=NULL );
153 
154 /**
155  * @ingroup Graph
156  * Removes the selected part of the graph ioG (properties values, nodes and edges).
157  * If no selection is done (inSel=NULL), the whole graph is reseted to default value.
158  * \warning The selection is extended to all selected edge ends.
159  */
160 TLP_SCOPE void removeFromGraph(Graph * ioG, BooleanProperty* inSelection=NULL);
161 
162 /**
163  * @ingroup Graph
164  * The class Graph is the interface of a Graph in the Tulip Library.
165  *
166  * There are a few principles to know when working with a Tulip Graph.
167  *
168  * @chapter Directed
169  * Every edge is directed in a Tulip Graph.
170  * You can choose to ignore this, but every edge has a source and destination.
171  *
172  * @chapter Inheritance
173  *
174  * Subgraphs inherit from their parent graph.
175  * This is true of nodes and edges; every node and edge in a subgraph also exists in each of its parent graphs.
176  * This is also true of properties; every property in a graph exist in all of its subgraphs, except if it has been replaced
177  * by a local property.
178  *
179  * For instance, ig you have the following graph hierarchy:
180  * root
181  * / \
182  * A B
183  *
184  * Every node in A is in root, and every node in B is in root.
185  * Nodes can be in A and root but not B; or in B and root but not A.
186  *
187  * For instance, imagine a graph. You want to compare it to its Delaunay triangulation.
188  * You need to create a subgraph that is a clone of the original (say this is A) to keep the original graph,
189  * and another copy (say this one is B) on which you will perform the delaunay triangulation.
190  *
191  * B will have none of the original edges, and A will have only the original edges.
192  *
193  * As for properties; let's imagine the same graph hierarchy.
194  * You want to compare two different layouts on the same graph.
195  * You need to create two clone subgraphs, on each you make the 'viewLayout' property local.
196  * This results in A and B having different values for the layout, but everything else in common.
197  * You then can apply two different algorithms on A and B (e.g. Bubble Tree and Tree Radial).
198  *
199  * @chapter Meta Nodes
200  * A meta node is a node representing a subgraph of the current graph.
201  *
202  * @chapter Undo Redo
203  * The Tulip Graph object supports for undo and redo of modifications.
204  *The operations affect the whole graph hierarchy, and cannot be limited to a subgraph.
205  *
206  */
207 class TLP_SCOPE Graph : public Observable {
208 
209  friend class GraphAbstract;
210  friend class GraphUpdatesRecorder;
211  friend class GraphDecorator;
212  friend class PropertyManager;
213 
214 public:
215  Graph():id(0) {}
216  virtual ~Graph() {}
217 
218  /**
219  * @brief Applies an algorithm plugin, identified by its name.
220  * Algorithm plugins are subclasses of the tlp::Algorithm interface.
221  * Parameters are transmitted to the algorithm trough the DataSet.
222  * To determine a plugin's parameters, you can either:
223  *
224  * * refer to its documentation
225  *
226  * * use buildDefaultDataSet on the plugin object if you have an instance of it
227  *
228  * * call getPluginParameters() with the name of the plugin on the PluginLister
229  *
230  *
231  * If an error occurs, a message describing the error should be stored in errorMessage.
232  *
233  * @param algorithm The algorithm to apply.
234  * @param errorMessage A string that will be modified to contain an error message should an error occur.
235  * @param dataSet The parameters to the algorithm. Defaults to NULL.
236  * @param progress A PluginProgress to report the progress of the operation, as well as final state. Defaults to NULL.
237  * @return bool Whether the algorithm was successfully applied.
238  **/
239  bool applyAlgorithm(const std::string &algorithm, std::string &errorMessage, DataSet *dataSet=NULL, PluginProgress *progress=NULL);
240 
241  //=========================================================================
242  // Graph hierarchy access and building
243  //=========================================================================
244 
245  /**
246  * @brief Removes all nodes, edges and sub-graphs from this graph.
247  *
248  * Contrarily to creating a new Graph, this keeps attributes and properties.
249  *
250  * @return void
251  **/
252  virtual void clear()=0;
253 
254  /**
255  * @brief Creates and returns a new sub-graph of this graph.
256  *
257  * If a BooleanProperty is provided, all the nodes and edges for which it is true will be added to the subgraph.
258  * If none is provided, then the subgraph will be empty.
259  *
260  * The id parameter should only be provided if you know exactly what you are doing; as Tulip will manage the subgraphs IDs when left to 0.
261  * It is only used by the Graph loading as subgraphs ids are preserved when saving/loading a Graph.
262  *
263  * @param selection The elements to add to the new subgraph. Defaults to 0.
264  * @param id The ID you wish to assign to the Graph. It is strongly advised to leave this as default and let Tulip manage subgraph IDs. Defaults to 0.
265  * @return :Graph* The newly created subgraph.
266  **/
267  virtual Graph *addSubGraph(BooleanProperty *selection=NULL,
268  unsigned int id = 0)=0;
269 
270  /**
271  * @brief Creates and returns a new named sub-graph of this graph.
272  *
273  * @param name The name of the newly created subgraph. Defaults to "unnamed".
274  * @return :Graph* The newly created subgraph.
275  **/
276  Graph *addSubGraph(std::string name);
277 
278  /**
279  * @brief Creates and returns a subgraph of this graph that contains all its elements.
280  *
281  * @param name The name of the newly created subgraph. Defaults to "unnamed".
282  * @return :Graph* The newly created clone subgraph.
283  **/
284  virtual Graph* addCloneSubGraph(std::string name = "unnamed");
285 
286  /**
287  * @brief Creates and returns a new sub-graph of the graph induced by a set of nodes.
288  * Every node contained in the given set of nodes is added to the subgraph.
289  * Every edge connecting any two nodes in the set of given nodes is also added.
290  * @param nodeSet The nodes to add to the subgraph. All the edges between these nodes are added too.
291  * @param parentSubGraph If provided, is used as parent graph for the newly created subgraph instead of the Graph this method is called on.
292  * @return The newly created subgraph.
293  */
294  Graph *inducedSubGraph(const std::set<node>& nodeSet,
295  Graph* parentSubGraph = NULL);
296 
297  /**
298  * @brief Deletes a sub-graph of this graph.
299  * All subgraphs of the removed graph are re-parented to this graph.
300  * For instance, with a graph hierarchy as follows :
301  * root
302  * / \
303  * A B
304  * /|\
305  * C D E
306  *
307  * @code root->delSubGraph(B);
308  * would result in the following hierarchy:
309  * root
310  * / | \\
311  * A C D E
312  *
313  * @param graph The subgraph to delete.
314  *
315  * @see delAllSubGraphs() if you want to remove all descendants of a graph.
316  */
317  virtual void delSubGraph(Graph *graph)=0;
318 
319  /**
320  * @brief Deletes a sub-graph of this graph and all of its sub-graphs.
321  ** For instance, with a graph hierarchy as follows :
322  * root
323  * / \
324  * A B
325  * /|\
326  * C D E
327  *
328  * @codeline root->delSubGraph(B); @endcode
329  * would result in the following hierarchy:
330  * root
331  * |
332  * A
333  *
334  * @param graph The subgraph to delete.
335  * @see delSubGraph() if you want to keep the descendants of the subgraph to remove.
336  */
337  virtual void delAllSubGraphs(Graph *graph)=0;
338 
339  /**
340  * @brief Returns the parent of the graph. If called on the root graph, it returns itself.
341  * @return The parent of this graph (or itself if it is the root graph).
342  * @see getRoot() to directly retrieve the root graph.
343  */
344  virtual Graph* getSuperGraph()const =0;
345 
346  /**
347  * @brief Gets the root graph of the graph hierarchy.
348  * @return The root graph of the graph hierarchy.
349  */
350  virtual Graph* getRoot() const =0;
351 
352  /**
353  * @cond DOXYGEN_HIDDEN
354  * @brief Sets the parent of a graph.
355  * @warning ONLY USE IF YOU KNOW EXACTLY WHAT YOU ARE DOING.
356  * @endcond
357  */
358  virtual void setSuperGraph(Graph *)=0;
359 
360  /**
361  * @brief Gets an iterator on all the sub-graphs of the graph.
362  * For instance, in the followong graph hierarchy:
363  ** root
364  * / \
365  * A B
366  * /|\
367  * C D E
368  *
369  * @codeline root->getSubGraphs(); @endcode
370  * Will return an iterator over A and B, but not C, D and E.
371  * @return An iterator over this graph's direct subgraphs.
372  */
373  virtual Iterator<Graph *> * getSubGraphs() const=0;
374 
375  /**
376  * @brief This method returns the nth subgraph.
377  * Since subgraphs order cannot be ensured in every implementation, this method should be equivalent to:
378  * @code
379  int i=0;
380  Iterator<Graph *> *it = g->getSubGraphs();
381  while (it->hasNext()) {
382  Graph *result = it->next();
383  if (i++ == n) {
384  delete it;
385  return result;
386  }
387  }
388  delete it;
389  return NULL;
390  * @endcode
391  * @param n the index of the subgraph to retrieve.
392  * @return The n-th subgraph.
393  */
394  virtual Graph *getNthSubGraph(unsigned int n) const;
395 
396  /**
397  * @brief Return the number of direct sub-graphs.
398  * For instance, in the followong graph hierarchy:
399  * root
400  * / \
401  * A B
402  * /|\
403  * C D E
404  *
405  * @codeline root->numberOfSubGraphs(); @endcode
406  * Will return 2.
407  * @return The number of direct subgraphs.
408  * @see numberOfDescendantGraphs() to count in the whole hierarchy.
409  */
410  virtual unsigned int numberOfSubGraphs() const=0;
411 
412  /**
413  * @brief Return the number of descendant sub-graphs.
414  * For instance, in the followong graph hierarchy:
415  * root
416  * / \
417  * A B
418  * /|\
419  * C D E
420  *
421  * @codeline root->numberOfSubGraphs(); @endcode
422  * Will return 5.
423  * @return The number of descendants subgraphs.
424  * @see numberOfSubGraphs() to count only direct subgraphs.
425  */
426  virtual unsigned int numberOfDescendantGraphs() const=0;
427 
428  /**
429  * @brief Indicates if the graph argument is a direct sub-graph.
430  * @param subGraph The graph to check is a subgraph of this graph.
431  * @return Whether subGraph is a direct subgraph of this graph.
432  * @see isDescendantGraph() to search in the whole hierarchy.
433  */
434  virtual bool isSubGraph(const Graph* subGraph) const=0;
435 
436  /**
437  * @brief Indicates if the graph argument is a descendant of this graph.
438  * @param subGraph The graph to check is a descendant of this graph.
439  * @return Whether subGraph is a descendant of this graph.
440  * @see isSubGraph to search only in direct subgraphs.
441  */
442  virtual bool isDescendantGraph(const Graph* subGraph) const=0;
443 
444  /**
445  * @brief Returns a pointer on the sub-graph with the corresponding id
446  * or NULL if there is no sub-graph with that id.
447  * @param id The id of the subgraph to retrieve.
448  * @return A subgraph of the given id, or null if no such subgraph exists on this graph.
449  * @see getDescendantGraph(unsigned int) to search in the whole hierarchy.
450  */
451  virtual Graph* getSubGraph(unsigned int id) const=0;
452 
453  /**
454  * @brief Returns a pointer on the sub-graph with the corresponding name
455  * or NULL if there is no sub-graph with that name.
456  * @param name The name of the subgraph to retrieve.
457  * @return A Graph named name, or NULL if no such subgraph exists on this graph.
458  * @see getDescendantGraph(const std::string &) to search in the whole hierarchy.
459  */
460  virtual Graph* getSubGraph(const std::string &name) const=0;
461 
462  /**
463  * @brief Returns a pointer on the descendant with the corresponding id
464  * or NULL if there is no descendant with that id.
465  * @param id The id of the descendant graph to retrieve.
466  * @return A graph with the given id, or NULL if no such graph exists in this graph's descendants.
467  * @see getSubGraph(unsigned int) to search only in direct subgraphs.
468  */
469  virtual Graph* getDescendantGraph(unsigned int id) const=0;
470 
471  /**
472  * @brief Returns a pointer on the first descendant graph with the corresponding name
473  * or NULL if there is no descendant graph with that name.
474  * @param name The name of the descendant graph to look for.
475  * @return A graph named name, or NULL if there is no such graph in this graph's descendants.
476  * @see getSubGraph(const std::string &) to search only in direct subgraphs.
477  */
478  virtual Graph* getDescendantGraph(const std::string &name) const=0;
479  //==============================================================================
480  // Modification of the graph structure
481  //==============================================================================
482  /**
483  * @brief Adds a new node in the graph and returns it. This node is also added in all
484  * the ancestor graphs.
485  * @return The newly added node.
486  * @see addNodes() if you want to add more than one node.
487  */
488  virtual node addNode()=0;
489 
490  /**
491  * @brief Adds new nodes in the graph and returns them in the addedNodes vector.
492  * The new nodes are also added in all the ancestor graphs.
493  *
494  * @param nbNodes The number of nodes to add.
495  * @param addedNodes The newly added nodes. This vector is cleared before being filled.
496  * @see addNode() to add a single node.
497  */
498  virtual void addNodes(unsigned int nbNodes, std::vector<node>& addedNodes)=0;
499 
500  /**
501  * @brief Adds an existing node in the graph. This node is also added in all the ancestor graphs.
502  * This node must exists in the graph hierarchy (which means it must exist in the root graph).
503  * You cannot add a node to the root graph this way (as it must already be an element of the root graph).
504  * @warning Using this method on the root graph will display a warning on the console.
505  *
506  * @param n The node to add to a subgraph. This node must exist in the root graph.
507  * @see addNode() to add a new node to a graph.
508  */
509  virtual void addNode(const node n)=0;
510 
511  /**
512  * @brief Adds existing nodes in the graph. The nodes are also added in all the ancestor graphs.
513  * as with addNode(const tlp::node), the nodes must exist in the graph hierarchy and thus exist in the root graph,
514  * and node cannot be added this way to the root graph.
515 
516  * @warning Using this method on the root graph will display a warning on the console.
517  * @warning The graph does not take ownership of the Iterator.
518  *
519  * @param nodes An iterator over nodes to add to this subgraph. The graph does not takes ownership of this iterator.
520  */
521  virtual void addNodes(Iterator<node>* nodes)=0;
522 
523  /**
524  * @brief Deletes a node in the graph.
525  * This node is also removed in the sub-graphs hierarchy of the current graph.
526  * @param n The node to delete.
527  * @param deleteInAllGraphs Whether to delete in all its parent graphs or only in this graph. By default only removes in the current graph.
528  * @see delNodes() to remove multiple nodes.
529  */
530  virtual void delNode(const node n, bool deleteInAllGraphs = false)=0;
531 
532  /**
533  * @brief Deletes nodes in the graph.
534  * Thess nodes are also removed in the sub-graphs hierarchy of the current graph.
535  * @warning the graph does not take ownership of the Iterator.
536  * @param it The nodes to delete.
537  * @param deleteInAllGraphs Whether to delete in all its parent graphs or only in this graph. By default only removes in the current graph.
538  * @see delNode() to remove a single node.
539  */
540  virtual void delNodes(Iterator<node>* it, bool deleteInAllGraphs = false)=0;
541 
542  /**
543  * @brief Adds a new edge in the graph
544  * This edge is also added in all the super-graph of the graph.
545  * @param source The source of the edge.
546  * @param target The target of the edge.
547  * @return The newly added edge.
548  * @see addEdges() to add multiple edges at once.
549  */
550  virtual edge addEdge(const node source, const node target)=0;
551 
552  /**
553  * @brief Adds new edges in the graph and returns them the addedEdges vector.
554  * The new edges are also added in all the graph ancestors.
555  *
556  * @warning If the edges vector contains a node that does not belong to this graph,
557  * undefined behavior will ensue.
558  * @param edges A vector describing between which nodes to add edges.
559  * The first element of the pair is the source, the second is the destination.
560  * @param addedEdges The newly added edges. This vector is cleared before being filled.
561  *
562  */
563  virtual void addEdges(const std::vector<std::pair<node, node> >& edges,
564  std::vector<edge>& addedEdges)=0;
565 
566  /**
567  * @brief Adds an existing edge in the graph. This edge is also added in all
568  * the ancestor graphs.
569  * The edge must be an element of the graph hierarchy, thus it must be
570  * an element of the root graph.
571  * @warning Using this method on the root graph will display a warning on the console.
572  * @param e The edge to add to this subgraph.
573  * @see addEgdes() to add more than one edge at once.
574  * @see addNode() to add nodes.
575  */
576  virtual void addEdge(const edge e)=0;
577 
578  /**
579  * @brief Adds existing edges in the graph. The edges are also added in all
580  * the ancestor graphs.
581  * The added edges must be elements of the graph hierarchy,
582  * thus they must be elements of the root graph.
583  * @warning Using this method on the root graph will display a warning on the console.
584  * @warning The graph does not take ownership of the iterator.
585  * @param edges The edges to add on this subgraph.
586  */
587  virtual void addEdges(Iterator<edge>* edges)=0;
588 
589  /**
590  * @brief Deletes an edge in the graph. The edge is also removed in
591  * the sub-graphs hierarchy.
592  * The ordering of remaining edges is preserved.
593  * @param e The edge to delete.
594  * @param deleteInAllGraphs Whether to delete in all its parent graphs or only in this graph. By default only removes in the current graph.
595  */
596  virtual void delEdge(const edge e, bool deleteInAllGraphs = false)=0;
597 
598  /**
599  * @brief Deletes edges in the graph. These edges are also removed in the sub-graphs hierarchy.
600  * The ordering of remaining edges is preserved.
601  * @warning The graph does not take ownership of the Iterator.
602  * @param itE
603  * @param deleteInAllGraphs Whether to delete in all its parent graphs or only in this graph. By default only removes in the current graph.
604  */
605  virtual void delEdges(Iterator<edge>* itE, bool deleteInAllGraphs = false)=0;
606 
607  /**
608  * @brief Sets the order of the edges around a node.
609  * This operation ensures that adjacent edges of a node will
610  * be ordered as they are in the vector of edges given in parameter.
611  *
612  * This can be useful if you want to make sure you retrieve the edges in a specific order when iterating upon them.
613  * @param n The node whose edges to order.
614  * @param edges The edges, in the order you want them.
615  */
616  virtual void setEdgeOrder(const node n,const std::vector<edge> &edges)=0;
617 
618  /**
619  * @brief Swaps two edges in the adjacency list of a node.
620  * @param n The node on whoch to swap the edges order.
621  * @param e1 The first edge, that will take the second edge's position.
622  * @param e2 The second edge, that will take the first edge's position.
623  */
624  virtual void swapEdgeOrder(const node n,const edge e1, const edge e2)=0;
625 
626  /**
627  * @brief Sets the source of an edge to be the given node.
628  * @param e The edge to change the source of.
629  * @param source The new source of the edge.
630  */
631  virtual void setSource(const edge e, const node source) = 0;
632 
633  /**
634  * @brief Sets the target of an edge to be the given node.
635  * @param e The edge to change the target of.
636  * @param target The new target of the edge.
637  */
638  virtual void setTarget(const edge e, const node target) = 0;
639 
640  /**
641  * @brief Sets both the source and the target of an edge.
642  * @param e The edge to set the source and target of.
643  * @param source The new source of the edge.
644  * @param target The new target of the edge.
645  */
646  virtual void setEnds(const edge e, const node source, const node target) = 0;
647 
648  /**
649  * @brief Reverses the direction of an edge, the source becomes the target and the target
650  * becomes the source.
651  * @warning The ordering is global to the entire graph hierarchy. Thus, by changing
652  * the ordering of a graph you change the ordering of the hierarchy.
653  * @param e The edge top reverse.
654  */
655  virtual void reverse(const edge e)=0;
656  // Attempts to reserve enough space to store nodes.
657  // Only defined on root graph.
658  virtual void reserveNodes(unsigned int nbNodes) = 0;
659  // Attempts to reserve enough space to store edges.
660  // Only defined on root graph.
661  virtual void reserveEdges(unsigned int nbEdges) = 0;
662  //================================================================================
663  //Iterators on the graph structure.
664  //================================================================================
665  /**
666  * @brief Finds the first node whose input degree equals 0.
667  *
668  * @return tlp::node The first encountered node with input degree of 0, or an invalid node if none was found.
669  **/
670  virtual tlp::node getSource() const;
671 
672  /**
673  * @brief Gets a node on the graph.
674  * @return Any node of the graph.
675  */
676  virtual node getOneNode() const =0;
677 
678  /**
679  * @brief Gets an iterator over this graph's nodes.
680  * @return An iterator over all the nodes of this graph.
681  * @see getInNodes()
682  * @see getOutNodes()
683  * @see getInOutNodes()
684  * @see getEdges()
685  */
686  virtual Iterator<node>* getNodes() const =0;
687 
688  /**
689  * @brief Gets the i-th node in the input nodes of a given node.
690  * An input node 'in' of a node 'N' is the source of an edge going from
691  * 'in' to 'N'. e.g.
692  * @code
693  * node in = graph->addNode();
694  * node N = graph->addNode();
695  * graph->addEdge(in, N);
696  * //in == graph->getInNode(N, 0);
697  * @endcode
698  *
699  * If you have 5 input nodes on a node N, then
700  * @codeline graph->getInNode(2); @endcode
701  * will return the second of those nodes.
702  * It will ignore the output nodes of this node.
703  * @param n The node to get an input node of.
704  * @param i The index of the input node to get.
705  * @return The i-th input node of the given node.
706  * @see getInNodes()
707  * @see getInEdges()
708  */
709  virtual node getInNode(const node n,unsigned int i)const =0;
710 
711  /**
712  * @brief Gets an iterator over the input nodes of a node.
713  * @param n The node to get the input nodes of.
714  * @return An iterator over the input nodes of a node.
715  * @see getInNode()
716  * @see getInOutNodes()
717  * @see getInEdges()
718  */
719  virtual Iterator<node>* getInNodes(const node n) const =0;
720 
721  /**
722  * @brief Gets the i-th node in the output nodes of a given node.
723  * An output node 'out' of a node 'N' is the target of an edge going from
724  * 'N' to 'out'. e.g.
725  * @code
726  * node N = graph->addNode();
727  * node out = graph->addNode();
728  * graph->addEdge(N, out);
729  * //out == graph->getOutNode(N, 0);
730  * @endcode
731  *
732  * If you have 5 output nodes on a node N, then
733  * @codeline graph->getOutNode(2); @endcode
734  * will return the second of those nodes.
735  * It will ignore the input nodes of this node.
736  * @param n The node to get an output node of.
737  * @param i The index of the output node to get.
738  * @return The i-th output node of the given node.
739  * @see getOutNodes()
740  * @see getOutEdges()
741  */
742  virtual node getOutNode(const node n,unsigned int i) const =0;
743 
744  /**
745  * @brief Gets an iterator over the output nodes of a node.
746  * @param n The node to get the output nodes of.
747  * @return An iterator over the output nodes of a node.
748  * @see getOutNode()
749  * @see getInOutNodes()
750  * @see getOutEdges()
751  */
752  virtual Iterator<node>* getOutNodes(const node n) const =0;
753 
754  /**
755  * @brief Gets an iterator over the neighbors of a given node.
756  * @param n The node to retrieve the neighbors of.
757  * @return An iterator over the node's neighbors.
758  */
759  virtual Iterator<node>* getInOutNodes(const node n) const =0;
760 
761  /**
762  * @brief Gets the underlying graph of a meta node.
763  * @param metaNode The metanode.
764  * @return The Graph pointed to by the metanode.
765  * @see getEdgeMetaInfo()
766  */
767  virtual Graph* getNodeMetaInfo(const node metaNode) const = 0;
768 
769  /**
770  * @brief Get an iterator over all the graph's edges.
771  * @return An iterator over all the graph's edges.
772  * @see getInEdges()
773  * @see getOutEdges()
774  * @see getInOutEdges()
775  */
776  virtual Iterator<edge>* getEdges() const =0;
777 
778  /**
779  * @brief Gets an edge of the graph.
780  * @return Any one of the graph's edges.
781  */
782  virtual edge getOneEdge() const =0;
783 
784  /**
785  * @brief Gets an iterator over the output edges of a node.
786  * @param n The node to get the output edges from.
787  * @return An iterator over the node's output edges.
788  * @see getEdges()
789  * @see getOutEdges()
790  * @see getInOutEdges()
791  */
792  virtual Iterator<edge>* getOutEdges(const node n) const =0;
793 
794  /**
795  * @brief Gets an iterator over the edges of a node.
796  * @param n The node to get the edges from.
797  * @return An iterator over the node's edges.
798  * @see getEdges()
799  * @see getOutEdges()
800  * @see getInEdges()
801  */
802  virtual Iterator<edge>* getInOutEdges(const node n) const =0;
803 
804  /**
805  * @brief Gets an iterator over the input edges of a node.
806  * @param n The node to get the input edges from.
807  * @return An iterator over the node's input edges.
808  * @see getEdges()
809  * @see getOutEdges()
810  * @see getInOutEdges()
811  */
812  virtual Iterator<edge>* getInEdges(const node n) const =0;
813 
814  /**
815  * @brief Gets an iterator over the edges composing a meta edge.
816  * @param metaEdge The metaEdge to get the real edges of.
817  * @return An Iterator over the edges composing the metaEdge.
818  * @see getNodeMetaInfo()
819  */
820  virtual Iterator<edge>* getEdgeMetaInfo(const edge metaEdge) const =0;
821  //================================================================================
822  // Graph, nodes and edges informations about the graph stucture
823  //================================================================================
824  /**
825  * @brief Gets the unique identifier of the graph.
826  * @return The unique identifier of this graph.
827  */
828  unsigned int getId() const {
829  return id;
830  }
831 
832  /**
833  * @brief Gets the number of nodes in this graph.
834  * @return The number of nodes in this graph.
835  * @see numberOfEdges()
836  */
837  virtual unsigned int numberOfNodes()const =0;
838 
839  /**
840  * @brief Gets the number of edges in this graph.
841  * @return The number of edges in this graph.
842  * @see numberOfNodes()
843  */
844  virtual unsigned int numberOfEdges()const =0;
845 
846  /**
847  * @param n The node to get the degree of.
848  * @return The degree of the given node.
849  */
850  virtual unsigned int deg(const node n)const =0;
851 
852  /**
853  * @brief Get the input degree of a node.
854  * @param n The node to get the input degree of.
855  * @return The input degree of the given node.
856  */
857  virtual unsigned int indeg(const node n)const =0;
858 
859  /**
860  * @brief Get the output degree of a node.
861  * @param n The node to get the output degree of.
862  * @return The output degree of the given node.
863  */
864  virtual unsigned int outdeg(const node n)const =0;
865 
866  /**
867  * @brief Gets the source of an edge.
868  * @param e The edge to get the source of.
869  * @return The source of the given edge.
870  */
871  virtual node source(const edge e)const =0;
872 
873  /**
874  * @brief Gets the target of an edge.
875  * @param e The edge to get the target of.
876  * @return The target of the given edge.
877  */
878  virtual node target(const edge e)const =0;
879 
880  /**
881  * @brief Gets the source and the target of an edge.
882  * @param e The edge to get the ends of.
883  * @return A pair whose first element is the source, and second is the target.
884  */
885  virtual const std::pair<node, node>& ends(const edge e)const=0;
886 
887  /**
888  * @brief Gets the opposite node of n through e.
889  * @param e The edge linking the two nodes.
890  * @param n The node at one end of e.
891  * @return The node at the other end of e.
892  */
893  virtual node opposite(const edge e, const node n)const =0;
894 
895  /**
896  * @brief Checks if an element belongs to this graph.
897  * @param n The node to check if it is an element of the graph.
898  * @return Whether or not the element belongs to the graph.
899  */
900  virtual bool isElement(const node n) const =0;
901 
902  /**
903  * @brief Checks is a node is a meta node.
904  * @param n The node to check if it is a meta node.
905  * @return Whether or not the node is a meta node.
906  */
907  virtual bool isMetaNode(const node n) const =0;
908 
909  /**
910  * @brief Checks if an element belongs to this graph.
911  * @param e The edge to check if it is an element of the graph.
912  * @return Whether or not the element belongs to the graph.
913  */
914  virtual bool isElement(const edge e) const =0;
915 
916  /**
917  * @brief Checks is an edge is a meta edge.
918  * @param e The edge to check if it is a meta edge.
919  * @return Whether or not the edge is a meta edge.
920  */
921  virtual bool isMetaEdge(const edge e) const =0;
922 
923  /**
924  * Returns the edge if it exists an edge between two nodes.
925  * The 'directed' flag indicates if the direction of the edge
926  * (from source to target) must be taken in to account.
927  * If no edge is found, returns an invalid edge.
928  *
929  * @brief If an edge exists between the two given nodes, return it.
930  * If specified, include and edge that goes from target to source.
931  * @warning this function always returns an edge, you need to check if this edge is valid with
932  * edge::isValid().
933  * @param source The source of the hypothetical edge.
934  * @param target The target of the hypothetical edge.
935  * @param directed Whether to include edges going from target to source.
936  * @return An edge that is only valid if it exists.
937  */
938  virtual edge existEdge(const node source, const node target,
939  bool directed = true) const =0;
940  //================================================================================
941  // Access to the graph attributes and to the node/edge property.
942  //================================================================================
943  /**
944  * @brief Sets the name of the graph.
945  * The name does not have to be unique, it is used for convenience.
946  * @param name The new name of the graph.
947  */
948  virtual void setName(const std::string &name) = 0;
949 
950  /**
951  * @brief Retrieves the name of the graph.
952  * @return The name of the graph.
953  */
954  virtual std::string getName() const = 0;
955 
956  /**
957  * @brief Gets the attributes of the graph.
958  *
959  * The attributes contains the name and any user-defined value.
960  * @return The attributes of the graph.
961  */
962  const DataSet & getAttributes() const {
963  return (const_cast<Graph *>(this))->getNonConstAttributes();
964  }
965 
966  /**
967  * @brief Gets an attribute on the graph.
968  * @param name The name of the attribute to set.
969  * @param value The value to set.
970  * @return Whether the setting of the attribute was sucessful.
971  */
972  template<typename ATTRIBUTETYPE>
973  bool getAttribute(const std::string &name, ATTRIBUTETYPE& value) const;
974 
975  /**
976  * @brief Gets a copy of the attribute.
977  * @param name The name of the attribute to retrieve.
978  * @return A copy of the attribute to retrieve.
979  */
980  DataType* getAttribute(const std::string& name) const;
981 
982  /**
983  * @brief Sets an attribute on the graph.
984  * @param name The name of the attribute to set.
985  * @param value The value to set on this attribute.
986  */
987  template<typename ATTRIBUTETYPE>
988  void setAttribute(const std::string &name,const ATTRIBUTETYPE &value);
989 
990  /**
991  * @brief Sets an attribute on the graph.
992  * @param name The name of the attribute to set.
993  * @param value The value to set.
994  */
995  void setAttribute(const std::string &name, const DataType* value);
996 
997  /**
998  * @brief Removes an attribute on the graph.
999  * @param name The name of the attribute to remove.
1000  */
1001  void removeAttribute(const std::string &name) {
1002  notifyRemoveAttribute(name);
1003  getNonConstAttributes().remove(name);
1004  }
1005 
1006  /**
1007  * @brief Checks if an attribute exists.
1008  * @param name The name of the attribute to check for.
1009  * @return Whether the attribute exists.
1010  */
1011  bool attributeExist(const std::string &name) {
1012  return getAttributes().exist(name);
1013  }
1014 
1015  /**
1016  * @brief Adds a property to the graph.
1017  * The graph takes ownership of the property. If you want to delete it, use
1018  * Graph::delLocalProperty().
1019  * @param name The unique identifier of the property.
1020  * @param prop The property to add.
1021  */
1022  virtual void addLocalProperty(const std::string &name, PropertyInterface *prop)=0;
1023 
1024  /**
1025  * @brief Gets an existing property.
1026  * In DEBUG mode an assertion checks the existence of the property.
1027  *
1028  * The graph keeps ownership of the property, if you wish to remove it from the graph use
1029  * Graph::delLocalProperty().
1030  *
1031  * @param name The unique identifier of the property.
1032  * @return An existing property, or NULL if no property with the given name exists.
1033  */
1034  virtual PropertyInterface* getProperty(const std::string& name) const = 0;
1035 
1036  /**
1037  * @brief Gets a property on this graph.
1038  * The name of a property indentifies it uniquely.
1039  * Either there already exists a property with the given name, in which case it is returned.
1040  * Either no such porperty exists and it is created.
1041  *
1042  * The graph keeps ownership of the property, if you wish to remove it fgrom the graph use
1043  * Graph::delLocalProperty().
1044  * @warning using the wrong template parameter will cause a segmentation fault.
1045  * @param The unique identifier of the property.
1046  * @return The property of given name.
1047  */
1048  template<typename PropertyType>
1049  PropertyType* getLocalProperty(const std::string &name);
1050 
1051  /**
1052  * @brief Gets a property on this graph or one of its ancestors.
1053  * If the property already exists on the graph or in one of its ancestors, it is returned.
1054  * Otherwise a new property is created on this graph.
1055  *
1056  * The graph keeps ownership of the property, if you wish to remove it from the graph use
1057  * Graph::delLocalProperty().
1058  *
1059  * @warning using the wrong propertyType will result in a segmentation fault. Using an invalid property type will always return NULL.
1060  * @param name The unique identifier of the property.
1061  * @return An existing property, or a new one if none exists with the given name.
1062  */
1063  template<typename PropertyType>
1064  PropertyType* getProperty(const std::string &name);
1065 
1066  /**
1067  * @brief Gets a property on this graph, and this graph only.
1068  * This forwards the call to the template version of getLocalProperty(), with the correct template parameter deduced from the propertyType parameter.
1069  *
1070  * The graph keeps ownership of the property, if you wish to remove it from the graph use
1071  * Graph::delLocalProperty().
1072  *
1073  * @warning using the wrong propertyType will result in a segmentation fault. Using an invalid property type will always return NULL.
1074  * @param propertyName The unique identifier of the property.
1075  * @param propertyType A string describing the type of the property.
1076  * @return The property of given name.
1077  * @see getLocalProperty().
1078  */
1079  PropertyInterface *getLocalProperty(const std::string& propertyName, const std::string& propertyType);
1080 
1081  /**
1082  * @brief Gets a property on this graph or one of its ancestors.
1083  * This forwards the call to the template version of getProperty(), with the correct template parameter deduced from the propertyType parameter.
1084  *
1085  * The graph keeps ownership of the property, if you wish to remove it from the graph use
1086  * Graph::delLocalProperty().
1087  *
1088  * @warning using the wrong propertyType will result in a segmentation fault. Using an invalid property type will always return NULL.
1089  * @param propertyName The unique identifier of the property.
1090  * @param propertyType A string describing the type of the property.
1091  * @return The property of given name.
1092  * @see getProperty().
1093  */
1094  PropertyInterface *getProperty(const std::string& propertyName, const std::string& propertyType);
1095 
1096  /**
1097  * @brief Checks if a property exists in this graph or one of its ancestors.
1098  * @param The unique identifier of the property.
1099  * @return Whether a property with the given name exists.
1100  */
1101  virtual bool existProperty(const std::string& name) const = 0;
1102 
1103  /**
1104  * @brief Checks if a property exists in this graph.
1105  * @param The unique identifier of the property.
1106  * @return Whether a property with the given name exists.
1107  */
1108  virtual bool existLocalProperty(const std::string& name) const = 0;
1109 
1110  /**
1111  * @brief Removes and deletes a property from this graph.
1112  * The property is removed from the graph's property pool, meaning its name can now be used by another property.
1113  * The object is deleted and the memory freed.
1114  * @param name The unique identifier of the property.
1115  */
1116  virtual void delLocalProperty(const std::string& name)=0;
1117 
1118  /**
1119  * @brief Gets an iterator over the names of the local properties of this graph.
1120  * @return An iterator over this graph's properties names.
1121  */
1122  virtual Iterator<std::string>* getLocalProperties() const=0;
1123 
1124  /**
1125  * @brief Gets an iterator over the local properties of this graph.
1126  * @return An iterator over this graph's properties.
1127  */
1128  virtual Iterator<PropertyInterface*>* getLocalObjectProperties() const=0;
1129 
1130  /**
1131  * @brief Gets an iterator over the names of the properties inherited from this graph's ancestors,
1132  * excluding this graph's local properties.
1133  * @return An iterator over the names of the properties this graph inherited.
1134  */
1135  virtual Iterator<std::string>* getInheritedProperties() const=0;
1136 
1137  /**
1138  * @brief Gets an iterator over the properties inherited from this graph's ancestors,
1139  * excluding this graph's local properties.
1140  * @return An iterator over the properties this graph inherited.
1141  */
1142  virtual Iterator<PropertyInterface*>* getInheritedObjectProperties() const=0;
1143 
1144  /**
1145  * @brief Gets an iterator over the names of all the properties attached to this graph,
1146  * whether they are local or inherited.
1147  * @return An iterator over the names of all the properties attached to this graph.
1148  */
1149  virtual Iterator<std::string>* getProperties() const=0;
1150 
1151  /**
1152  * @brief Gets an iterator over the properties attached to this graph,
1153  * whether they are local or inherited.
1154  * @return An iterator over all of the properties attached to this graph.
1155  */
1156  virtual Iterator<PropertyInterface*>* getObjectProperties() const=0;
1157 
1158  /**
1159  * @brief Runs a plugin on the graph, whose result is a property.
1160  *
1161  * @param algorithm The name of the plugin to run.
1162  * @param result The property in which to put the results. All previous values will be erased.
1163  * @param errorMessage Stores the error message if the plugin fails.
1164  * @param progress A means of feedback during the plugin execution. Some plugins support being stopped or cancelled through this.
1165  * @param parameters The parameters of the algorithm. Some algorithms use this DataSet to output some additional informations.
1166  * @return Whether the plugin executed successfully or not. If not, check the error message.
1167  *
1168  * @see PluginLister::getPluginParameters() to retrieve the list of default parameters for the pligin.
1169  */
1170  bool applyPropertyAlgorithm(const std::string &algorithm,
1171  PropertyInterface* result,
1172  std::string &errorMessage,
1173  PluginProgress *progress=NULL,
1174  DataSet *parameters=NULL);
1175  /**
1176  * @cond DOXYGEN_HIDDEN
1177  *
1178  * @deprecated Use applyPropertyAlgorithm() instead.
1179  *
1180  * @endcond
1181  */
1182  template<typename PropertyType>
1183  _DEPRECATED bool computeProperty(const std::string &algorithm,
1184  PropertyType* result, std::string &msg,
1185  PluginProgress *progress=NULL, DataSet *data=NULL);
1186 
1187  // observation mechanism
1188  void _DEPRECATED addGraphObserver(Observable *) const;
1189  void _DEPRECATED removeGraphObserver(Observable *) const;
1190 
1191  // updates management
1192  /**
1193  * @brief Saves the current state of the whole graph hierarchy and allows to revert to this state later on, using pop().
1194  * All modifications except those altering the ordering of the edges will be undone.
1195  *
1196  * This allows to undo/redo modifications on a graph.
1197  * This is mostly useful from a user interface point of view, but some algorithms use this mechanism to clean up before finishing.
1198  * For instance:
1199  * @code
1200  * Graph* graph = tlp::newGraph();
1201  * DoubleProperty* prop = graph->getProperty<DoubleProperty>("metric");
1202  * string errorMessage;
1203  *
1204  * //our super metric stuff we want to kee
1205  * DoubleProperty* superProperty = graph->getProperty<DoubleProperty>("superStuff");
1206  * vector<PropertyInterface*> propertiesToKeep;
1207  * propertiesToKeep.push_back(superProperty);
1208  *
1209  *
1210  * //apply some metric
1211  * graph->applyPropertyAlgorithm("Degree", prop, errorMessage);
1212  *
1213  * // save this state to be able to revert to it later
1214  * //however we do not want to allow to unpop(), which would go forward again to the state where prop contains 'Depth'.
1215  * //this saves some memory.
1216  * //Also we always want to keep the value of our super property, so we pass it in the collection of properties to leave unaffected by the pop().
1217  * graph->push(false, propertiesToKeep);
1218  *
1219  * //compute the quality of this metric, or whatever makes sense
1220  * int degreeQuality = prop->getMax();
1221  *
1222  * //compute another metric
1223  * graph->applyPropertyAlgorithm("Depth", prop, errorMessage);
1224  *
1225  * //compute our secret metric, that depends on depth
1226  * graph->applyPropertyAlgorithm("MySuperSecretAlgorithm", superProperty, errorMessage);
1227  *
1228  * //compute its quality
1229  * int depthQuality = prop->getMax();
1230  *
1231  * //if the degree was better, revert back to the state where its contents were in prop.
1232  * if(degreeQuality > depthQuality) {
1233  * //this does not affect superProperty, as we told the system not to consider it when recording modifications to potentially revert.
1234  * graph->pop();
1235  * }
1236  *
1237  * //do some stuff using our high quality metric
1238  * ColorProperty* color = graph->getProperty("viewColor");
1239  * graph->applyPropertyAlgorithm("Color Mapping", color, errorMessage);
1240  *
1241  * @endcode
1242  *
1243  * @param unpopAllowed Whether or not to allow to re-do the modifications once they are undone.
1244  * @param propertiesToPreserveOnPop A collection of properties whose state to preserve when using pop().
1245  * @see pop()
1246  * @see unpop()
1247  * @see canPop()
1248  * @see canUnPop()
1249  * @see canPopThenUnPop()
1250  */
1251  virtual void push(bool unpopAllowed = true,
1252  std::vector<PropertyInterface*>* propertiesToPreserveOnPop= NULL)=0;
1253 
1254  /**
1255  * @brief Undoes modifications and reverts the whole graph hierarchy back to a previous state.
1256  *
1257  * @param unpopAllowed Whether or not it is possible to redo what will be undoe by this call.
1258  */
1259  virtual void pop(bool unpopAllowed = true)=0;
1260 
1261  /**
1262  * @brief Re-perform actions that were undone using pop().
1263  *
1264  * For instance:
1265  * @code
1266  * DoubleProperty* prop = graph->getProperty<DoubleProperty>("metric");
1267  * string errorMessage;
1268  *
1269  * //apply some metric
1270  * graph->applyPropertyAlgorithm("Degree", prop, errorMessage);
1271  *
1272  * // save this state to be able to revert to it later
1273  * graph->push();
1274  *
1275  * //compute the quality of this metric, or whatever makes sense
1276  * int degreeQuality = prop->getMax();
1277  *
1278  * //compute another metric
1279  * graph->applyPropertyAlgorithm("Depth", prop, errorMessage);
1280  *
1281  * //compute its quality
1282  * int depthQuality = prop->getMax();
1283  *
1284  * //if the degree was better, revert back to the state where its contents were in prop.
1285  * if(degreeQuality > depthQuality) {
1286  * graph->pop();
1287  * }
1288  *
1289  * ...
1290  *
1291  * //revert back to the depth for some reason.
1292  * graph->unpop();
1293  * @endcode
1294  */
1295  virtual void unpop()=0;
1296 
1297  /**
1298  * @brief Checks if there is a state to revert to.
1299  * @return Whether there was a previous call to push() that was not yet pop()'ed.
1300  */
1301  virtual bool canPop()=0;
1302 
1303  /**
1304  * @brief Checks if the last undone modifications can be redone.
1305  * @return Whether it is possible to re-do modifications that have been undone by pop().
1306  */
1307  virtual bool canUnpop()=0;
1308 
1309  /**
1310  * @brief Checks if it is possible to call pop() and then unPop(), to undo then re-do modifications.
1311  * @return Whether it is possible to undo and then redo.
1312  */
1313  virtual bool canPopThenUnpop()=0;
1314 
1315  // meta nodes management
1316  /**
1317  * @brief Creates a meta-node from a set of nodes.
1318  * Every edges from any node in the set to another node of the graph will be replaced with meta edges
1319  * from the meta node to the other nodes.
1320  * @warning This method will fail when called on the root graph.
1321  *
1322  * @param nodeSet The nodes to put into the meta node.
1323  * @param multiEdges Whether a meta edge should be created for each underlying edge.
1324  * @param delAllEdge Whether the underlying edges will be removed from the whole hierarchy.
1325  * @return The newly created meta node.
1326  */
1327  node createMetaNode(const std::set<node> &nodeSet, bool multiEdges = true, bool delAllEdge = true);
1328 
1329  /**
1330  * @brief Populates a quotient graph with one meta node
1331  * for each iterated graph.
1332  *
1333  * @param itS a Graph iterator, (typically a subgraph iterator)
1334  * @param quotientGraph the graph that will contain the meta nodes
1335  * @param metaNodes will contains all the added meta nodes after the call
1336  *
1337  */
1338  void createMetaNodes(Iterator<Graph *> *itS, Graph *quotientGraph,
1339  std::vector<node>& metaNodes);
1340  /**
1341  * @brief Closes an existing subgraph into a metanode. Edges from nodes
1342  * in the subgraph to nodes outside the subgraph are replaced with
1343  * edges from the metanode to the nodes outside the subgraph.
1344  * @warning this method will fail when called on the root graph.
1345  *
1346  * @param subGraph an existing subgraph
1347  * @param multiEdges indicates if a meta edge will be created for each underlying edge
1348  * @param delAllEdge indicates if the underlying edges will be removed from the entire hierarchy
1349  */
1350  node createMetaNode(Graph* subGraph, bool multiEdges = true, bool delAllEdge = true);
1351 
1352  /**
1353  * @brief Opens a metanode and replaces all edges between that
1354  * meta node and other nodes in the graph.
1355  *
1356  * @warning this method will fail when called on the root graph.
1357  *
1358  * @param n The meta node to open.
1359  * @param updateProperties If set to true, open meta node will update inner nodes layout, color, size, etc
1360  */
1361  void openMetaNode(node n, bool updateProperties=true);
1362 
1363 protected:
1364  virtual DataSet &getNonConstAttributes() = 0;
1365  // designed to reassign an id to a previously deleted elt
1366  // used by GraphUpdatesRecorder
1367  virtual node restoreNode(node)=0;
1368  virtual void restoreNodes(const std::vector<node>& nodes)=0;
1369  virtual edge restoreEdge(edge, node source, node target)=0;
1370  virtual void restoreEdges(const std::vector<edge>& edges,
1371  const std::vector<std::pair<node, node> >& ends)=0;
1372  // designed to only update own structures
1373  // used by GraphUpdatesRecorder
1374  virtual void removeNode(const node)=0;
1375  virtual void removeEdge(const edge)=0;
1376 
1377  // to check if a property can be deleted
1378  // used by PropertyManager
1379  virtual bool canDeleteProperty(Graph* g, PropertyInterface *prop) {
1380  return getRoot()->canDeleteProperty(g, prop);
1381  }
1382 
1383  // internally used to deal with sub graph deletion
1384  virtual void removeSubGraph(Graph*)=0;
1385  virtual void clearSubGraphs()=0;
1386  virtual void restoreSubGraph(Graph*)=0;
1387  virtual void setSubGraphToKeep(Graph*)=0;
1388 
1389  // for notification of GraphObserver
1390  void notifyAddNode(const node n);
1391  void notifyAddNode(Graph*, const node n) {
1392  notifyAddNode(n);
1393  }
1394  void notifyAddEdge(const edge e);
1395  void notifyAddEdge(Graph*, const edge e) {
1396  notifyAddEdge(e);
1397  }
1398  void notifyBeforeSetEnds(const edge e);
1399  void notifyBeforeSetEnds(Graph*, const edge e) {
1400  notifyBeforeSetEnds(e);
1401  }
1402  void notifyAfterSetEnds(const edge e);
1403  void notifyAfterSetEnds(Graph*, const edge e) {
1404  notifyAfterSetEnds(e);
1405  }
1406  void notifyDelNode(const node n);
1407  void notifyDelNode(Graph*, const node n) {
1408  notifyDelNode(n);
1409  }
1410  void notifyDelEdge(const edge e);
1411  void notifyDelEdge(Graph*, const edge e) {
1412  notifyDelEdge(e);
1413  }
1414  void notifyReverseEdge(const edge e);
1415  void notifyReverseEdge(Graph*, const edge e) {
1416  notifyReverseEdge(e);
1417  }
1418  void notifyBeforeAddSubGraph(const Graph*);
1419  void notifyAfterAddSubGraph(const Graph*);
1420  void notifyBeforeAddSubGraph(Graph*, const Graph* sg) {
1421  notifyBeforeAddSubGraph(sg);
1422  }
1423  void notifyAfterAddSubGraph(Graph*, const Graph* sg) {
1424  notifyAfterAddSubGraph(sg);
1425  }
1426  void notifyBeforeDelSubGraph(const Graph*);
1427  void notifyAfterDelSubGraph(const Graph*);
1428  void notifyBeforeDelSubGraph(Graph*, const Graph* sg) {
1429  notifyBeforeDelSubGraph(sg);
1430  }
1431  void notifyAfterDelSubGraph(Graph*, const Graph* sg) {
1432  notifyAfterDelSubGraph(sg);
1433  }
1434 
1435  void notifyBeforeAddDescendantGraph(const Graph*);
1436  void notifyAfterAddDescendantGraph(const Graph*);
1437  void notifyBeforeDelDescendantGraph(const Graph*);
1438  void notifyAfterDelDescendantGraph(const Graph*);
1439 
1440  void notifyBeforeAddLocalProperty(const std::string&);
1441  void notifyAddLocalProperty(const std::string&);
1442  void notifyAddLocalProperty(Graph*, const std::string& name) {
1443  notifyAddLocalProperty(name);
1444  }
1445  void notifyBeforeDelLocalProperty(const std::string&);
1446  void notifyAfterDelLocalProperty(const std::string&);
1447  void notifyDelLocalProperty(Graph*, const std::string& name) {
1448  notifyBeforeDelLocalProperty(name);
1449  }
1450  void notifyBeforeSetAttribute(const std::string&);
1451  void notifyBeforeSetAttribute(Graph*, const std::string& name) {
1452  notifyBeforeSetAttribute(name);
1453  }
1454  void notifyAfterSetAttribute(const std::string&);
1455  void notifyAfterSetAttribute(Graph*, const std::string& name) {
1456  notifyAfterSetAttribute(name);
1457  }
1458  void notifyRemoveAttribute(const std::string&);
1459  void notifyRemoveAttribute(Graph*, const std::string& name) {
1460  notifyRemoveAttribute(name);
1461  }
1462  void notifyDestroy();
1463  void notifyDestroy(Graph*) {
1464  notifyDestroy();
1465  }
1466 
1467 protected:
1468 
1469  unsigned int id;
1470  TLP_HASH_MAP<std::string, tlp::PropertyInterface*> circularCalls;
1471 };
1472 
1473 /**
1474  * @ingroup Observation
1475  * Event class for specific events on Graph
1476  **/
1477 class TLP_SCOPE GraphEvent :public Event {
1478 public:
1479  // be careful about the ordering of the constants
1480  // in the enum below because it is used in some assertions
1481  enum GraphEventType {
1482  TLP_ADD_NODE = 0,
1483  TLP_DEL_NODE = 1,
1484  TLP_ADD_EDGE = 2,
1485  TLP_DEL_EDGE = 3,
1486  TLP_REVERSE_EDGE = 4,
1487  TLP_BEFORE_SET_ENDS = 5,
1488  TLP_AFTER_SET_ENDS = 6,
1489  TLP_ADD_NODES = 7,
1490  TLP_ADD_EDGES = 8,
1491  TLP_BEFORE_ADD_DESCENDANTGRAPH = 9,
1492  TLP_AFTER_ADD_DESCENDANTGRAPH = 10,
1493  TLP_BEFORE_DEL_DESCENDANTGRAPH = 11,
1494  TLP_AFTER_DEL_DESCENDANTGRAPH = 12,
1495  TLP_BEFORE_ADD_SUBGRAPH = 13,
1496  TLP_AFTER_ADD_SUBGRAPH = 14,
1497  TLP_BEFORE_DEL_SUBGRAPH = 15,
1498  TLP_AFTER_DEL_SUBGRAPH = 16,
1499  TLP_ADD_LOCAL_PROPERTY = 17,
1500  TLP_BEFORE_DEL_LOCAL_PROPERTY = 18,
1501  TLP_AFTER_DEL_LOCAL_PROPERTY = 19,
1502  TLP_ADD_INHERITED_PROPERTY = 20,
1503  TLP_BEFORE_DEL_INHERITED_PROPERTY = 21,
1504  TLP_AFTER_DEL_INHERITED_PROPERTY = 22,
1505  TLP_BEFORE_SET_ATTRIBUTE = 23,
1506  TLP_AFTER_SET_ATTRIBUTE = 24,
1507  TLP_REMOVE_ATTRIBUTE = 25,
1508  TLP_BEFORE_ADD_LOCAL_PROPERTY = 26,
1509  TLP_BEFORE_ADD_INHERITED_PROPERTY = 27
1510  };
1511 
1512  // constructor for node/edge events
1513  GraphEvent(const Graph& g, GraphEventType graphEvtType, unsigned int id,
1514  Event::EventType evtType = Event::TLP_MODIFICATION)
1515  : Event(g, evtType), evtType(graphEvtType) {
1516  info.eltId = id;
1517  }
1518  // constructor for nodes events
1519  GraphEvent(const Graph& g, GraphEventType graphEvtType,
1520  const std::vector<node>& nodes,
1521  Event::EventType evtType = Event::TLP_MODIFICATION)
1522  : Event(g, evtType), evtType(graphEvtType) {
1523  info.nodes = &nodes;
1524  }
1525  // constructor for edges events
1526  GraphEvent(const Graph& g, GraphEventType graphEvtType,
1527  const std::vector<edge>& edges,
1528  Event::EventType evtType = Event::TLP_MODIFICATION)
1529  : Event(g, evtType), evtType(graphEvtType) {
1530  info.edges = &edges;
1531  }
1532  // constructor for subgraph events
1533  GraphEvent(const Graph& g, GraphEventType graphEvtType,
1534  const Graph* sg)
1535  : Event(g, Event::TLP_MODIFICATION), evtType(graphEvtType) {
1536  info.subGraph = sg;
1537  }
1538 
1539  // constructor for attribute/property events
1540  GraphEvent(const Graph& g, GraphEventType graphEvtType,
1541  const std::string& str,
1542  Event::EventType evtType = Event::TLP_MODIFICATION)
1543  : Event(g, evtType), evtType(graphEvtType) {
1544  info.name = new std::string(str);
1545  }
1546 
1547  // destructor needed to cleanup name if any
1548  ~GraphEvent() {
1549  if (evtType > TLP_AFTER_DEL_SUBGRAPH)
1550  delete info.name;
1551  }
1552 
1553  Graph* getGraph() const {
1554  return dynamic_cast<Graph *>(sender());
1555  }
1556 
1557  node getNode() const {
1558  assert(evtType < TLP_ADD_EDGE);
1559  return node(info.eltId);
1560  }
1561 
1562  edge getEdge() const {
1563  assert(evtType > TLP_DEL_NODE && evtType < TLP_ADD_NODES);
1564  return edge(info.eltId);
1565  }
1566 
1567  const std::vector<node>& getNodes() const {
1568  assert(evtType == TLP_ADD_NODES);
1569  return *(info.nodes);
1570  }
1571 
1572  const std::vector<edge>& getEdges() const {
1573  assert(evtType == TLP_ADD_EDGES);
1574  return *(info.edges);
1575  }
1576 
1577  const Graph* getSubGraph() const {
1578  assert(evtType > TLP_ADD_EDGES && evtType < TLP_ADD_LOCAL_PROPERTY);
1579  return info.subGraph;
1580  }
1581 
1582  const std::string& getAttributeName() const {
1583  assert(evtType > TLP_AFTER_DEL_INHERITED_PROPERTY);
1584  return *(info.name);
1585  }
1586 
1587  const std::string& getPropertyName() const {
1588  assert(evtType > TLP_AFTER_DEL_SUBGRAPH && evtType < TLP_BEFORE_SET_ATTRIBUTE);
1589  return *(info.name);
1590  }
1591 
1592  GraphEventType getType() const {
1593  return evtType;
1594  }
1595 
1596 protected:
1597  GraphEventType evtType;
1598  union {
1599  unsigned int eltId;
1600  const Graph* subGraph;
1601  std::string* name;
1602  const std::vector<node>* nodes;
1603  const std::vector<edge>* edges;
1604  } info;
1605 };
1606 
1607 }
1608 
1609 ///Print the graph (only nodes and edges) in ostream, in the tulip format
1610 TLP_SCOPE std::ostream& operator<< (std::ostream &,const tlp::Graph *);
1611 
1612 //================================================================================
1613 // these functions allow to use tlp::Graph as a key in a hash-based data structure (e.g. hashmap).
1614 //================================================================================
1615 #ifndef DOXYGEN_NOTFOR_DEVEL
1616 
1617 TLP_BEGIN_HASH_NAMESPACE {
1618  template <>
1619  struct TLP_SCOPE hash<const tlp::Graph *> {
1620  size_t operator()(const tlp::Graph *s) const {return size_t(s->getId());}
1621  };
1622  template <>
1623  struct TLP_SCOPE hash<tlp::Graph *> {
1624  size_t operator()(tlp::Graph *s) const {return size_t(s->getId());}
1625  };
1626 } TLP_END_HASH_NAMESPACE
1627 
1628 #endif // DOXYGEN_NOTFOR_DEVEL
1629 //include the template code
1630 #include <tulip/PropertyInterface.h>
1631 #include "cxx/Graph.cxx"
1632 #endif