Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
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
37namespace tlp {
38
39class PropertyInterface;
40class BooleanProperty;
41class PluginProgress;
42template <class C>
43struct 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 **/
77TLP_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 **/
101TLP_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 **/
121TLP_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 **/
142TLP_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 **/
156TLP_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 */
165TLP_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 */
174TLP_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 */
234class 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
242public:
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 */
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 * @return The newly created meta node.
1597 */
1598 virtual node createMetaNode(const std::vector<node> &nodes, bool multiEdges = true,
1599 bool delAllEdge = true);
1600
1601 /**
1602 * @brief Populates a quotient graph with one meta node
1603 * for each iterated graph.
1604 *
1605 * @param itS a Graph iterator, (typically a subgraph iterator)
1606 * @param quotientGraph the graph that will contain the meta nodes
1607 * @param metaNodes will contains all the added meta nodes after the call
1608 *
1609 */
1610 virtual void createMetaNodes(Iterator<Graph *> *itS, Graph *quotientGraph,
1611 std::vector<node> &metaNodes);
1612 /**
1613 * @brief Closes an existing subgraph into a metanode. Edges from nodes
1614 * in the subgraph to nodes outside the subgraph are replaced with
1615 * edges from the metanode to the nodes outside the subgraph.
1616 * @warning this method will fail when called on the root graph.
1617 *
1618 * @param subGraph an existing subgraph
1619 * @param multiEdges indicates if a meta edge will be created for each underlying edge
1620 * @param delAllEdge indicates if the underlying edges will be removed from the entire hierarchy
1621 */
1622 virtual node createMetaNode(Graph *subGraph, bool multiEdges = true, bool delAllEdge = true);
1623
1624 /**
1625 * @brief Opens a metanode and replaces all edges between that
1626 * meta node and other nodes in the graph.
1627 *
1628 * @warning this method will fail when called on the root graph.
1629 *
1630 * @param n The meta node to open.
1631 * @param updateProperties If set to true, open meta node will update inner nodes layout, color,
1632 * size, etc
1633 */
1634 void openMetaNode(node n, bool updateProperties = true);
1635
1636 ///@cond DOXYGEN_HIDDEN
1637protected:
1638 virtual DataSet &getNonConstAttributes() = 0;
1639 // designed to reassign an id to a previously deleted elt
1640 // used by GraphUpdatesRecorder
1641 virtual void restoreNode(node) = 0;
1642 virtual void restoreEdge(edge, node source, node target) = 0;
1643 // designed to only update own structures
1644 // used by GraphUpdatesRecorder
1645 virtual void removeNode(const node) = 0;
1646 virtual void removeEdge(const edge) = 0;
1647
1648 // to check if a property can be deleted
1649 // used by PropertyManager
1650 virtual bool canDeleteProperty(Graph *g, PropertyInterface *prop) {
1651 return getRoot()->canDeleteProperty(g, prop);
1652 }
1653
1654 // local property renaming
1655 // can failed if a property with the same name already exists
1656 virtual bool renameLocalProperty(PropertyInterface *prop, const std::string &newName) = 0;
1657
1658 // internally used to deal with sub graph deletion
1659 virtual void removeSubGraph(Graph *) = 0;
1660 virtual void clearSubGraphs() = 0;
1661 virtual void restoreSubGraph(Graph *) = 0;
1662 virtual void setSubGraphToKeep(Graph *) = 0;
1663
1664 // for notification of GraphObserver
1665 void notifyAddNode(const node n);
1666 void notifyAddNode(Graph *, const node n) {
1667 notifyAddNode(n);
1668 }
1669 void notifyAddEdge(const edge e);
1670 void notifyAddEdge(Graph *, const edge e) {
1671 notifyAddEdge(e);
1672 }
1673 void notifyBeforeSetEnds(const edge e);
1674 void notifyBeforeSetEnds(Graph *, const edge e) {
1675 notifyBeforeSetEnds(e);
1676 }
1677 void notifyAfterSetEnds(const edge e);
1678 void notifyAfterSetEnds(Graph *, const edge e) {
1679 notifyAfterSetEnds(e);
1680 }
1681 void notifyDelNode(const node n);
1682 void notifyDelNode(Graph *, const node n) {
1683 notifyDelNode(n);
1684 }
1685 void notifyDelEdge(const edge e);
1686 void notifyDelEdge(Graph *, const edge e) {
1687 notifyDelEdge(e);
1688 }
1689 void notifyReverseEdge(const edge e);
1690 void notifyReverseEdge(Graph *, const edge e) {
1691 notifyReverseEdge(e);
1692 }
1693 void notifyBeforeAddSubGraph(const Graph *);
1694 void notifyAfterAddSubGraph(const Graph *);
1695 void notifyBeforeAddSubGraph(Graph *, const Graph *sg) {
1696 notifyBeforeAddSubGraph(sg);
1697 }
1698 void notifyAfterAddSubGraph(Graph *, const Graph *sg) {
1699 notifyAfterAddSubGraph(sg);
1700 }
1701 void notifyBeforeDelSubGraph(const Graph *);
1702 void notifyAfterDelSubGraph(const Graph *);
1703 void notifyBeforeDelSubGraph(Graph *, const Graph *sg) {
1704 notifyBeforeDelSubGraph(sg);
1705 }
1706 void notifyAfterDelSubGraph(Graph *, const Graph *sg) {
1707 notifyAfterDelSubGraph(sg);
1708 }
1709
1710 void notifyBeforeAddDescendantGraph(const Graph *);
1711 void notifyAfterAddDescendantGraph(const Graph *);
1712 void notifyBeforeDelDescendantGraph(const Graph *);
1713 void notifyAfterDelDescendantGraph(const Graph *);
1714
1715 void notifyBeforeAddLocalProperty(const std::string &);
1716 void notifyAddLocalProperty(const std::string &);
1717 void notifyAddLocalProperty(Graph *, const std::string &name) {
1718 notifyAddLocalProperty(name);
1719 }
1720 void notifyBeforeDelLocalProperty(const std::string &);
1721 void notifyAfterDelLocalProperty(const std::string &);
1722 void notifyDelLocalProperty(Graph *, const std::string &name) {
1723 notifyBeforeDelLocalProperty(name);
1724 }
1725 void notifyBeforeSetAttribute(const std::string &);
1726 void notifyBeforeSetAttribute(Graph *, const std::string &name) {
1727 notifyBeforeSetAttribute(name);
1728 }
1729 void notifyAfterSetAttribute(const std::string &);
1730 void notifyAfterSetAttribute(Graph *, const std::string &name) {
1731 notifyAfterSetAttribute(name);
1732 }
1733 void notifyRemoveAttribute(const std::string &);
1734 void notifyRemoveAttribute(Graph *, const std::string &name) {
1735 notifyRemoveAttribute(name);
1736 }
1737 void notifyDestroy();
1738 void notifyDestroy(Graph *) {
1739 notifyDestroy();
1740 }
1741
1742 unsigned int id;
1743 std::unordered_map<std::string, tlp::PropertyInterface *> circularCalls;
1744 ///@endcond
1745};
1746
1747/**
1748 * @ingroup Observation
1749 * Event class for specific events on Graph
1750 **/
1751class TLP_SCOPE GraphEvent : public Event {
1752public:
1753 // be careful about the ordering of the constants
1754 // in the enum below because it is used in some assertions
1755 enum GraphEventType {
1756 TLP_ADD_NODE = 0,
1757 TLP_DEL_NODE = 1,
1758 TLP_ADD_EDGE = 2,
1759 TLP_DEL_EDGE = 3,
1760 TLP_REVERSE_EDGE = 4,
1761 TLP_BEFORE_SET_ENDS = 5,
1762 TLP_AFTER_SET_ENDS = 6,
1763 TLP_ADD_NODES = 7,
1764 TLP_ADD_EDGES = 8,
1765 TLP_BEFORE_ADD_DESCENDANTGRAPH = 9,
1766 TLP_AFTER_ADD_DESCENDANTGRAPH = 10,
1767 TLP_BEFORE_DEL_DESCENDANTGRAPH = 11,
1768 TLP_AFTER_DEL_DESCENDANTGRAPH = 12,
1769 TLP_BEFORE_ADD_SUBGRAPH = 13,
1770 TLP_AFTER_ADD_SUBGRAPH = 14,
1771 TLP_BEFORE_DEL_SUBGRAPH = 15,
1772 TLP_AFTER_DEL_SUBGRAPH = 16,
1773 TLP_ADD_LOCAL_PROPERTY = 17,
1774 TLP_BEFORE_DEL_LOCAL_PROPERTY = 18,
1775 TLP_AFTER_DEL_LOCAL_PROPERTY = 19,
1776 TLP_ADD_INHERITED_PROPERTY = 20,
1777 TLP_BEFORE_DEL_INHERITED_PROPERTY = 21,
1778 TLP_AFTER_DEL_INHERITED_PROPERTY = 22,
1779 TLP_BEFORE_RENAME_LOCAL_PROPERTY = 23,
1780 TLP_AFTER_RENAME_LOCAL_PROPERTY = 24,
1781 TLP_BEFORE_SET_ATTRIBUTE = 25,
1782 TLP_AFTER_SET_ATTRIBUTE = 26,
1783 TLP_REMOVE_ATTRIBUTE = 27,
1784 TLP_BEFORE_ADD_LOCAL_PROPERTY = 28,
1785 TLP_BEFORE_ADD_INHERITED_PROPERTY = 29
1786 };
1787
1788 // constructor for node/edge/nodes/edges events
1789 GraphEvent(const Graph &g, GraphEventType graphEvtType, unsigned int id,
1790 Event::EventType evtType = Event::TLP_MODIFICATION)
1791 : Event(g, evtType), evtType(graphEvtType) {
1792 if (graphEvtType == TLP_ADD_NODES || graphEvtType == TLP_ADD_EDGES)
1793 info.nbElts = id;
1794 else
1795 info.eltId = id;
1796
1797 vectInfos.addedNodes = nullptr;
1798 }
1799 // constructor for subgraph events
1800 GraphEvent(const Graph &g, GraphEventType graphEvtType, const Graph *sg)
1801 : Event(g, Event::TLP_MODIFICATION), evtType(graphEvtType) {
1802 info.subGraph = sg;
1803 vectInfos.addedNodes = nullptr;
1804 }
1805
1806 // constructor for attribute/property events
1807 GraphEvent(const Graph &g, GraphEventType graphEvtType, const std::string &str,
1808 Event::EventType evtType = Event::TLP_MODIFICATION)
1809 : Event(g, evtType), evtType(graphEvtType) {
1810 info.name = new std::string(str);
1811 vectInfos.addedNodes = nullptr;
1812 }
1813
1814 // constructor for rename property events
1815 GraphEvent(const Graph &g, GraphEventType graphEvtType, PropertyInterface *prop,
1816 const std::string &newName)
1817 : Event(g, Event::TLP_MODIFICATION), evtType(graphEvtType) {
1818 info.renamedProp = new std::pair<PropertyInterface *, std::string>(prop, newName);
1819 vectInfos.addedNodes = nullptr;
1820 }
1821
1822 ~GraphEvent() override;
1823
1824 Graph *getGraph() const {
1825 return static_cast<Graph *>(sender());
1826 }
1827
1828 node getNode() const {
1829 assert(evtType < TLP_ADD_EDGE);
1830 return node(info.eltId);
1831 }
1832
1833 edge getEdge() const {
1834 assert(evtType > TLP_DEL_NODE && evtType < TLP_ADD_NODES);
1835 return edge(info.eltId);
1836 }
1837
1838 const std::vector<node> &getNodes() const;
1839
1840 unsigned int getNumberOfNodes() const {
1841 assert(evtType == TLP_ADD_NODES);
1842 return info.nbElts;
1843 }
1844
1845 const std::vector<edge> &getEdges() const;
1846
1847 unsigned int getNumberOfEdges() const {
1848 assert(evtType == TLP_ADD_EDGES);
1849 return info.nbElts;
1850 }
1851
1852 const Graph *getSubGraph() const {
1853 assert(evtType > TLP_ADD_EDGES && evtType < TLP_ADD_LOCAL_PROPERTY);
1854 return info.subGraph;
1855 }
1856
1857 const std::string &getAttributeName() const {
1858 assert(evtType > TLP_AFTER_DEL_INHERITED_PROPERTY);
1859 return *(info.name);
1860 }
1861
1862 const std::string &getPropertyName() const;
1863
1864 PropertyInterface *getProperty() const {
1865 assert(evtType == TLP_BEFORE_RENAME_LOCAL_PROPERTY ||
1866 evtType == TLP_AFTER_RENAME_LOCAL_PROPERTY);
1867 return info.renamedProp->first;
1868 }
1869
1870 const std::string &getPropertyNewName() const {
1871 assert(evtType == TLP_BEFORE_RENAME_LOCAL_PROPERTY);
1872 return info.renamedProp->second;
1873 }
1874
1875 const std::string &getPropertyOldName() const {
1876 assert(evtType == TLP_AFTER_RENAME_LOCAL_PROPERTY);
1877 return info.renamedProp->second;
1878 }
1879
1880 GraphEventType getType() const {
1881 return evtType;
1882 }
1883
1884protected:
1885 GraphEventType evtType;
1886 union {
1887 unsigned int eltId;
1888 const Graph *subGraph;
1889 std::string *name;
1890 unsigned int nbElts;
1891 std::pair<PropertyInterface *, std::string> *renamedProp;
1892 } info;
1893 union {
1894 std::vector<node> *addedNodes;
1895 std::vector<edge> *addedEdges;
1896 } vectInfos;
1897};
1898} // namespace tlp
1899
1900/// Print the graph (only nodes and edges) in ostream, in the tulip format
1901TLP_SCOPE std::ostream &operator<<(std::ostream &, const tlp::Graph *);
1902
1903#include "cxx/Graph.cxx"
1904#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
virtual void createMetaNodes(Iterator< Graph * > *itS, Graph *quotientGraph, std::vector< node > &metaNodes)
Populates a quotient graph with one meta node for each iterated graph.
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 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 edgePos(const edge e) const =0
Return the position of an edge in the vector of edges of the graph.
virtual edge getOneEdge() const =0
Returns the first edge in the graph.
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...
void openMetaNode(node n, bool updateProperties=true)
Opens a metanode and replaces all edges between that meta node and other nodes in the graph.
void setAttribute(const std::string &name, const DataType *value)
Sets an attribute on the graph.
virtual Graph * getSuperGraph() const =0
Returns the parent of the graph. If called on the root graph, it returns itself.
virtual void addNodes(Iterator< node > *nodes)=0
Adds existing nodes in the graph. The nodes are also added in all the ancestor graphs....
virtual node createMetaNode(Graph *subGraph, bool multiEdges=true, bool delAllEdge=true)
Closes an existing subgraph into a metanode. Edges from nodes in the subgraph to nodes outside the su...
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.
virtual Iterator< edge > * getEdgeMetaInfo(const edge metaEdge) const =0
Gets an iterator over the edges composing a meta edge.
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 Iterator< node > * bfs(const node root=node()) const =0
Gets an iterator performing a breadth-first search on the 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.
DataType * getAttribute(const std::string &name) const
Gets a copy of the attribute.
virtual void clear()=0
Removes all nodes, edges and subgraphs from this graph.
virtual Graph * getNthSubGraph(unsigned int n) const
This method returns the nth subgraph. Since subgraphs order cannot be ensured in every implementation...
virtual void setSource(const edge e, const node source)=0
Sets the source of an edge to be the given node.
virtual Iterator< node > * dfs(const node root=node()) const =0
Gets an iterator performing a depth-first search 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 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 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 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 const std::pair< node, node > & ends(const edge e) const =0
Gets the source and the target of an edge.
virtual bool isElement(const node n) const =0
Checks if an element belongs to this graph.
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.
const DataSet & getAttributes() const
Gets the attributes of the graph.
Definition: Graph.h:1225
virtual Iterator< Graph * > * getSubGraphs() const =0
Gets an iterator over all the subgraphs of the graph. For instance, in the following graph hierarchy:...
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 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 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,...
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...
unsigned int getId() const
Gets the unique identifier of the graph.
Definition: Graph.h:1067
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 bool canPop()=0
Checks if there is a state to revert to.
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 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 * 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 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 bool isEmpty() const
return whether the graph is empty or not.
Definition: Graph.h:1075
void addNodes(const std::vector< node > &nodes)
Adds existing nodes in the graph. The nodes are also added in all the ancestor graphs....
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 Iterator< node > * getInNodes(const node n) const =0
Gets an iterator over the input nodes of a node.
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 std::vector< edge > getEdges(const node source, const node target, bool directed=true) const =0
Returns all the edges between two nodes.
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.
virtual Iterator< node > * getOutNodes(const node n) const =0
Gets an iterator over the output nodes of a node.
virtual node createMetaNode(const std::vector< node > &nodes, bool multiEdges=true, bool delAllEdge=true)
Creates a meta-node from a vector of nodes. Every edges from any node in the vector to another node o...
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 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 Iterator< PropertyInterface * > * getObjectProperties() const =0
Gets an iterator over the properties attached to this graph, whether they are local or inherited.
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 Graph * getRoot() const =0
Gets the root graph of the graph hierarchy.
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 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...
virtual void addEdges(Iterator< edge > *edges)=0
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 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< 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< edge > * getInEdges(const node n) const =0
Gets an iterator over the input edges of a node.
Graph * addSubGraph(const std::string &name)
Creates and returns a new named subgraph of this graph.
virtual Iterator< edge > * getOutEdges(const node n) const =0
Gets an iterator over the output edges of a node.
virtual Graph * getNodeMetaInfo(const node metaNode) const =0
Gets the underlying graph of a meta node.
virtual Iterator< PropertyInterface * > * getLocalObjectProperties() const =0
Gets an iterator over the local properties of this graph.
virtual void popIfNoUpdates()=0
abort last push if no updates have been recorded
virtual Iterator< std::string > * getLocalProperties() const =0
Gets an iterator over the names of the local properties of this graph.
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 Iterator< edge > * getInOutEdges(const node n) const =0
Gets an iterator over the edges of a node.
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 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 Iterator< std::string > * getInheritedProperties() const =0
Gets an iterator over the names of the properties inherited from this graph's ancestors,...
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 bool canUnpop()=0
Checks if the last undone modifications can be redone.
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.
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 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 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...
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.
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 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.
virtual Graph * addSubGraph(BooleanProperty *selection=nullptr, const std::string &name="unnamed")=0
Creates and returns a new subgraph of this graph.
virtual Iterator< node > * getInOutNodes(const node n) const =0
Gets an iterator over the neighbors of a given 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< node > * getNodes() const =0
Gets an iterator over this graph's nodes.
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.
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.
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.
void removeFromGraph(Graph *ioG, BooleanProperty *inSelection=nullptr)
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).
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...
void copyToGraph(Graph *outG, const Graph *inG, BooleanProperty *inSelection=nullptr, BooleanProperty *outSelection=nullptr)
Graph * newGraph()
Creates a new, empty graph.
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.
Iterator< Graph * > * getRootGraphs()
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