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