Tulip  4.3.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 
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 name The name of the newly created subgraph. Defaults to "unnamed".
265  * @return :Graph* The newly created subgraph.
266  **/
267  virtual Graph *addSubGraph(BooleanProperty *selection=NULL,
268  std::string name = "unnamed")=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.
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 an iterator performing a breadth-first search on the graph.
763  * @param root The node from whom to start the BFS. If not provided, the root
764  * node will be assigned to a source node in the graph (node with input degree equals to 0).
765  * If there is no source node in the graph, a random node will be picked.
766  * @return A stable iterator over the graph nodes in the BFS order.
767  */
768  virtual Iterator<node>* bfs(const node root = node()) const = 0;
769 
770  /**
771  * @brief Gets an iterator performing a depth-first search on the graph.
772  * @param root The node from whom to start the DFS. If not provided, the root
773  * node will be assigned to a source node in the graph (node with input degree equals to 0).
774  * If there is no source node in the graph, a random node will be picked.
775  * @return A stable iterator over the graph nodes in the DFS order.
776  */
777  virtual Iterator<node>* dfs(const node root = node()) const = 0;
778 
779  /**
780  * @brief Gets the underlying graph of a meta node.
781  * @param metaNode The metanode.
782  * @return The Graph pointed to by the metanode.
783  * @see getEdgeMetaInfo()
784  */
785  virtual Graph* getNodeMetaInfo(const node metaNode) const = 0;
786 
787  /**
788  * @brief Get an iterator over all the graph's edges.
789  * @return An iterator over all the graph's edges.
790  * @see getInEdges()
791  * @see getOutEdges()
792  * @see getInOutEdges()
793  */
794  virtual Iterator<edge>* getEdges() const =0;
795 
796  /**
797  * @brief Gets an edge of the graph.
798  * @return Any one of the graph's edges.
799  */
800  virtual edge getOneEdge() const =0;
801 
802  /**
803  * @brief Gets an iterator over the output edges of a node.
804  * @param n The node to get the output edges from.
805  * @return An iterator over the node's output edges.
806  * @see getEdges()
807  * @see getOutEdges()
808  * @see getInOutEdges()
809  */
810  virtual Iterator<edge>* getOutEdges(const node n) const =0;
811 
812  /**
813  * @brief Gets an iterator over the edges of a node.
814  * @param n The node to get the edges from.
815  * @return An iterator over the node's edges.
816  * @see getEdges()
817  * @see getOutEdges()
818  * @see getInEdges()
819  */
820  virtual Iterator<edge>* getInOutEdges(const node n) const =0;
821 
822  /**
823  * @brief Gets an iterator over the input edges of a node.
824  * @param n The node to get the input edges from.
825  * @return An iterator over the node's input edges.
826  * @see getEdges()
827  * @see getOutEdges()
828  * @see getInOutEdges()
829  */
830  virtual Iterator<edge>* getInEdges(const node n) const =0;
831 
832  /**
833  * @brief Gets an iterator over the edges composing a meta edge.
834  * @param metaEdge The metaEdge to get the real edges of.
835  * @return An Iterator over the edges composing the metaEdge.
836  * @see getNodeMetaInfo()
837  */
838  virtual Iterator<edge>* getEdgeMetaInfo(const edge metaEdge) const =0;
839 
840  //================================================================================
841  // Graph, nodes and edges informations about the graph stucture
842  //================================================================================
843  /**
844  * @brief Gets the unique identifier of the graph.
845  * @return The unique identifier of this graph.
846  */
847  unsigned int getId() const {
848  return id;
849  }
850 
851  /**
852  * @brief Gets the number of nodes in this graph.
853  * @return The number of nodes in this graph.
854  * @see numberOfEdges()
855  */
856  virtual unsigned int numberOfNodes()const =0;
857 
858  /**
859  * @brief Gets the number of edges in this graph.
860  * @return The number of edges in this graph.
861  * @see numberOfNodes()
862  */
863  virtual unsigned int numberOfEdges()const =0;
864 
865  /**
866  * @param n The node to get the degree of.
867  * @return The degree of the given node.
868  */
869  virtual unsigned int deg(const node n)const =0;
870 
871  /**
872  * @brief Get the input degree of a node.
873  * @param n The node to get the input degree of.
874  * @return The input degree of the given node.
875  */
876  virtual unsigned int indeg(const node n)const =0;
877 
878  /**
879  * @brief Get the output degree of a node.
880  * @param n The node to get the output degree of.
881  * @return The output degree of the given node.
882  */
883  virtual unsigned int outdeg(const node n)const =0;
884 
885  /**
886  * @brief Gets the source of an edge.
887  * @param e The edge to get the source of.
888  * @return The source of the given edge.
889  */
890  virtual node source(const edge e)const =0;
891 
892  /**
893  * @brief Gets the target of an edge.
894  * @param e The edge to get the target of.
895  * @return The target of the given edge.
896  */
897  virtual node target(const edge e)const =0;
898 
899  /**
900  * @brief Gets the source and the target of an edge.
901  * @param e The edge to get the ends of.
902  * @return A pair whose first element is the source, and second is the target.
903  */
904  virtual const std::pair<node, node>& ends(const edge e)const=0;
905 
906  /**
907  * @brief Gets the opposite node of n through e.
908  * @param e The edge linking the two nodes.
909  * @param n The node at one end of e.
910  * @return The node at the other end of e.
911  */
912  virtual node opposite(const edge e, const node n)const =0;
913 
914  /**
915  * @brief Checks if an element belongs to this graph.
916  * @param n The node to check if it is an element of the graph.
917  * @return Whether or not the element belongs to the graph.
918  */
919  virtual bool isElement(const node n) const =0;
920 
921  /**
922  * @brief Checks if a node is a meta node.
923  * @param n The node to check if it is a meta node.
924  * @return Whether or not the node is a meta node.
925  */
926  virtual bool isMetaNode(const node n) const =0;
927 
928  /**
929  * @brief Checks if an element belongs to this graph.
930  * @param e The edge to check if it is an element of the graph.
931  * @return Whether or not the element belongs to the graph.
932  */
933  virtual bool isElement(const edge e) const =0;
934 
935  /**
936  * @brief Checks if an edge is a meta edge.
937  * @param e The edge to check if it is a meta edge.
938  * @return Whether or not the edge is a meta edge.
939  */
940  virtual bool isMetaEdge(const edge e) const =0;
941 
942  /**
943  * @brief Checks if an edge exists between two given nodes.
944  * @param source The source of the hypothetical edge.
945  * @param target The target of the hypothetical edge.
946  * @param directed When set to false edges from target to source are also considered
947  * @return true if such an edge exists
948  */
949  virtual bool hasEdge(const node source, const node target,
950  bool directed = true) const {
951  return existEdge(source, target, directed).isValid();
952  }
953 
954 
955  /**
956  * @brief Returns all the edges between two nodes.
957  * @param source The source of the hypothetical edges.
958  * @param target The target of the hypothetical edges.
959  * @param directed When set to false edges from target to source are also considered
960  * @return a vector of existing edges
961  */
962  virtual std::vector<edge> getEdges(const node source, const node target,
963  bool directed = true) const=0;
964 
965  /**
966  * @brief Returns the first edge found between the two given nodes.
967  * @warning This function always returns an edge,
968  * you need to check if this edge is valid with edge::isValid().
969  * @param source The source of the hypothetical edge.
970  * @param target The target of the hypothetical edge.
971  * @param directed When set to false
972  * an edge from target to source may also be returned
973  * @return An edge that is only valid if it exists.
974  */
975  virtual edge existEdge(const node source, const node target,
976  bool directed = true) const=0;
977 
978  //================================================================================
979  // Access to the graph attributes and to the node/edge property.
980  //================================================================================
981  /**
982  * @brief Sets the name of the graph.
983  * The name does not have to be unique, it is used for convenience.
984  * @param name The new name of the graph.
985  */
986  virtual void setName(const std::string &name) = 0;
987 
988  /**
989  * @brief Retrieves the name of the graph.
990  * @return The name of the graph.
991  */
992  virtual std::string getName() const = 0;
993 
994  /**
995  * @brief Gets the attributes of the graph.
996  *
997  * The attributes contains the name and any user-defined value.
998  * @return The attributes of the graph.
999  */
1000  const DataSet & getAttributes() const {
1001  return (const_cast<Graph *>(this))->getNonConstAttributes();
1002  }
1003 
1004  /**
1005  * @brief Gets an attribute on the graph.
1006  * @param name The name of the attribute to set.
1007  * @param value The value to set.
1008  * @return Whether the setting of the attribute was sucessful.
1009  */
1010  template<typename ATTRIBUTETYPE>
1011  bool getAttribute(const std::string &name, ATTRIBUTETYPE& value) const;
1012 
1013  /**
1014  * @brief Gets a copy of the attribute.
1015  * @param name The name of the attribute to retrieve.
1016  * @return A copy of the attribute to retrieve.
1017  */
1018  DataType* getAttribute(const std::string& name) const;
1019 
1020  /**
1021  * @brief Sets an attribute on the graph.
1022  * @param name The name of the attribute to set.
1023  * @param value The value to set on this attribute.
1024  */
1025  template<typename ATTRIBUTETYPE>
1026  void setAttribute(const std::string &name,const ATTRIBUTETYPE &value);
1027 
1028  /**
1029  * @brief Sets an attribute on the graph.
1030  * @param name The name of the attribute to set.
1031  * @param value The value to set.
1032  */
1033  void setAttribute(const std::string &name, const DataType* value);
1034 
1035  /**
1036  * @brief Removes an attribute on the graph.
1037  * @param name The name of the attribute to remove.
1038  */
1039  void removeAttribute(const std::string &name) {
1040  notifyRemoveAttribute(name);
1041  getNonConstAttributes().remove(name);
1042  }
1043 
1044  /**
1045  * @brief Checks if an attribute exists.
1046  * @param name The name of the attribute to check for.
1047  * @return Whether the attribute exists.
1048  */
1049  bool attributeExist(const std::string &name) {
1050  return getAttributes().exist(name);
1051  }
1052 
1053  /**
1054  * @brief Adds a property to the graph.
1055  * The graph takes ownership of the property. If you want to delete it, use
1056  * Graph::delLocalProperty().
1057  * @param name The unique identifier of the property.
1058  * @param prop The property to add.
1059  */
1060  virtual void addLocalProperty(const std::string &name, PropertyInterface *prop)=0;
1061 
1062  /**
1063  * @brief Gets an existing property.
1064  * In DEBUG mode an assertion checks the existence of the property.
1065  *
1066  * The graph keeps ownership of the property, if you wish to remove it from the graph use
1067  * Graph::delLocalProperty().
1068  *
1069  * @param name The unique identifier of the property.
1070  * @return An existing property, or NULL if no property with the given name exists.
1071  */
1072  virtual PropertyInterface* getProperty(const std::string& name) const = 0;
1073 
1074  /**
1075  * @brief Gets a property on this graph.
1076  * The name of a property indentifies it uniquely.
1077  * Either there already exists a property with the given name, in which case it is returned.
1078  * Either no such porperty exists and it is created.
1079  *
1080  * The graph keeps ownership of the property, if you wish to remove it fgrom the graph use
1081  * Graph::delLocalProperty().
1082  * @warning using the wrong template parameter will cause a segmentation fault.
1083  * @param The unique identifier of the property.
1084  * @return The property of given name.
1085  */
1086  template<typename PropertyType>
1087  PropertyType* getLocalProperty(const std::string &name);
1088 
1089  /**
1090  * @brief Gets a property on this graph or one of its ancestors.
1091  * If the property already exists on the graph or in one of its ancestors, it is returned.
1092  * Otherwise a new property is created on this graph.
1093  *
1094  * The graph keeps ownership of the property, if you wish to remove it from the graph use
1095  * Graph::delLocalProperty().
1096  *
1097  * @warning using the wrong propertyType will result in a segmentation fault. Using an invalid property type will always return NULL.
1098  * @param name The unique identifier of the property.
1099  * @return An existing property, or a new one if none exists with the given name.
1100  */
1101  template<typename PropertyType>
1102  PropertyType* getProperty(const std::string &name);
1103 
1104  /**
1105  * @brief Gets a property on this graph, and this graph only.
1106  * This forwards the call to the template version of getLocalProperty(), with the correct template parameter deduced from the propertyType parameter.
1107  *
1108  * The graph keeps ownership of the property, if you wish to remove it from the graph use
1109  * Graph::delLocalProperty().
1110  *
1111  * @warning using the wrong propertyType will result in a segmentation fault. Using an invalid property type will always return NULL.
1112  * @param propertyName The unique identifier of the property.
1113  * @param propertyType A string describing the type of the property.
1114  * @return The property of given name.
1115  * @see getLocalProperty().
1116  */
1117  PropertyInterface *getLocalProperty(const std::string& propertyName, const std::string& propertyType);
1118 
1119  /**
1120  * @brief Gets a property on this graph or one of its ancestors.
1121  * This forwards the call to the template version of getProperty(), with the correct template parameter deduced from the propertyType parameter.
1122  *
1123  * The graph keeps ownership of the property, if you wish to remove it from the graph use
1124  * Graph::delLocalProperty().
1125  *
1126  * @warning using the wrong propertyType will result in a segmentation fault. Using an invalid property type will always return NULL.
1127  * @param propertyName The unique identifier of the property.
1128  * @param propertyType A string describing the type of the property.
1129  * @return The property of given name.
1130  * @see getProperty().
1131  */
1132  PropertyInterface *getProperty(const std::string& propertyName, const std::string& propertyType);
1133 
1134  /**
1135  * @brief Checks if a property exists in this graph or one of its ancestors.
1136  * @param The unique identifier of the property.
1137  * @return Whether a property with the given name exists.
1138  */
1139  virtual bool existProperty(const std::string& name) const = 0;
1140 
1141  /**
1142  * @brief Checks if a property exists in this graph.
1143  * @param The unique identifier of the property.
1144  * @return Whether a property with the given name exists.
1145  */
1146  virtual bool existLocalProperty(const std::string& name) const = 0;
1147 
1148  /**
1149  * @brief Removes and deletes a property from this graph.
1150  * The property is removed from the graph's property pool, meaning its name can now be used by another property.
1151  * The object is deleted and the memory freed.
1152  * @param name The unique identifier of the property.
1153  */
1154  virtual void delLocalProperty(const std::string& name)=0;
1155 
1156  /**
1157  * @brief Gets an iterator over the names of the local properties of this graph.
1158  * @return An iterator over this graph's properties names.
1159  */
1160  virtual Iterator<std::string>* getLocalProperties() const=0;
1161 
1162  /**
1163  * @brief Gets an iterator over the local properties of this graph.
1164  * @return An iterator over this graph's properties.
1165  */
1166  virtual Iterator<PropertyInterface*>* getLocalObjectProperties() const=0;
1167 
1168  /**
1169  * @brief Gets an iterator over the names of the properties inherited from this graph's ancestors,
1170  * excluding this graph's local properties.
1171  * @return An iterator over the names of the properties this graph inherited.
1172  */
1173  virtual Iterator<std::string>* getInheritedProperties() const=0;
1174 
1175  /**
1176  * @brief Gets an iterator over the properties inherited from this graph's ancestors,
1177  * excluding this graph's local properties.
1178  * @return An iterator over the properties this graph inherited.
1179  */
1180  virtual Iterator<PropertyInterface*>* getInheritedObjectProperties() const=0;
1181 
1182  /**
1183  * @brief Gets an iterator over the names of all the properties attached to this graph,
1184  * whether they are local or inherited.
1185  * @return An iterator over the names of all the properties attached to this graph.
1186  */
1187  virtual Iterator<std::string>* getProperties() const=0;
1188 
1189  /**
1190  * @brief Gets an iterator over the properties attached to this graph,
1191  * whether they are local or inherited.
1192  * @return An iterator over all of the properties attached to this graph.
1193  */
1194  virtual Iterator<PropertyInterface*>* getObjectProperties() const=0;
1195 
1196  /**
1197  * @brief Runs a plugin on the graph, whose result is a property.
1198  *
1199  * @param algorithm The name of the plugin to run.
1200  * @param result The property in which to put the results. All previous values will be erased.
1201  * @param errorMessage Stores the error message if the plugin fails.
1202  * @param progress A means of feedback during the plugin execution. Some plugins support being stopped or cancelled through this.
1203  * @param parameters The parameters of the algorithm. Some algorithms use this DataSet to output some additional informations.
1204  * @return Whether the plugin executed successfully or not. If not, check the error message.
1205  *
1206  * @see PluginLister::getPluginParameters() to retrieve the list of default parameters for the pligin.
1207  */
1208  bool applyPropertyAlgorithm(const std::string &algorithm,
1209  PropertyInterface* result,
1210  std::string &errorMessage,
1211  PluginProgress *progress=NULL,
1212  DataSet *parameters=NULL);
1213  /**
1214  * @cond DOXYGEN_HIDDEN
1215  *
1216  * @deprecated Use applyPropertyAlgorithm() instead.
1217  *
1218  * @endcond
1219  */
1220  template<typename PropertyType>
1221  _DEPRECATED bool computeProperty(const std::string &algorithm,
1222  PropertyType* result, std::string &msg,
1223  PluginProgress *progress=NULL, DataSet *data=NULL);
1224 
1225  // observation mechanism
1226  void _DEPRECATED addGraphObserver(Observable *) const;
1227  void _DEPRECATED removeGraphObserver(Observable *) const;
1228 
1229  // updates management
1230  /**
1231  * @brief Saves the current state of the whole graph hierarchy and allows to revert to this state later on, using pop().
1232  * All modifications except those altering the ordering of the edges will be undone.
1233  *
1234  * This allows to undo/redo modifications on a graph.
1235  * This is mostly useful from a user interface point of view, but some algorithms use this mechanism to clean up before finishing.
1236  * For instance:
1237  * @code
1238  * Graph* graph = tlp::newGraph();
1239  * DoubleProperty* prop = graph->getProperty<DoubleProperty>("metric");
1240  * string errorMessage;
1241  *
1242  * //our super metric stuff we want to kee
1243  * DoubleProperty* superProperty = graph->getProperty<DoubleProperty>("superStuff");
1244  * vector<PropertyInterface*> propertiesToKeep;
1245  * propertiesToKeep.push_back(superProperty);
1246  *
1247  *
1248  * //apply some metric
1249  * graph->applyPropertyAlgorithm("Degree", prop, errorMessage);
1250  *
1251  * // save this state to be able to revert to it later
1252  * //however we do not want to allow to unpop(), which would go forward again to the state where prop contains 'Depth'.
1253  * //this saves some memory.
1254  * //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().
1255  * graph->push(false, propertiesToKeep);
1256  *
1257  * //compute the quality of this metric, or whatever makes sense
1258  * int degreeQuality = prop->getMax();
1259  *
1260  * //compute another metric
1261  * graph->applyPropertyAlgorithm("Depth", prop, errorMessage);
1262  *
1263  * //compute our secret metric, that depends on depth
1264  * graph->applyPropertyAlgorithm("MySuperSecretAlgorithm", superProperty, errorMessage);
1265  *
1266  * //compute its quality
1267  * int depthQuality = prop->getMax();
1268  *
1269  * //if the degree was better, revert back to the state where its contents were in prop.
1270  * if(degreeQuality > depthQuality) {
1271  * //this does not affect superProperty, as we told the system not to consider it when recording modifications to potentially revert.
1272  * graph->pop();
1273  * }
1274  *
1275  * //do some stuff using our high quality metric
1276  * ColorProperty* color = graph->getProperty("viewColor");
1277  * graph->applyPropertyAlgorithm("Color Mapping", color, errorMessage);
1278  *
1279  * @endcode
1280  *
1281  * @param unpopAllowed Whether or not to allow to re-do the modifications once they are undone.
1282  * @param propertiesToPreserveOnPop A collection of properties whose state to preserve when using pop().
1283  * @see pop()
1284  * @see unpop()
1285  * @see canPop()
1286  * @see canUnPop()
1287  * @see canPopThenUnPop()
1288  */
1289  virtual void push(bool unpopAllowed = true,
1290  std::vector<PropertyInterface*>* propertiesToPreserveOnPop= NULL)=0;
1291 
1292  /**
1293  * @brief Undoes modifications and reverts the whole graph hierarchy back to a previous state.
1294  *
1295  * @param unpopAllowed Whether or not it is possible to redo what will be undoe by this call.
1296  */
1297  virtual void pop(bool unpopAllowed = true)=0;
1298 
1299  /**
1300  * @brief Re-perform actions that were undone using pop().
1301  *
1302  * For instance:
1303  * @code
1304  * DoubleProperty* prop = graph->getProperty<DoubleProperty>("metric");
1305  * string errorMessage;
1306  *
1307  * //apply some metric
1308  * graph->applyPropertyAlgorithm("Degree", prop, errorMessage);
1309  *
1310  * // save this state to be able to revert to it later
1311  * graph->push();
1312  *
1313  * //compute the quality of this metric, or whatever makes sense
1314  * int degreeQuality = prop->getMax();
1315  *
1316  * //compute another metric
1317  * graph->applyPropertyAlgorithm("Depth", prop, errorMessage);
1318  *
1319  * //compute its quality
1320  * int depthQuality = prop->getMax();
1321  *
1322  * //if the degree was better, revert back to the state where its contents were in prop.
1323  * if(degreeQuality > depthQuality) {
1324  * graph->pop();
1325  * }
1326  *
1327  * ...
1328  *
1329  * //revert back to the depth for some reason.
1330  * graph->unpop();
1331  * @endcode
1332  */
1333  virtual void unpop()=0;
1334 
1335  /**
1336  * @brief Checks if there is a state to revert to.
1337  * @return Whether there was a previous call to push() that was not yet pop()'ed.
1338  */
1339  virtual bool canPop()=0;
1340 
1341  /**
1342  * @brief Checks if the last undone modifications can be redone.
1343  * @return Whether it is possible to re-do modifications that have been undone by pop().
1344  */
1345  virtual bool canUnpop()=0;
1346 
1347  /**
1348  * @brief Checks if it is possible to call pop() and then unPop(), to undo then re-do modifications.
1349  * @return Whether it is possible to undo and then redo.
1350  */
1351  virtual bool canPopThenUnpop()=0;
1352 
1353  // meta nodes management
1354  /**
1355  * @brief Creates a meta-node from a set of nodes.
1356  * Every edges from any node in the set to another node of the graph will be replaced with meta edges
1357  * from the meta node to the other nodes.
1358  * @warning This method will fail when called on the root graph.
1359  *
1360  * @param nodeSet The nodes to put into the meta node.
1361  * @param multiEdges Whether a meta edge should be created for each underlying edge.
1362  * @param delAllEdge Whether the underlying edges will be removed from the whole hierarchy.
1363  * @return The newly created meta node.
1364  */
1365  node createMetaNode(const std::set<node> &nodeSet, bool multiEdges = true, bool delAllEdge = true);
1366 
1367  /**
1368  * @brief Populates a quotient graph with one meta node
1369  * for each iterated graph.
1370  *
1371  * @param itS a Graph iterator, (typically a subgraph iterator)
1372  * @param quotientGraph the graph that will contain the meta nodes
1373  * @param metaNodes will contains all the added meta nodes after the call
1374  *
1375  */
1376  void createMetaNodes(Iterator<Graph *> *itS, Graph *quotientGraph,
1377  std::vector<node>& metaNodes);
1378  /**
1379  * @brief Closes an existing subgraph into a metanode. Edges from nodes
1380  * in the subgraph to nodes outside the subgraph are replaced with
1381  * edges from the metanode to the nodes outside the subgraph.
1382  * @warning this method will fail when called on the root graph.
1383  *
1384  * @param subGraph an existing subgraph
1385  * @param multiEdges indicates if a meta edge will be created for each underlying edge
1386  * @param delAllEdge indicates if the underlying edges will be removed from the entire hierarchy
1387  */
1388  node createMetaNode(Graph* subGraph, bool multiEdges = true, bool delAllEdge = true);
1389 
1390  /**
1391  * @brief Opens a metanode and replaces all edges between that
1392  * meta node and other nodes in the graph.
1393  *
1394  * @warning this method will fail when called on the root graph.
1395  *
1396  * @param n The meta node to open.
1397  * @param updateProperties If set to true, open meta node will update inner nodes layout, color, size, etc
1398  */
1399  void openMetaNode(node n, bool updateProperties=true);
1400 
1401 protected:
1402  virtual DataSet &getNonConstAttributes() = 0;
1403  // designed to reassign an id to a previously deleted elt
1404  // used by GraphUpdatesRecorder
1405  virtual node restoreNode(node)=0;
1406  virtual void restoreNodes(const std::vector<node>& nodes)=0;
1407  virtual edge restoreEdge(edge, node source, node target)=0;
1408  virtual void restoreEdges(const std::vector<edge>& edges,
1409  const std::vector<std::pair<node, node> >& ends)=0;
1410  // designed to only update own structures
1411  // used by GraphUpdatesRecorder
1412  virtual void removeNode(const node)=0;
1413  virtual void removeEdge(const edge)=0;
1414 
1415  // to check if a property can be deleted
1416  // used by PropertyManager
1417  virtual bool canDeleteProperty(Graph* g, PropertyInterface *prop) {
1418  return getRoot()->canDeleteProperty(g, prop);
1419  }
1420 
1421  // internally used to deal with sub graph deletion
1422  virtual void removeSubGraph(Graph*)=0;
1423  virtual void clearSubGraphs()=0;
1424  virtual void restoreSubGraph(Graph*)=0;
1425  virtual void setSubGraphToKeep(Graph*)=0;
1426 
1427  // for notification of GraphObserver
1428  void notifyAddNode(const node n);
1429  void notifyAddNode(Graph*, const node n) {
1430  notifyAddNode(n);
1431  }
1432  void notifyAddEdge(const edge e);
1433  void notifyAddEdge(Graph*, const edge e) {
1434  notifyAddEdge(e);
1435  }
1436  void notifyBeforeSetEnds(const edge e);
1437  void notifyBeforeSetEnds(Graph*, const edge e) {
1438  notifyBeforeSetEnds(e);
1439  }
1440  void notifyAfterSetEnds(const edge e);
1441  void notifyAfterSetEnds(Graph*, const edge e) {
1442  notifyAfterSetEnds(e);
1443  }
1444  void notifyDelNode(const node n);
1445  void notifyDelNode(Graph*, const node n) {
1446  notifyDelNode(n);
1447  }
1448  void notifyDelEdge(const edge e);
1449  void notifyDelEdge(Graph*, const edge e) {
1450  notifyDelEdge(e);
1451  }
1452  void notifyReverseEdge(const edge e);
1453  void notifyReverseEdge(Graph*, const edge e) {
1454  notifyReverseEdge(e);
1455  }
1456  void notifyBeforeAddSubGraph(const Graph*);
1457  void notifyAfterAddSubGraph(const Graph*);
1458  void notifyBeforeAddSubGraph(Graph*, const Graph* sg) {
1459  notifyBeforeAddSubGraph(sg);
1460  }
1461  void notifyAfterAddSubGraph(Graph*, const Graph* sg) {
1462  notifyAfterAddSubGraph(sg);
1463  }
1464  void notifyBeforeDelSubGraph(const Graph*);
1465  void notifyAfterDelSubGraph(const Graph*);
1466  void notifyBeforeDelSubGraph(Graph*, const Graph* sg) {
1467  notifyBeforeDelSubGraph(sg);
1468  }
1469  void notifyAfterDelSubGraph(Graph*, const Graph* sg) {
1470  notifyAfterDelSubGraph(sg);
1471  }
1472 
1473  void notifyBeforeAddDescendantGraph(const Graph*);
1474  void notifyAfterAddDescendantGraph(const Graph*);
1475  void notifyBeforeDelDescendantGraph(const Graph*);
1476  void notifyAfterDelDescendantGraph(const Graph*);
1477 
1478  void notifyBeforeAddLocalProperty(const std::string&);
1479  void notifyAddLocalProperty(const std::string&);
1480  void notifyAddLocalProperty(Graph*, const std::string& name) {
1481  notifyAddLocalProperty(name);
1482  }
1483  void notifyBeforeDelLocalProperty(const std::string&);
1484  void notifyAfterDelLocalProperty(const std::string&);
1485  void notifyDelLocalProperty(Graph*, const std::string& name) {
1486  notifyBeforeDelLocalProperty(name);
1487  }
1488  void notifyBeforeSetAttribute(const std::string&);
1489  void notifyBeforeSetAttribute(Graph*, const std::string& name) {
1490  notifyBeforeSetAttribute(name);
1491  }
1492  void notifyAfterSetAttribute(const std::string&);
1493  void notifyAfterSetAttribute(Graph*, const std::string& name) {
1494  notifyAfterSetAttribute(name);
1495  }
1496  void notifyRemoveAttribute(const std::string&);
1497  void notifyRemoveAttribute(Graph*, const std::string& name) {
1498  notifyRemoveAttribute(name);
1499  }
1500  void notifyDestroy();
1501  void notifyDestroy(Graph*) {
1502  notifyDestroy();
1503  }
1504 
1505  unsigned int id;
1506  TLP_HASH_MAP<std::string, tlp::PropertyInterface*> circularCalls;
1507 };
1508 
1509 /**
1510  * @ingroup Observation
1511  * Event class for specific events on Graph
1512  **/
1513 class TLP_SCOPE GraphEvent :public Event {
1514 public:
1515  // be careful about the ordering of the constants
1516  // in the enum below because it is used in some assertions
1517  enum GraphEventType {
1518  TLP_ADD_NODE = 0,
1519  TLP_DEL_NODE = 1,
1520  TLP_ADD_EDGE = 2,
1521  TLP_DEL_EDGE = 3,
1522  TLP_REVERSE_EDGE = 4,
1523  TLP_BEFORE_SET_ENDS = 5,
1524  TLP_AFTER_SET_ENDS = 6,
1525  TLP_ADD_NODES = 7,
1526  TLP_ADD_EDGES = 8,
1527  TLP_BEFORE_ADD_DESCENDANTGRAPH = 9,
1528  TLP_AFTER_ADD_DESCENDANTGRAPH = 10,
1529  TLP_BEFORE_DEL_DESCENDANTGRAPH = 11,
1530  TLP_AFTER_DEL_DESCENDANTGRAPH = 12,
1531  TLP_BEFORE_ADD_SUBGRAPH = 13,
1532  TLP_AFTER_ADD_SUBGRAPH = 14,
1533  TLP_BEFORE_DEL_SUBGRAPH = 15,
1534  TLP_AFTER_DEL_SUBGRAPH = 16,
1535  TLP_ADD_LOCAL_PROPERTY = 17,
1536  TLP_BEFORE_DEL_LOCAL_PROPERTY = 18,
1537  TLP_AFTER_DEL_LOCAL_PROPERTY = 19,
1538  TLP_ADD_INHERITED_PROPERTY = 20,
1539  TLP_BEFORE_DEL_INHERITED_PROPERTY = 21,
1540  TLP_AFTER_DEL_INHERITED_PROPERTY = 22,
1541  TLP_BEFORE_SET_ATTRIBUTE = 23,
1542  TLP_AFTER_SET_ATTRIBUTE = 24,
1543  TLP_REMOVE_ATTRIBUTE = 25,
1544  TLP_BEFORE_ADD_LOCAL_PROPERTY = 26,
1545  TLP_BEFORE_ADD_INHERITED_PROPERTY = 27
1546  };
1547 
1548  // constructor for node/edge events
1549  GraphEvent(const Graph& g, GraphEventType graphEvtType, unsigned int id,
1550  Event::EventType evtType = Event::TLP_MODIFICATION)
1551  : Event(g, evtType), evtType(graphEvtType) {
1552  info.eltId = id;
1553  }
1554  // constructor for nodes events
1555  GraphEvent(const Graph& g, GraphEventType graphEvtType,
1556  const std::vector<node>& nodes,
1557  Event::EventType evtType = Event::TLP_MODIFICATION)
1558  : Event(g, evtType), evtType(graphEvtType) {
1559  info.nodes = &nodes;
1560  }
1561  // constructor for edges events
1562  GraphEvent(const Graph& g, GraphEventType graphEvtType,
1563  const std::vector<edge>& edges,
1564  Event::EventType evtType = Event::TLP_MODIFICATION)
1565  : Event(g, evtType), evtType(graphEvtType) {
1566  info.edges = &edges;
1567  }
1568  // constructor for subgraph events
1569  GraphEvent(const Graph& g, GraphEventType graphEvtType,
1570  const Graph* sg)
1571  : Event(g, Event::TLP_MODIFICATION), evtType(graphEvtType) {
1572  info.subGraph = sg;
1573  }
1574 
1575  // constructor for attribute/property events
1576  GraphEvent(const Graph& g, GraphEventType graphEvtType,
1577  const std::string& str,
1578  Event::EventType evtType = Event::TLP_MODIFICATION)
1579  : Event(g, evtType), evtType(graphEvtType) {
1580  info.name = new std::string(str);
1581  }
1582 
1583  // destructor needed to cleanup name if any
1584  ~GraphEvent() {
1585  if (evtType > TLP_AFTER_DEL_SUBGRAPH)
1586  delete info.name;
1587  }
1588 
1589  Graph* getGraph() const {
1590  return static_cast<Graph *>(sender());
1591  }
1592 
1593  node getNode() const {
1594  assert(evtType < TLP_ADD_EDGE);
1595  return node(info.eltId);
1596  }
1597 
1598  edge getEdge() const {
1599  assert(evtType > TLP_DEL_NODE && evtType < TLP_ADD_NODES);
1600  return edge(info.eltId);
1601  }
1602 
1603  const std::vector<node>& getNodes() const {
1604  assert(evtType == TLP_ADD_NODES);
1605  return *(info.nodes);
1606  }
1607 
1608  const std::vector<edge>& getEdges() const {
1609  assert(evtType == TLP_ADD_EDGES);
1610  return *(info.edges);
1611  }
1612 
1613  const Graph* getSubGraph() const {
1614  assert(evtType > TLP_ADD_EDGES && evtType < TLP_ADD_LOCAL_PROPERTY);
1615  return info.subGraph;
1616  }
1617 
1618  const std::string& getAttributeName() const {
1619  assert(evtType > TLP_AFTER_DEL_INHERITED_PROPERTY);
1620  return *(info.name);
1621  }
1622 
1623  const std::string& getPropertyName() const {
1624  assert(evtType > TLP_AFTER_DEL_SUBGRAPH && evtType < TLP_BEFORE_SET_ATTRIBUTE);
1625  return *(info.name);
1626  }
1627 
1628  GraphEventType getType() const {
1629  return evtType;
1630  }
1631 
1632 protected:
1633  GraphEventType evtType;
1634  union {
1635  unsigned int eltId;
1636  const Graph* subGraph;
1637  std::string* name;
1638  const std::vector<node>* nodes;
1639  const std::vector<edge>* edges;
1640  } info;
1641 };
1642 
1643 }
1644 
1645 ///Print the graph (only nodes and edges) in ostream, in the tulip format
1646 TLP_SCOPE std::ostream& operator<< (std::ostream &,const tlp::Graph *);
1647 
1648 //================================================================================
1649 // these functions allow to use tlp::Graph as a key in a hash-based data structure (e.g. hashmap).
1650 //================================================================================
1651 #ifndef DOXYGEN_NOTFOR_DEVEL
1652 
1653 TLP_BEGIN_HASH_NAMESPACE {
1654  template <>
1655  struct TLP_SCOPE hash<const tlp::Graph *> {
1656  size_t operator()(const tlp::Graph *s) const {return size_t(s->getId());}
1657  };
1658  template <>
1659  struct TLP_SCOPE hash<tlp::Graph *> {
1660  size_t operator()(tlp::Graph *s) const {return size_t(s->getId());}
1661  };
1662 } TLP_END_HASH_NAMESPACE
1663 
1664 #endif // DOXYGEN_NOTFOR_DEVEL
1665 #include "cxx/Graph.cxx"
1666 #endif