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