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