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