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