Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/Graph.h
00001 /*
00002  *
00003  * This file is part of Tulip (www.tulip-software.org)
00004  *
00005  * Authors: David Auber and the Tulip development Team
00006  * from LaBRI, University of Bordeaux
00007  *
00008  * Tulip is free software; you can redistribute it and/or modify
00009  * it under the terms of the GNU Lesser General Public License
00010  * as published by the Free Software Foundation, either version 3
00011  * of the License, or (at your option) any later version.
00012  *
00013  * Tulip is distributed in the hope that it will be useful,
00014  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00015  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
00016  * See the GNU General Public License for more details.
00017  *
00018  */
00019 
00020 #ifndef Tulip_SUPERGRAPH_H
00021 #define Tulip_SUPERGRAPH_H
00022 
00023 #include <iostream>
00024 #include <string>
00025 #include <vector>
00026 
00027 #include <climits>
00028 #include <tulip/tulipconf.h>
00029 #include <tulip/DataSet.h>
00030 #include <tulip/Node.h>
00031 #include <tulip/Edge.h>
00032 #include <tulip/Observable.h>
00033 
00034 namespace tlp {
00035 
00036 class PropertyInterface;
00037 class BooleanProperty;
00038 class PluginProgress;
00039 template<class C>struct Iterator;
00040 
00041 /**
00042  * @enum This Enum describes the possible types of an element of the graph.
00043  *
00044  * It is used in functions that can return an edge or a node, to distinguish between the two cases.
00045  **/
00046 enum ElementType {
00047   /** This element describes a node **/
00048   NODE = 0,
00049   /** This element describes an edge **/
00050   EDGE = 1
00051 };
00052 
00053 /**
00054  * @ingroup Graph
00055  * @brief Loads a graph in the tlp format from a file (extension can be .tlp or .tlp.gz).
00056  * This function uses the "TLP Import" import plugin, and will fail if it is not loaded (By default this plugin is linked into the library and should be loaded).
00057  *
00058  * If the import fails (no such file, parse error, ...) NULL is returned.
00059  *
00060  * @param filename The file in tlp format to parse.
00061  * @return :Graph* The imported Graph, NULL if the import failed.
00062  **/
00063 TLP_SCOPE Graph * loadGraph(const std::string &filename, tlp::PluginProgress* progress = NULL);
00064 
00065 /**
00066  * @ingroup Graph
00067  * @brief Saves the corresponding graph and all its subgraphs to a file using the tlp format. Extension of the file can be either .tlp (human-readable text file) or .tlp.gz (gzipped text file).
00068  *
00069  * This function checks the file name for the '.gz' extension and uses a compressed output if found.
00070  *
00071  * This function uses the "TLP Export" export plugin, and will fail if it is not loaded (by default this plugin is linked into the library and should be loaded).
00072  *
00073  * @param graph the graph to save.
00074  * @param filename the file to save the graph to.
00075  * @return bool Whether the export was successfull or not.
00076  **/
00077 TLP_SCOPE bool saveGraph(Graph* graph, const std::string &filename, tlp::PluginProgress* progress = NULL);
00078 
00079 /**
00080  * @ingroup Graph
00081  * @brief Exports a graph using the specified export plugin with parameters stored in the DataSet.
00082  *
00083  * You determine the destination, whether by using a fstream, or by saving the contents of the stream to the destination of your choice.
00084  *
00085  * @param graph The graph to export.
00086  * @param outputStream The stream to export to. Can be a standard ostream, an ofstream, or even a gzipped ostream.
00087  * @param format The format to use to export the Graph.
00088  * @param dataSet The parameters to pass to the export plugin (e.g. additional data, options for the format)
00089  * @param progress A PluginProgress to report the progress of the operation, as well as final state. Defaults to NULL.
00090  * @return bool Whether the export was successfull or not.
00091  **/
00092 TLP_SCOPE bool exportGraph(Graph *graph, std::ostream &outputStream, const std::string &format, DataSet &dataSet, PluginProgress *progress=NULL);
00093 
00094 /**
00095  * @ingroup Graph
00096  * @brief Imports a graph using the specified import plugin with the parameters stored in the DataSet.
00097  *
00098  * If no graph is passed, then a new graph will be created. You can pass a graph in order to import data into it.
00099  * Returns the graph with imported data, or NULL if the import failed. In this case, the Pluginprogress should have an error that can be displayed.
00100  *
00101  * @param format The format to use to import the graph.
00102  * @param dataSet The parameters to pass to the import plugin (file to read, ...)
00103  * @param progress A PluginProgress to report the progress of the operation, as well as final state. Defaults to NULL.
00104  * @param newGraph The graph to import the data into. This can be usefull to import data into a subgraph. Defaults to NULL.
00105  * @return :Graph* The graph containing the imported data, or NULL in case of failure.
00106  **/
00107 TLP_SCOPE Graph* importGraph(const std::string &format, DataSet &dataSet, PluginProgress *progress=NULL,Graph *newGraph=NULL);
00108 
00109 /**
00110  * @ingroup Graph
00111  * @brief Creates a new, empty graph.
00112  *
00113  * This is a simple method factory to create a Graph implementation (remember, Graph is only an interface).
00114  *
00115  * This is the recommended way to create a new Graph.
00116  *
00117  * @return :Graph* A new, empty graph.
00118  **/
00119 TLP_SCOPE Graph* newGraph();
00120 
00121 /**
00122  * @ingroup Graph
00123  * Appends the selected part of the graph inG (properties, nodes and edges) into the graph outG.
00124  * If no selection is done (inSel=NULL), the whole inG graph is appended.
00125  * The output selection is used to select the appended nodes & edges
00126  * \warning The input selection is extended to all selected edge ends.
00127  */
00128 TLP_SCOPE void copyToGraph(Graph *outG, const Graph *inG, BooleanProperty* inSelection=NULL, BooleanProperty* outSelection=NULL );
00129 
00130 /**
00131  * @ingroup Graph
00132  * Removes the selected part of the graph ioG (properties values, nodes and edges).
00133  * If no selection is done (inSel=NULL), the whole graph is reseted to default value.
00134  * \warning The selection is extended to all selected edge ends.
00135  */
00136 TLP_SCOPE void removeFromGraph(Graph * ioG, BooleanProperty* inSelection=NULL);
00137 
00138 
00139 /**
00140  * @ingroup Graph
00141  * Gets an iterator over the root graphs. That is all the currently existing graphs which have been created using the tlp::newGraph, tlp::loadGraph or tlp::importGraph functions and are the root graphs of an existing graph hierarchy.
00142  * @return An iterator over all the root graphs. The caller of this function is responsible of the deletion of the returned iterator.
00143  */
00144 TLP_SCOPE Iterator<Graph*>* getRootGraphs();
00145 
00146 
00147 /**
00148  * @ingroup Graph
00149  * The class Graph is the interface of a Graph in the Tulip Library.
00150  *
00151  * There are a few principles to know when working with a Tulip Graph.
00152  *
00153  * @chapter Directed
00154  * Every edge is directed in a Tulip Graph.
00155  * You can choose to ignore this, but every edge has a source and destination.
00156  *
00157  * @chapter Inheritance
00158  *
00159  * Subgraphs inherit from their parent graph.
00160  * This is true of nodes and edges; every node and edge in a subgraph also exists in each of its parent graphs.
00161  * This is also true of properties; every property in a graph exist in all of its subgraphs, except if it has been replaced
00162  * by a local property.
00163  *
00164  * For instance, ig you have the following graph hierarchy:
00165  * root
00166  *  / \
00167  * A   B
00168  *
00169  * Every node in A is in root, and every node in B is in root.
00170  * Nodes can be in A and root but not B; or in B and root but not A.
00171  *
00172  * For instance, imagine a graph. You want to compare it to its Delaunay triangulation.
00173  * You need to create a subgraph that is a clone of the original (say this is A) to keep the original graph,
00174  * and another copy (say this one is B) on which you will perform the delaunay triangulation.
00175  *
00176  * B will have none of the original edges, and A will have only the original edges.
00177  *
00178  * As for properties; let's imagine the same graph hierarchy.
00179  * You want to compare two different layouts on the same graph.
00180  * You need to create two clone subgraphs, on each you make the 'viewLayout' property local.
00181  * This results in A and B having different values for the layout, but everything else in common.
00182  * You then can apply two different algorithms on A and B (e.g. Bubble Tree and Tree Radial).
00183  *
00184  * @chapter Meta Nodes
00185  * A meta node is a node representing a subgraph of the current graph.
00186  *
00187  * @chapter Undo Redo
00188  * The Tulip Graph object supports for undo and redo of modifications.
00189  *The operations affect the whole graph hierarchy, and cannot be limited to a subgraph.
00190  *
00191  */
00192 class TLP_SCOPE Graph : public Observable {
00193 
00194   friend class GraphAbstract;
00195   friend class GraphUpdatesRecorder;
00196   friend class GraphDecorator;
00197   friend class PropertyManager;
00198   friend class PropertyInterface;
00199 
00200 public:
00201   Graph():id(0) {}
00202   virtual ~Graph() {}
00203 
00204   /**
00205    * @brief Applies an algorithm plugin, identified by its name.
00206    * Algorithm plugins are subclasses of the tlp::Algorithm interface.
00207    * Parameters are transmitted to the algorithm trough the DataSet.
00208    * To determine a plugin's parameters, you can either:
00209    *
00210    * * refer to its documentation
00211    *
00212    * * use buildDefaultDataSet on the plugin object if you have an instance of it
00213    *
00214    * * call getPluginParameters() with the name of the plugin on the PluginLister
00215    *
00216    *
00217    * If an error occurs, a message describing the error should be stored in errorMessage.
00218    *
00219    * @param algorithm The algorithm to apply.
00220    * @param errorMessage A string that will be modified to contain an error message should an error occur.
00221    * @param dataSet The parameters to the algorithm. Defaults to NULL.
00222    * @param progress A PluginProgress to report the progress of the operation, as well as final state. Defaults to NULL.
00223    * @return bool Whether the algorithm was successfully applied.
00224    **/
00225   bool applyAlgorithm(const std::string &algorithm, std::string &errorMessage, DataSet *dataSet=NULL, PluginProgress *progress=NULL);
00226 
00227   //=========================================================================
00228   // Graph hierarchy access and building
00229   //=========================================================================
00230 
00231   /**
00232    * @brief Removes all nodes, edges and sub-graphs from this graph.
00233    *
00234    * Contrarily to creating a new Graph, this keeps attributes and properties.
00235    *
00236    * @return void
00237    **/
00238   virtual  void clear()=0;
00239 
00240   /**
00241     * @brief Creates and returns a new sub-graph of this graph.
00242     *
00243     * If a BooleanProperty is provided, all the nodes and edges for which it is true will be added to the subgraph.
00244     * If none is provided, then the subgraph will be empty.
00245     *
00246     * The id parameter should only be provided if you know exactly what you are doing; as Tulip will manage the subgraphs IDs when left to 0.
00247     * It is only used by the Graph loading as subgraphs ids are preserved when saving/loading a Graph.
00248     *
00249     * @param selection The elements to add to the new subgraph. Defaults to 0.
00250     * @param name The name of the newly created subgraph. Defaults to "unnamed".
00251     * @return :Graph* The newly created subgraph.
00252     **/
00253   virtual Graph *addSubGraph(BooleanProperty *selection=NULL,
00254                              const std::string& name = "unnamed")=0;
00255 
00256   /**
00257    * @brief Creates and returns a new named sub-graph of this graph.
00258    *
00259    * @param name The name of the newly created subgraph.
00260    * @return :Graph* The newly created subgraph.
00261    **/
00262   Graph *addSubGraph(const std::string& name);
00263 
00264   /**
00265    * @brief Creates and returns a subgraph that contains all the elements of this graph.
00266    *
00267    * @param name The name of the newly created subgraph. Defaults to "unnamed".
00268    * @param addSibling if true the clone subgraph will be a sibling of this graph, if false (the default) it will be a subgraph of this graph
00269    * @return :Graph* The newly created clone subgraph. NULL will be returned if addSibling is set to true and this graph is a root graph.
00270    **/
00271   virtual Graph* addCloneSubGraph(const std::string& name = "unnamed", bool addSibling = false);
00272 
00273   /**
00274    * @brief Creates and returns a new sub-graph of the graph induced by a set of nodes.
00275    * Every node contained in the given set of nodes is added to the subgraph.
00276    * Every edge connecting any two nodes in the set of given nodes is also added.
00277    * @param nodeSet The nodes to add to the subgraph. All the edges between these nodes are added too.
00278    * @param parentSubGraph If provided, is used as parent graph for the newly created subgraph instead of the graph this method is called on.
00279    * @return The newly created subgraph.
00280    */
00281   Graph *inducedSubGraph(const std::set<node>& nodeSet,
00282                          Graph* parentSubGraph = NULL);
00283 
00284   /**
00285    * @brief Deletes a sub-graph of this graph.
00286    * All subgraphs of the removed graph are re-parented to this graph.
00287    * For instance, with a graph hierarchy as follows :
00288    * root
00289    * / \
00290    * A  B
00291    *    /|\
00292    *   C D E
00293    *
00294    * @code root->delSubGraph(B);
00295    * would result in the following hierarchy:
00296    *  root
00297    * / | \\
00298    * A C D E
00299    *
00300    * @param graph The subgraph to delete.
00301    *
00302    * @see delAllSubGraphs() if you want to remove all descendants of a graph.
00303    */
00304   virtual void delSubGraph(Graph *graph)=0;
00305 
00306   /**
00307    * @brief Deletes a sub-graph of this graph and all of its sub-graphs.
00308    ** For instance, with a graph hierarchy as follows :
00309    * root
00310    * / \
00311    * A  B
00312    *    /|\
00313    *   C D E
00314    *
00315    * @codeline root->delSubGraph(B); @endcode
00316    * would result in the following hierarchy:
00317    *  root
00318    *   |
00319    *   A
00320    *
00321    * @param graph The subgraph to delete.
00322    * @see delSubGraph() if you want to keep the descendants of the subgraph to remove.
00323    */
00324   virtual void delAllSubGraphs(Graph *graph)=0;
00325 
00326   /**
00327    * @brief Returns the parent of the graph. If called on the root graph, it returns itself.
00328    * @return The parent of this graph (or itself if it is the root graph).
00329    * @see getRoot() to directly retrieve the root graph.
00330    */
00331   virtual Graph* getSuperGraph()const =0;
00332 
00333   /**
00334    * @brief Gets the root graph of the graph hierarchy.
00335    * @return The root graph of the graph hierarchy.
00336    */
00337   virtual Graph* getRoot() const =0;
00338 
00339   /**
00340    * @cond DOXYGEN_HIDDEN
00341    * @brief Sets the parent of a graph.
00342    * @warning ONLY USE IF YOU KNOW EXACTLY WHAT YOU ARE DOING.
00343    * @endcond
00344    */
00345   virtual void setSuperGraph(Graph *)=0;
00346 
00347   /**
00348    * @brief Gets an iterator over all the sub-graphs of the graph.
00349    * For instance, in the following graph hierarchy:
00350    ** root
00351    * / \
00352    * A  B
00353    *    /|\
00354    *   C D E
00355    *
00356    * @codeline root->getSubGraphs(); @endcode
00357    * Will return an iterator over A and B, but not C, D and E.
00358    * @return An iterator over this graph's direct subgraphs.
00359    */
00360   virtual Iterator<Graph *> * getSubGraphs() const=0;
00361 
00362   /**
00363    * @brief This method returns the nth subgraph.
00364    * Since subgraphs order cannot be ensured in every implementation, this method should be equivalent to:
00365    * @code
00366     int i=0;
00367     Iterator<Graph *> *it = g->getSubGraphs();
00368     while (it->hasNext()) {
00369       Graph *result = it->next();
00370       if (i++ == n) {
00371         delete it;
00372         return result;
00373       }
00374     }
00375     delete it;
00376     return NULL;
00377    * @endcode
00378    * @param n the index of the subgraph to retrieve.
00379    * @return The n-th subgraph.
00380    */
00381   virtual Graph *getNthSubGraph(unsigned int n) const;
00382 
00383   /**
00384    * @brief Return the number of direct sub-graphs.
00385    * For instance, in the following graph hierarchy:
00386    * root
00387    * / \
00388    * A  B
00389    *    /|\
00390    *   C D E
00391    *
00392    * @codeline root->numberOfSubGraphs(); @endcode
00393    * Will return 2.
00394    * @return The number of direct subgraphs.
00395    * @see numberOfDescendantGraphs() to count in the whole hierarchy.
00396    */
00397   virtual unsigned int numberOfSubGraphs() const=0;
00398 
00399   /**
00400    * @brief Return the number of descendant sub-graphs.
00401    * For instance, in the following graph hierarchy:
00402    * root
00403    * / \
00404    * A  B
00405    *    /|\
00406    *   C D E
00407    *
00408    * @codeline root->numberOfSubGraphs(); @endcode
00409    * Will return 5.
00410    * @return The number of descendants subgraphs.
00411    * @see numberOfSubGraphs() to count only direct subgraphs.
00412    */
00413   virtual unsigned int numberOfDescendantGraphs() const=0;
00414 
00415   /**
00416    * @brief Indicates if the graph argument is a direct sub-graph.
00417    * @param subGraph The graph to check is a subgraph of this graph.
00418    * @return Whether subGraph is a direct subgraph of this graph.
00419    * @see isDescendantGraph() to search in the whole hierarchy.
00420    */
00421   virtual bool isSubGraph(const Graph* subGraph) const=0;
00422 
00423   /**
00424    * @brief Indicates if the graph argument is a descendant of this graph.
00425    * @param subGraph The graph to check is a descendant of this graph.
00426    * @return Whether subGraph is a descendant of this graph.
00427    * @see isSubGraph to search only in direct subgraphs.
00428    */
00429   virtual bool isDescendantGraph(const Graph* subGraph) const=0;
00430 
00431   /**
00432    * @brief Returns a pointer on the sub-graph with the corresponding id
00433    * or NULL if there is no sub-graph with that id.
00434    * @param id The id of the subgraph to retrieve.
00435    * @return A subgraph of the given id, or null if no such subgraph exists on this graph.
00436    * @see getDescendantGraph(unsigned int) to search in the whole hierarchy.
00437    */
00438   virtual Graph* getSubGraph(unsigned int id) const=0;
00439 
00440   /**
00441    * @brief Returns a pointer on the sub-graph with the corresponding name
00442    * or NULL if there is no sub-graph with that name.
00443    * @param name The name of the subgraph to retrieve.
00444    * @return A Graph named name, or NULL if no such subgraph exists on this graph.
00445    * @see getDescendantGraph(const std::string &) to search in the whole hierarchy.
00446    */
00447   virtual Graph* getSubGraph(const std::string &name) const=0;
00448 
00449   /**
00450    * @brief Returns a pointer on the descendant with the corresponding id
00451    * or NULL if there is no descendant  with that id.
00452    * @param id The id of the descendant graph to retrieve.
00453    * @return A graph with the given id, or NULL if no such graph exists in this graph's descendants.
00454    * @see getSubGraph(unsigned int) to search only in direct subgraphs.
00455    */
00456   virtual Graph* getDescendantGraph(unsigned int id) const=0;
00457 
00458   /**
00459    * @brief Returns a pointer on the first descendant graph with the corresponding name
00460    * or NULL if there is no descendant graph with that name.
00461    * @param name The name of the descendant graph to look for.
00462    * @return A graph named name, or NULL if there is no such graph in this graph's descendants.
00463    * @see getSubGraph(const std::string &) to search only in direct subgraphs.
00464    */
00465   virtual Graph* getDescendantGraph(const std::string &name) const=0;
00466 
00467   /**
00468    * @brief Gets an iterator over all the descendant sub-graphs of the graph.
00469    * For instance, in the following graph hierarchy:
00470    ** root
00471    * / \
00472    * A  B
00473    *    /|\
00474    *   C D E
00475    *
00476    * @codeline root->getSubGraphs(); @endcode
00477    * Will return an iterator over A B, C, D and E.
00478    * @return An iterator over this graph's descendant subgraphs.
00479    */
00480   Iterator<Graph *> * getDescendantGraphs() const;
00481 
00482   //==============================================================================
00483   // Modification of the graph structure
00484   //==============================================================================
00485   /**
00486    * @brief Adds a new node in the graph and returns it. This node is also added in all
00487    * the ancestor graphs.
00488    * @return The newly added node.
00489    * @see addNodes() if you want to add more than one node.
00490    */
00491   virtual node addNode()=0;
00492 
00493   /**
00494    * @brief Adds new nodes in the graph and returns them in the addedNodes vector.
00495    * The new nodes are also added in all the ancestor graphs.
00496    *
00497    * @param nbNodes The number of nodes to add.
00498    * @param addedNodes The newly added nodes. This vector is cleared before being filled.
00499    * @see addNode() to add a single node.
00500    */
00501   virtual void addNodes(unsigned int nbNodes, std::vector<node>& addedNodes)=0;
00502 
00503   /**
00504    * @brief Adds an existing node in the graph. This node is also added in all the ancestor graphs.
00505    * This node must exists in the graph hierarchy (which means it must exist in the root graph).
00506    * You cannot add a node to the root graph this way (as it must already be an element of the root graph).
00507    * @warning Using this method on the root graph will display a warning on the console.
00508    *
00509    * @param n The node to add to a subgraph. This node must exist in the root graph.
00510    * @see addNode() to add a new node to a graph.
00511    */
00512   virtual void addNode(const node n)=0;
00513 
00514   /**
00515    * @brief Adds existing nodes in the graph. The nodes are also added in all the ancestor graphs.
00516    * as with addNode(const tlp::node), the nodes must exist in the graph hierarchy and thus exist in the root graph,
00517    * and node cannot be added this way to the root graph.
00518 
00519    * @warning Using this method on the root graph will display a warning on the console.
00520    * @warning The graph does not take ownership of the Iterator.
00521    *
00522    * @param nodes An iterator over nodes to add to this subgraph. The graph does not takes ownership of this iterator.
00523    */
00524   virtual void addNodes(Iterator<node>* nodes)=0;
00525 
00526   /**
00527   * @brief Adds existing nodes in the graph. The nodes are also added in all the ancestor graphs.
00528   * as with addNode(const tlp::node), the nodes must exist in the graph hierarchy and thus exist in the root graph,
00529   * and nodes cannot be added this way to the root graph.
00530 
00531   * @warning Using this method on the root graph will display a warning on the console.
00532   *
00533   * @param nodes a vector of nodes to add to this subgraph.
00534   */
00535   void addNodes(const std::vector<node>& nodes);
00536 
00537   /**
00538    * @brief Deletes a node in the graph.
00539    * This node is also removed in the sub-graphs hierarchy of the current graph.
00540    * @param n The node to delete.
00541    * @param deleteInAllGraphs Whether to delete in all its parent graphs or only in this graph. By default only removes in the current graph.
00542    * @see delNodes() to remove multiple nodes.
00543    */
00544   virtual void delNode(const node n, bool deleteInAllGraphs = false)=0;
00545 
00546   /**
00547    * @brief Deletes nodes in the graph.
00548    * These nodes are also removed in the sub-graphs hierarchy of the current graph.
00549    * @warning the graph does not take ownership of the Iterator.
00550    * @param it The nodes to delete.
00551    * @param deleteInAllGraphs Whether to delete in all its parent graphs or only in this graph. By default only removes in the current graph.
00552    * @see delNode() to remove a single node.
00553    */
00554   virtual void delNodes(Iterator<node>* it, bool deleteInAllGraphs = false)=0;
00555 
00556   /**
00557    * @brief Deletes nodes in the graph.
00558    * These nodes are also removed in the sub-graphs hierarchy of the current graph.
00559    * @warning the graph does not take ownership of the Iterator.
00560    * @param nodes a vector of the nodes to delete.
00561    * @param deleteInAllGraphs Whether to delete in all its parent graphs or only in this graph. By default only removes in the current graph.
00562    * @see delNode() to remove a single node.
00563    */
00564   void delNodes(const std::vector<node>& nodes, bool deleteInAllGraphs = false);
00565 
00566   /**
00567    * @brief Adds a new edge in the graph
00568    * This edge is also added in all the super-graph of the graph.
00569    * @param source The source of the edge.
00570    * @param target The target of the edge.
00571    * @return The newly added edge.
00572    * @see addEdges() to add multiple edges at once.
00573    */
00574   virtual edge addEdge(const node source, const node target)=0;
00575 
00576   /**
00577    * @brief Adds new edges in the graph and returns them the addedEdges vector.
00578    * The new edges are also added in all the graph ancestors.
00579    *
00580    * @warning If the edges vector contains a node that does not belong to this graph,
00581    * undefined behavior will ensue.
00582    * @param edges A vector describing between which nodes to add edges.
00583    * The first element of the pair is the source, the second is the destination.
00584    * @param addedEdges The newly added edges. This vector is cleared before being filled.
00585    *
00586    */
00587   virtual void addEdges(const std::vector<std::pair<node, node> >& edges,
00588                         std::vector<edge>& addedEdges)=0;
00589 
00590   /**
00591    * @brief Adds an existing edge in the graph. This edge is also added in all
00592    * the ancestor graphs.
00593    * The edge must be an element of the graph hierarchy, thus it must be
00594    * an element of the root graph.
00595    * @warning Using this method on the root graph will display a warning on the console.
00596    * @param e The edge to add to this subgraph.
00597    * @see addEgdes() to add more than one edge at once.
00598    * @see addNode() to add nodes.
00599    */
00600   virtual void addEdge(const edge e)=0;
00601 
00602   /**
00603    * @brief Adds existing edges in the graph. The edges are also added in all
00604    * the ancestor graphs.
00605    * The added edges must be elements of the graph hierarchy,
00606    * thus they must be elements of the root graph.
00607    * @warning Using this method on the root graph will display a warning on the console.
00608    * @warning The graph does not take ownership of the iterator.
00609    * @param edges The edges to add on this subgraph.
00610    */
00611   virtual void addEdges(Iterator<edge>* edges)=0;
00612 
00613   /**
00614    * @brief Adds existing edges in the graph. The edges are also added in all
00615    * the ancestor graphs.
00616    * The added edges must be elements of the graph hierarchy,
00617    * thus they must be elements of the root graph.
00618    * @warning Using this method on the root graph will display a warning on the console.
00619    * @param edges a vector of the edges to add on this subgraph.
00620    */
00621   void addEdges(const std::vector<edge>& edges);
00622 
00623   /**
00624    * @brief Deletes an edge in the graph. The edge is also removed in
00625    * the sub-graphs hierarchy.
00626    * The ordering of remaining edges is preserved.
00627    * @param e The edge to delete.
00628    * @param deleteInAllGraphs Whether to delete in all its parent graphs or only in this graph. By default only removes in the current graph.
00629    */
00630   virtual void delEdge(const edge e, bool deleteInAllGraphs = false)=0;
00631 
00632   /**
00633    * @brief Deletes edges in the graph. These edges are also removed in the sub-graphs hierarchy.
00634    * The ordering of remaining edges is preserved.
00635    * @warning The graph does not take ownership of the Iterator.
00636    * @param itE
00637    * @param deleteInAllGraphs  Whether to delete in all its parent graphs or only in this graph. By default only removes in the current graph.
00638    */
00639   virtual void delEdges(Iterator<edge>* itE, bool deleteInAllGraphs = false)=0;
00640 
00641   /**
00642    * @brief Deletes edges in the graph. These edges are also removed in the sub-graphs hierarchy.
00643    * The ordering of remaining edges is preserved.
00644    * @warning The graph does not take ownership of the Iterator.
00645    * @param edges a vector of the edges to delete
00646    * @param deleteInAllGraphs  Whether to delete in all its parent graphs or only in this graph. By default only removes in the current graph.
00647    */
00648   void delEdges(const std::vector<edge>& edges, bool deleteInAllGraphs = false);
00649 
00650   /**
00651    * @brief Sets the order of the edges around a node.
00652    * This operation ensures that adjacent edges of a node will
00653    * be ordered as they are in the vector of edges given in parameter.
00654    *
00655    * This can be useful if you want to make sure you retrieve the edges in a specific order when iterating upon them.
00656    * @param n The node whose edges to order.
00657    * @param edges The edges, in the order you want them.
00658    */
00659   virtual void setEdgeOrder(const node n,const std::vector<edge> &edges)=0;
00660 
00661   /**
00662    * @brief Swaps two edges in the adjacency list of a node.
00663    * @param n The node on whoch to swap the edges order.
00664    * @param e1 The first edge, that will take the second edge's position.
00665    * @param e2 The second edge, that will take the first edge's position.
00666    */
00667   virtual void swapEdgeOrder(const node n,const edge e1, const edge e2)=0;
00668 
00669   /**
00670    * @brief Sets the source of an edge to be the given node.
00671    * @param e The edge to change the source of.
00672    * @param source The new source of the edge.
00673    */
00674   virtual void setSource(const edge e, const node source) = 0;
00675 
00676   /**
00677    * @brief Sets the target of an edge to be the given node.
00678    * @param e The edge to change the target of.
00679    * @param target The new target of the edge.
00680    */
00681   virtual void setTarget(const edge e, const node target) = 0;
00682 
00683   /**
00684    * @brief Sets both the source and the target of an edge.
00685    * @param e The edge to set the source and target of.
00686    * @param source The new source of the edge.
00687    * @param target The new target of the edge.
00688    */
00689   virtual void setEnds(const edge e, const node source, const node target) = 0;
00690 
00691   /**
00692    * @brief Reverses the direction of an edge, the source becomes the target and the target
00693    *  becomes the source.
00694    * @warning The ordering is global to the entire graph hierarchy. Thus, by changing
00695    *  the ordering of a graph you change the ordering of the hierarchy.
00696    * @param e The edge top reverse.
00697    */
00698   virtual void reverse(const edge e)=0;
00699   // Attempts to reserve enough space to store nodes.
00700   // Only defined on root graph.
00701   virtual void reserveNodes(unsigned int nbNodes) = 0;
00702   // Attempts to reserve enough space to store edges.
00703   // Only defined on root graph.
00704   virtual void reserveEdges(unsigned int nbEdges) = 0;
00705   //================================================================================
00706   //Iterators on the graph structure.
00707   //================================================================================
00708   /**
00709    * @brief Finds the first node whose input degree equals 0.
00710    *
00711    * @return tlp::node The first encountered node with input degree of 0, or an invalid node if none was found.
00712    **/
00713   virtual tlp::node getSource() const;
00714 
00715   /**
00716    * @brief Gets a node on the graph.
00717    * @return Any node of the graph.
00718    */
00719   virtual node getOneNode() const =0;
00720 
00721   /**
00722    * @brief Gets an iterator over this graph's nodes.
00723    * @return An iterator over all the nodes of this graph.
00724    * @see getInNodes()
00725    * @see getOutNodes()
00726    * @see getInOutNodes()
00727    * @see getEdges()
00728    */
00729   virtual Iterator<node>* getNodes() const =0;
00730 
00731   /**
00732    * @brief Gets the i-th node in the input nodes of a given node.
00733    * An input node 'in' of a node 'N' is the source of an edge going from
00734    * 'in' to 'N'. e.g.
00735    * @code
00736    * node in = graph->addNode();
00737    * node N = graph->addNode();
00738    * graph->addEdge(in, N);
00739    * //in == graph->getInNode(N, 1);
00740    * @endcode
00741    *
00742    * If you have 5 input nodes on a node N, then
00743    * @codeline graph->getInNode(2); @endcode
00744    * will return the second of those nodes.
00745    * It will ignore the output nodes of this node.
00746    * @param n The node to get an input node of.
00747    * @param i The index of the input node to get.
00748    * @return The i-th input node of the given node.
00749    * @see getInNodes()
00750    * @see getInEdges()
00751    */
00752   virtual node getInNode(const node n,unsigned int i)const =0;
00753 
00754   /**
00755    * @brief Gets an iterator over the input nodes of a node.
00756    * @param n The node to get the input nodes of.
00757    * @return An iterator over the input nodes of a node.
00758    * @see getInNode()
00759    * @see getInOutNodes()
00760    * @see getInEdges()
00761    */
00762   virtual Iterator<node>* getInNodes(const node n) const =0;
00763 
00764   /**
00765    * @brief Gets the i-th node in the output nodes of a given node.
00766    * An output node 'out' of a node 'N' is the target of an edge going from
00767    * 'N' to 'out'. e.g.
00768    * @code
00769    * node N = graph->addNode();
00770    * node out = graph->addNode();
00771    * graph->addEdge(N, out);
00772    * //out == graph->getOutNode(N, 1);
00773    * @endcode
00774    *
00775    * If you have 5 output nodes on a node N, then
00776    * @codeline graph->getOutNode(2); @endcode
00777    * will return the second of those nodes.
00778    * It will ignore the input nodes of this node.
00779    * @param n The node to get an output node of.
00780    * @param i The index of the output node to get.
00781    * @return The i-th output node of the given node.
00782    * @see getOutNodes()
00783    * @see getOutEdges()
00784    */
00785   virtual node getOutNode(const node n,unsigned int i) const =0;
00786 
00787   /**
00788    * @brief Gets an iterator over the output nodes of a node.
00789    * @param n The node to get the output nodes of.
00790    * @return An iterator over the output nodes of a node.
00791    * @see getOutNode()
00792    * @see getInOutNodes()
00793    * @see getOutEdges()
00794    */
00795   virtual Iterator<node>* getOutNodes(const node n) const =0;
00796 
00797   /**
00798    * @brief Gets an iterator over the neighbors of a given node.
00799    * @param n The node to retrieve the neighbors of.
00800    * @return An iterator over the node's neighbors.
00801    */
00802   virtual Iterator<node>* getInOutNodes(const node n) const =0;
00803 
00804   /**
00805    * @brief Gets an iterator performing a breadth-first search on the graph.
00806    * @param root The node from whom to start the BFS. If not provided, the root
00807    * node will be assigned to a source node in the graph (node with input degree equals to 0).
00808    * If there is no source node in the graph, a random node will be picked.
00809    * @return A stable iterator over the graph nodes in the BFS order.
00810    */
00811   virtual Iterator<node>* bfs(const node root = node()) const = 0;
00812 
00813   /**
00814    * @brief Gets an iterator performing a depth-first search on the graph.
00815    * @param root The node from whom to start the DFS. If not provided, the root
00816    * node will be assigned to a source node in the graph (node with input degree equals to 0).
00817    * If there is no source node in the graph, a random node will be picked.
00818    * @return A stable iterator over the graph nodes in the DFS order.
00819    */
00820   virtual Iterator<node>* dfs(const node root = node()) const = 0;
00821 
00822   /**
00823    * @brief Gets the underlying graph of a meta node.
00824    * @param metaNode The metanode.
00825    * @return The Graph pointed to by the metanode.
00826    * @see getEdgeMetaInfo()
00827    */
00828   virtual Graph* getNodeMetaInfo(const node metaNode) const = 0;
00829 
00830   /**
00831    * @brief Get an iterator over all the graph's edges.
00832    * @return An iterator over all the graph's edges.
00833    * @see getInEdges()
00834    * @see getOutEdges()
00835    * @see getInOutEdges()
00836    */
00837   virtual Iterator<edge>* getEdges() const =0;
00838 
00839   /**
00840    * @brief Gets an edge of the graph.
00841    * @return Any one of the graph's edges.
00842    */
00843   virtual edge getOneEdge() const =0;
00844 
00845   /**
00846    * @brief Gets an iterator over the output edges of a node.
00847    * @param n The node to get the output edges from.
00848    * @return An iterator over the node's output edges.
00849    * @see getEdges()
00850    * @see getOutEdges()
00851    * @see getInOutEdges()
00852    */
00853   virtual Iterator<edge>* getOutEdges(const node n) const =0;
00854 
00855   /**
00856    * @brief Gets an iterator over the edges of a node.
00857    * @param n The node to get the edges from.
00858    * @return An iterator over the node's edges.
00859    * @see getEdges()
00860    * @see getOutEdges()
00861    * @see getInEdges()
00862    */
00863   virtual Iterator<edge>* getInOutEdges(const node n) const =0;
00864 
00865   /**
00866    * @brief Gets an iterator over the input edges of a node.
00867    * @param n The node to get the input edges from.
00868    * @return An iterator over the node's input edges.
00869    * @see getEdges()
00870    * @see getOutEdges()
00871    * @see getInOutEdges()
00872    */
00873   virtual Iterator<edge>* getInEdges(const node n) const =0;
00874 
00875   /**
00876    * @brief Gets an iterator over the edges composing a meta edge.
00877    * @param metaEdge The metaEdge to get the real edges of.
00878    * @return An Iterator over the edges composing the metaEdge.
00879    * @see getNodeMetaInfo()
00880    */
00881   virtual Iterator<edge>* getEdgeMetaInfo(const edge metaEdge) const =0;
00882 
00883   //================================================================================
00884   // Graph, nodes and edges information about the graph stucture
00885   //================================================================================
00886   /**
00887    * @brief Gets the unique identifier of the graph.
00888    * @return The unique identifier of this graph.
00889    */
00890   unsigned int getId() const {
00891     return id;
00892   }
00893 
00894   /**
00895    * @brief Gets the number of nodes in this graph.
00896    * @return The number of nodes in this graph.
00897    * @see numberOfEdges()
00898    */
00899   virtual unsigned int numberOfNodes()const =0;
00900 
00901   /**
00902    * @brief Gets the number of edges in this graph.
00903    * @return The number of edges in this graph.
00904    * @see numberOfNodes()
00905    */
00906   virtual unsigned int numberOfEdges()const =0;
00907 
00908   /**
00909    * @param n The node to get the degree of.
00910    * @return The degree of the given node.
00911    */
00912   virtual unsigned int deg(const node n)const =0;
00913 
00914   /**
00915    * @brief Get the input degree of a node.
00916    * @param n The node to get the input degree of.
00917    * @return The input degree of the given node.
00918    */
00919   virtual unsigned int indeg(const node n)const =0;
00920 
00921   /**
00922    * @brief Get the output degree of a node.
00923    * @param n The node to get the output degree of.
00924    * @return The output degree of the given node.
00925    */
00926   virtual unsigned int outdeg(const node n)const =0;
00927 
00928   /**
00929    * @brief Gets the source of an edge.
00930    * @param e The edge to get the source of.
00931    * @return The source of the given edge.
00932    */
00933   virtual node source(const edge e)const =0;
00934 
00935   /**
00936    * @brief Gets the target of an edge.
00937    * @param e The edge to get the target of.
00938    * @return The target of the given edge.
00939    */
00940   virtual node target(const edge e)const =0;
00941 
00942   /**
00943    * @brief Gets the source and the target of an edge.
00944    * @param e The edge to get the ends of.
00945    * @return A pair whose first element is the source, and second is the target.
00946    */
00947   virtual const std::pair<node, node>& ends(const edge e)const=0;
00948 
00949   /**
00950    * @brief Gets the opposite node  of n through e.
00951    * @param e The edge linking the two nodes.
00952    * @param n The node at one end of e.
00953    * @return The node at the other end of e.
00954    */
00955   virtual node opposite(const edge e, const node n)const =0;
00956 
00957   /**
00958    * @brief Checks if an element belongs to this graph.
00959    * @param n The node to check if it is an element of the graph.
00960    * @return Whether or not the element belongs to the graph.
00961    */
00962   virtual bool isElement(const node n) const =0;
00963 
00964   /**
00965    * @brief Checks if a node is a meta node.
00966    * @param n The node to check if it is a meta node.
00967    * @return Whether or not the node is a meta node.
00968    */
00969   virtual bool isMetaNode(const node n) const =0;
00970 
00971   /**
00972    * @brief Checks if an element belongs to this graph.
00973    * @param e The edge to check if it is an element of the graph.
00974    * @return Whether or not the element belongs to the graph.
00975    */
00976   virtual bool isElement(const edge e) const =0;
00977 
00978   /**
00979    * @brief Checks if an edge is a meta edge.
00980    * @param e The edge to check if it is a meta edge.
00981    * @return Whether or not the edge is a meta edge.
00982    */
00983   virtual bool isMetaEdge(const edge e) const =0;
00984 
00985   /**
00986    * @brief Checks if an edge exists between two given nodes.
00987    * @param source The source of the hypothetical edge.
00988    * @param target The target of the hypothetical edge.
00989    * @param directed When set to false edges from target to source are also considered
00990    * @return true if such an edge exists
00991    */
00992   virtual bool hasEdge(const node source, const node target,
00993                        bool directed = true) const {
00994     return existEdge(source, target, directed).isValid();
00995   }
00996 
00997 
00998   /**
00999    * @brief Returns all the edges between two nodes.
01000    * @param source The source of the hypothetical edges.
01001    * @param target The target of the hypothetical edges.
01002    * @param directed When set to false edges from target to source are also considered
01003    * @return a vector of existing edges
01004    */
01005   virtual std::vector<edge> getEdges(const node source, const node target,
01006                                      bool directed = true) const=0;
01007 
01008   /**
01009    * @brief Returns the first edge found between the two given nodes.
01010    * @warning This function always returns an edge,
01011    * you need to check if this edge is valid with edge::isValid().
01012    * @param source The source of the hypothetical edge.
01013    * @param target The target of the hypothetical edge.
01014    * @param directed When set to false
01015    * an edge from target to source may also be returned
01016    * @return An edge that is only valid if it exists.
01017    */
01018   virtual edge existEdge(const node source, const node target,
01019                          bool directed = true) const=0;
01020 
01021   //================================================================================
01022   // Access to the graph attributes and to the node/edge property.
01023   //================================================================================
01024   /**
01025    * @brief Sets the name of the graph.
01026    * The name does not have to be unique, it is used for convenience.
01027    * @param name The new name of the graph.
01028    */
01029   virtual void setName(const std::string &name) = 0;
01030 
01031   /**
01032    * @brief Retrieves the name of the graph.
01033    * @return The name of the graph.
01034    */
01035   virtual std::string getName() const = 0;
01036 
01037   /**
01038    * @brief Gets the attributes of the graph.
01039    *
01040    * The attributes contains the name and any user-defined value.
01041    * @return The attributes of the graph.
01042    */
01043   const DataSet & getAttributes() const {
01044     return (const_cast<Graph *>(this))->getNonConstAttributes();
01045   }
01046 
01047   /**
01048    * @brief Gets an attribute on the graph.
01049    * @param name The name of the attribute to set.
01050    * @param value The value to set.
01051    * @return Whether the setting of the attribute was sucessful.
01052    */
01053   template<typename ATTRIBUTETYPE>
01054   bool getAttribute(const std::string &name, ATTRIBUTETYPE& value) const;
01055 
01056   /**
01057    * @brief Gets a copy of the attribute.
01058    * @param name The name of the attribute to retrieve.
01059    * @return A copy of the attribute to retrieve.
01060    */
01061   DataType* getAttribute(const std::string& name) const;
01062 
01063   /**
01064    * @brief Sets an attribute on the graph.
01065    * @param name The name of the attribute to set.
01066    * @param value The value to set on this attribute.
01067    */
01068   template<typename ATTRIBUTETYPE>
01069   void setAttribute(const std::string &name,const ATTRIBUTETYPE &value);
01070 
01071   /**
01072    * @brief Sets an attribute on the graph.
01073    * @param name The name of the attribute to set.
01074    * @param value The value to set.
01075    */
01076   void setAttribute(const std::string &name, const DataType* value);
01077 
01078   /**
01079    * @brief Removes an attribute on the graph.
01080    * @param name The name of the attribute to remove.
01081    */
01082   void removeAttribute(const std::string &name) {
01083     notifyRemoveAttribute(name);
01084     getNonConstAttributes().remove(name);
01085   }
01086 
01087   /**
01088    * @brief Checks if an attribute exists.
01089    * @param name The name of the attribute to check for.
01090    * @return Whether the attribute exists.
01091    */
01092   bool attributeExist(const std::string &name) {
01093     return getAttributes().exist(name);
01094   }
01095 
01096   /**
01097    * @brief Adds a property to the graph.
01098    * The graph takes ownership of the property. If you want to delete it, use
01099    * Graph::delLocalProperty().
01100    * @param name The unique identifier of the property.
01101    * @param prop The property to add.
01102    */
01103   virtual  void addLocalProperty(const std::string &name, PropertyInterface *prop)=0;
01104 
01105   /**
01106    * @brief Gets an existing property.
01107    * In DEBUG mode an assertion checks the existence of the property.
01108    *
01109    * The graph keeps ownership of the property, if you wish to remove it from the graph use
01110    * Graph::delLocalProperty().
01111    *
01112    * @param name The unique identifier of the property.
01113    * @return An existing property, or NULL if no property with the given name exists.
01114    */
01115   virtual PropertyInterface* getProperty(const std::string& name) const = 0;
01116 
01117   /**
01118    * @brief Gets a property on this graph.
01119    * The name of a property indentifies it uniquely.
01120    * Either there already exists a property with the given name, in which case it is returned.
01121    * Either no such porperty exists and it is created.
01122    *
01123    * The graph keeps ownership of the property, if you wish to remove it fgrom the graph use
01124    * Graph::delLocalProperty().
01125    * @warning using the wrong template parameter will cause a segmentation fault.
01126    * @param The unique identifier of the property.
01127    * @return The property of given name.
01128    */
01129   template<typename PropertyType>
01130   PropertyType* getLocalProperty(const std::string &name);
01131 
01132   /**
01133    * @brief Gets a property on this graph or one of its ancestors.
01134    * If the property already exists on the graph or in one of its ancestors, it is returned.
01135    * Otherwise a new property is created on this graph.
01136    *
01137    * The graph keeps ownership of the property, if you wish to remove it from the graph use
01138    * Graph::delLocalProperty().
01139    *
01140    * @warning using the wrong propertyType will result in a segmentation fault. Using an invalid property type will always return NULL.
01141    * @param name The unique identifier of the property.
01142    * @return An existing property, or a new one if none exists with the given name.
01143    */
01144   template<typename PropertyType>
01145   PropertyType* getProperty(const std::string &name);
01146 
01147   /**
01148    * @brief Gets a property on this graph, and this graph only.
01149    * This forwards the call to the template version of getLocalProperty(), with the correct template parameter deduced from the propertyType parameter.
01150    *
01151    * The graph keeps ownership of the property, if you wish to remove it from the graph use
01152    * Graph::delLocalProperty().
01153    *
01154    * @warning using the wrong propertyType will result in a segmentation fault. Using an invalid property type will always return NULL.
01155    * @param propertyName The unique identifier of the property.
01156    * @param propertyType A string describing the type of the property.
01157    * @return The property of given name.
01158    * @see getLocalProperty().
01159    */
01160   PropertyInterface *getLocalProperty(const std::string& propertyName, const std::string& propertyType);
01161 
01162   /**
01163    * @brief Gets a property on this graph or one of its ancestors.
01164    * This forwards the call to the template version of getProperty(), with the correct template parameter deduced from the propertyType parameter.
01165    *
01166    * The graph keeps ownership of the property, if you wish to remove it from the graph use
01167    * Graph::delLocalProperty().
01168    *
01169    * @warning using the wrong propertyType will result in a segmentation fault. Using an invalid property type will always return NULL.
01170    * @param propertyName The unique identifier of the property.
01171    * @param propertyType A string describing the type of the property.
01172    * @return The property of given name.
01173    * @see getProperty().
01174    */
01175   PropertyInterface *getProperty(const std::string& propertyName, const std::string& propertyType);
01176 
01177   /**
01178    * @brief Checks if a property exists in this graph or one of its ancestors.
01179    * @param The unique identifier of the property.
01180    * @return Whether a property with the given name exists.
01181    */
01182   virtual  bool existProperty(const std::string& name) const = 0;
01183 
01184   /**
01185    * @brief Checks if a property exists in this graph.
01186    * @param The unique identifier of the property.
01187    * @return Whether a property with the given name exists.
01188    */
01189   virtual  bool existLocalProperty(const std::string& name) const = 0;
01190 
01191   /**
01192    * @brief Removes and deletes a property from this graph.
01193    * The property is removed from the graph's property pool, meaning its name can now be used by another property.
01194    * The object is deleted and the memory freed.
01195    * @param name The unique identifier of the property.
01196    */
01197   virtual  void delLocalProperty(const std::string& name)=0;
01198 
01199   /**
01200    * @brief Gets an iterator over the names of the local properties of this graph.
01201    * @return An iterator over this graph's properties names.
01202    */
01203   virtual Iterator<std::string>* getLocalProperties() const=0;
01204 
01205   /**
01206    * @brief Gets an iterator over the local properties of this graph.
01207    * @return An iterator over this graph's properties.
01208    */
01209   virtual Iterator<PropertyInterface*>* getLocalObjectProperties() const=0;
01210 
01211   /**
01212    * @brief Gets an iterator over the names of the properties inherited from this graph's ancestors,
01213    * excluding this graph's local properties.
01214    * @return An iterator over the names of the properties this graph inherited.
01215    */
01216   virtual Iterator<std::string>* getInheritedProperties() const=0;
01217 
01218   /**
01219    * @brief Gets an iterator over the properties inherited from this graph's ancestors,
01220    * excluding this graph's local properties.
01221    * @return An iterator over the properties this graph inherited.
01222    */
01223   virtual Iterator<PropertyInterface*>* getInheritedObjectProperties() const=0;
01224 
01225   /**
01226    * @brief Gets an iterator over the names of all the properties attached to this graph,
01227    * whether they are local or inherited.
01228    * @return An iterator over the names of all the properties attached to this graph.
01229    */
01230   virtual Iterator<std::string>* getProperties() const=0;
01231 
01232   /**
01233    * @brief Gets an iterator over the properties attached to this graph,
01234    * whether they are local or inherited.
01235    * @return An iterator over all of the properties attached to this graph.
01236    */
01237   virtual Iterator<PropertyInterface*>* getObjectProperties() const=0;
01238 
01239   /**
01240    * @brief Runs a plugin on the graph, whose result is a property.
01241    *
01242    * @param algorithm The name of the plugin to run.
01243    * @param result The property in which to put the results. All previous values will be erased.
01244    * @param errorMessage Stores the error message if the plugin fails.
01245    * @param progress A means of feedback during the plugin execution. Some plugins support being stopped or cancelled through this.
01246    * @param parameters The parameters of the algorithm. Some algorithms use this DataSet to output some additional information.
01247    * @return Whether the plugin executed successfully or not. If not, check the error message.
01248    *
01249    * @see PluginLister::getPluginParameters() to retrieve the list of default parameters for the pligin.
01250    */
01251   bool applyPropertyAlgorithm(const std::string &algorithm,
01252                               PropertyInterface* result,
01253                               std::string &errorMessage,
01254                               PluginProgress *progress=NULL,
01255                               DataSet *parameters=NULL);
01256 
01257   // updates management
01258   /**
01259    * @brief Saves the current state of the whole graph hierarchy and allows to revert to this state later on, using pop().
01260    * All modifications except those altering the ordering of the edges will be undone.
01261    *
01262    * This allows to undo/redo modifications on a graph.
01263    * This is mostly useful from a user interface point of view, but some algorithms use this mechanism to clean up before finishing.
01264    * For instance:
01265    * @code
01266    * Graph* graph = tlp::newGraph();
01267    * DoubleProperty* prop = graph->getProperty<DoubleProperty>("metric");
01268    * string errorMessage;
01269    *
01270    * //our super metric stuff we want to kee
01271    * DoubleProperty* superProperty = graph->getProperty<DoubleProperty>("superStuff");
01272    * vector<PropertyInterface*> propertiesToKeep;
01273    * propertiesToKeep.push_back(superProperty);
01274    *
01275    *
01276    * //apply some metric
01277    * graph->applyPropertyAlgorithm("Degree", prop, errorMessage);
01278    *
01279    * // save this state to be able to revert to it later
01280    * //however we do not want to allow to unpop(), which would go forward again to the state where prop contains 'Depth'.
01281    * //this saves some memory.
01282    * //Also we always want to keep the value of our super property, so we pass it in the collection of properties to leave unaffected by the pop().
01283    * graph->push(false, propertiesToKeep);
01284    *
01285    * //compute the quality of this metric, or whatever makes sense
01286    * int degreeQuality = prop->getMax();
01287    *
01288    * //compute another metric
01289    * graph->applyPropertyAlgorithm("Depth", prop, errorMessage);
01290    *
01291    * //compute our secret metric, that depends on depth
01292    * graph->applyPropertyAlgorithm("MySuperSecretAlgorithm", superProperty, errorMessage);
01293    *
01294    * //compute its quality
01295    * int depthQuality = prop->getMax();
01296    *
01297    * //if the degree was better, revert back to the state where its contents were in prop.
01298    * if(degreeQuality > depthQuality) {
01299    *    //this does not affect superProperty, as we told the system not to consider it when recording modifications to potentially revert.
01300    *    graph->pop();
01301    * }
01302    *
01303    * //do some stuff using our high quality metric
01304    * ColorProperty* color = graph->getProperty("viewColor");
01305    * graph->applyPropertyAlgorithm("Color Mapping", color, errorMessage);
01306    *
01307    * @endcode
01308    *
01309    * @param unpopAllowed Whether or not to allow to re-do the modifications once they are undone.
01310    * @param propertiesToPreserveOnPop A collection of properties whose state to preserve when using pop().
01311    * @see pop()
01312    * @see unpop()
01313    * @see canPop()
01314    * @see canUnPop()
01315    * @see canPopThenUnPop()
01316    */
01317   virtual void push(bool unpopAllowed = true,
01318                     std::vector<PropertyInterface*>* propertiesToPreserveOnPop= NULL)=0;
01319 
01320   /**
01321    * @brief Undoes modifications and reverts the whole graph hierarchy back to a previous state.
01322    *
01323    * @param unpopAllowed Whether or not it is possible to redo what will be undoe by this call.
01324    */
01325   virtual void pop(bool unpopAllowed = true)=0;
01326 
01327   /**
01328    * @brief Re-perform actions that were undone using pop().
01329    *
01330    * For instance:
01331    * @code
01332    * DoubleProperty* prop = graph->getProperty<DoubleProperty>("metric");
01333    * string errorMessage;
01334    *
01335    * //apply some metric
01336    * graph->applyPropertyAlgorithm("Degree", prop, errorMessage);
01337    *
01338    * // save this state to be able to revert to it later
01339    * graph->push();
01340    *
01341    * //compute the quality of this metric, or whatever makes sense
01342    * int degreeQuality = prop->getMax();
01343    *
01344    * //compute another metric
01345    * graph->applyPropertyAlgorithm("Depth", prop, errorMessage);
01346    *
01347    * //compute its quality
01348    * int depthQuality = prop->getMax();
01349    *
01350    * //if the degree was better, revert back to the state where its contents were in prop.
01351    * if(degreeQuality > depthQuality) {
01352    *    graph->pop();
01353    * }
01354    *
01355    * ...
01356    *
01357    * //revert back to the depth for some reason.
01358    * graph->unpop();
01359    * @endcode
01360    */
01361   virtual void unpop()=0;
01362 
01363   /**
01364    * @brief Checks if there is a state to revert to.
01365    * @return Whether there was a previous call to push() that was not yet pop()'ed.
01366    */
01367   virtual bool canPop()=0;
01368 
01369   /**
01370    * @brief Checks if the last undone modifications can be redone.
01371    * @return Whether it is possible to re-do modifications that have been undone by pop().
01372    */
01373   virtual bool canUnpop()=0;
01374 
01375   /**
01376    * @brief Checks if it is possible to call pop() and then unPop(), to undo then re-do modifications.
01377    * @return Whether it is possible to undo and then redo.
01378    */
01379   virtual bool canPopThenUnpop()=0;
01380 
01381   // meta nodes management
01382   /**
01383    * @brief Creates a meta-node from a set of nodes.
01384    * Every edges from any node in the set to another node of the graph will be replaced with meta edges
01385    * from the meta node to the other nodes.
01386    * @warning This method will fail when called on the root graph.
01387    *
01388    * @param nodeSet The nodes to put into the meta node.
01389    * @param multiEdges Whether a meta edge should be created for each underlying edge.
01390    * @param delAllEdge Whether the underlying edges will be removed from the whole hierarchy.
01391    * @return The newly created meta node.
01392    */
01393   node createMetaNode(const std::set<node> &nodeSet, bool multiEdges = true, bool delAllEdge = true);
01394 
01395   /**
01396    *  @brief Populates a quotient graph with one meta node
01397    * for each iterated graph.
01398    *
01399    * @param itS a Graph iterator, (typically a subgraph iterator)
01400    * @param quotientGraph the graph that will contain the meta nodes
01401    * @param metaNodes will contains all the added meta nodes after the call
01402    *
01403    */
01404   void createMetaNodes(Iterator<Graph *> *itS, Graph *quotientGraph,
01405                        std::vector<node>& metaNodes);
01406   /**
01407    * @brief Closes an existing subgraph into a metanode.  Edges from nodes
01408    * in the subgraph to nodes outside the subgraph are replaced with
01409    * edges from the metanode to the nodes outside the subgraph.
01410    * @warning this method will fail when called on the root graph.
01411    *
01412    * @param subGraph an existing subgraph
01413    * @param multiEdges indicates if a meta edge will be created for each underlying edge
01414    * @param delAllEdge indicates if the underlying edges will be removed from the entire hierarchy
01415    */
01416   node createMetaNode(Graph* subGraph, bool multiEdges = true, bool delAllEdge = true);
01417 
01418   /**
01419    * @brief Opens a metanode and replaces all edges between that
01420    * meta node and other nodes in the graph.
01421    *
01422    * @warning this method will fail when called on the root graph.
01423    *
01424    * @param n The meta node to open.
01425    * @param updateProperties If set to true, open meta node will update inner nodes layout, color, size, etc
01426    */
01427   void openMetaNode(node n, bool updateProperties=true);
01428 
01429 protected:
01430   virtual DataSet &getNonConstAttributes() = 0;
01431   // designed to reassign an id to a previously deleted elt
01432   // used by GraphUpdatesRecorder
01433   virtual node restoreNode(node)=0;
01434   virtual void restoreNodes(const std::vector<node>& nodes)=0;
01435   virtual edge restoreEdge(edge, node source, node target)=0;
01436   virtual void restoreEdges(const std::vector<edge>& edges,
01437                             const std::vector<std::pair<node, node> >& ends)=0;
01438   // designed to only update own structures
01439   // used by GraphUpdatesRecorder
01440   virtual void removeNode(const node)=0;
01441   virtual void removeEdge(const edge)=0;
01442 
01443   // to check if a property can be deleted
01444   // used by PropertyManager
01445   virtual bool canDeleteProperty(Graph* g, PropertyInterface *prop) {
01446     return getRoot()->canDeleteProperty(g, prop);
01447   }
01448 
01449   // local property renaming
01450   // can failed if a property with the same name already exists
01451   virtual bool renameLocalProperty(PropertyInterface* prop,
01452                                    const std::string& newName)=0;
01453 
01454   // internally used to deal with sub graph deletion
01455   virtual void removeSubGraph(Graph*)=0;
01456   virtual void clearSubGraphs()=0;
01457   virtual void restoreSubGraph(Graph*)=0;
01458   virtual void setSubGraphToKeep(Graph*)=0;
01459 
01460   // for notification of GraphObserver
01461   void notifyAddNode(const node n);
01462   void notifyAddNode(Graph*, const node n) {
01463     notifyAddNode(n);
01464   }
01465   void notifyAddEdge(const edge e);
01466   void notifyAddEdge(Graph*, const edge e) {
01467     notifyAddEdge(e);
01468   }
01469   void notifyBeforeSetEnds(const edge e);
01470   void notifyBeforeSetEnds(Graph*, const edge e) {
01471     notifyBeforeSetEnds(e);
01472   }
01473   void notifyAfterSetEnds(const edge e);
01474   void notifyAfterSetEnds(Graph*, const edge e) {
01475     notifyAfterSetEnds(e);
01476   }
01477   void notifyDelNode(const node n);
01478   void notifyDelNode(Graph*, const node n) {
01479     notifyDelNode(n);
01480   }
01481   void notifyDelEdge(const edge e);
01482   void notifyDelEdge(Graph*, const edge e) {
01483     notifyDelEdge(e);
01484   }
01485   void notifyReverseEdge(const edge e);
01486   void notifyReverseEdge(Graph*, const edge e) {
01487     notifyReverseEdge(e);
01488   }
01489   void notifyBeforeAddSubGraph(const Graph*);
01490   void notifyAfterAddSubGraph(const Graph*);
01491   void notifyBeforeAddSubGraph(Graph*, const Graph* sg) {
01492     notifyBeforeAddSubGraph(sg);
01493   }
01494   void notifyAfterAddSubGraph(Graph*, const Graph* sg) {
01495     notifyAfterAddSubGraph(sg);
01496   }
01497   void notifyBeforeDelSubGraph(const Graph*);
01498   void notifyAfterDelSubGraph(const Graph*);
01499   void notifyBeforeDelSubGraph(Graph*, const Graph* sg) {
01500     notifyBeforeDelSubGraph(sg);
01501   }
01502   void notifyAfterDelSubGraph(Graph*, const Graph* sg) {
01503     notifyAfterDelSubGraph(sg);
01504   }
01505 
01506   void notifyBeforeAddDescendantGraph(const Graph*);
01507   void notifyAfterAddDescendantGraph(const Graph*);
01508   void notifyBeforeDelDescendantGraph(const Graph*);
01509   void notifyAfterDelDescendantGraph(const Graph*);
01510 
01511   void notifyBeforeAddLocalProperty(const std::string&);
01512   void notifyAddLocalProperty(const std::string&);
01513   void notifyAddLocalProperty(Graph*, const std::string& name) {
01514     notifyAddLocalProperty(name);
01515   }
01516   void notifyBeforeDelLocalProperty(const std::string&);
01517   void notifyAfterDelLocalProperty(const std::string&);
01518   void notifyDelLocalProperty(Graph*, const std::string& name) {
01519     notifyBeforeDelLocalProperty(name);
01520   }
01521   void notifyBeforeSetAttribute(const std::string&);
01522   void notifyBeforeSetAttribute(Graph*, const std::string& name) {
01523     notifyBeforeSetAttribute(name);
01524   }
01525   void notifyAfterSetAttribute(const std::string&);
01526   void notifyAfterSetAttribute(Graph*, const std::string& name) {
01527     notifyAfterSetAttribute(name);
01528   }
01529   void notifyRemoveAttribute(const std::string&);
01530   void notifyRemoveAttribute(Graph*, const std::string& name) {
01531     notifyRemoveAttribute(name);
01532   }
01533   void notifyDestroy();
01534   void notifyDestroy(Graph*) {
01535     notifyDestroy();
01536   }
01537 
01538   unsigned int id;
01539   TLP_HASH_MAP<std::string, tlp::PropertyInterface*> circularCalls;
01540 };
01541 
01542 /**
01543  * @ingroup Observation
01544  * Event class for specific events on Graph
01545  **/
01546 class TLP_SCOPE GraphEvent :public Event {
01547 public:
01548   // be careful about the ordering of the constants
01549   // in the enum below because it is used in some assertions
01550   enum GraphEventType {
01551     TLP_ADD_NODE = 0,
01552     TLP_DEL_NODE = 1,
01553     TLP_ADD_EDGE = 2,
01554     TLP_DEL_EDGE = 3,
01555     TLP_REVERSE_EDGE = 4,
01556     TLP_BEFORE_SET_ENDS = 5,
01557     TLP_AFTER_SET_ENDS = 6,
01558     TLP_ADD_NODES = 7,
01559     TLP_ADD_EDGES = 8,
01560     TLP_BEFORE_ADD_DESCENDANTGRAPH = 9,
01561     TLP_AFTER_ADD_DESCENDANTGRAPH = 10,
01562     TLP_BEFORE_DEL_DESCENDANTGRAPH = 11,
01563     TLP_AFTER_DEL_DESCENDANTGRAPH = 12,
01564     TLP_BEFORE_ADD_SUBGRAPH = 13,
01565     TLP_AFTER_ADD_SUBGRAPH = 14,
01566     TLP_BEFORE_DEL_SUBGRAPH = 15,
01567     TLP_AFTER_DEL_SUBGRAPH = 16,
01568     TLP_ADD_LOCAL_PROPERTY = 17,
01569     TLP_BEFORE_DEL_LOCAL_PROPERTY = 18,
01570     TLP_AFTER_DEL_LOCAL_PROPERTY = 19,
01571     TLP_ADD_INHERITED_PROPERTY = 20,
01572     TLP_BEFORE_DEL_INHERITED_PROPERTY = 21,
01573     TLP_AFTER_DEL_INHERITED_PROPERTY = 22,
01574     TLP_BEFORE_RENAME_LOCAL_PROPERTY = 23,
01575     TLP_AFTER_RENAME_LOCAL_PROPERTY = 24,
01576     TLP_BEFORE_SET_ATTRIBUTE = 25,
01577     TLP_AFTER_SET_ATTRIBUTE = 26,
01578     TLP_REMOVE_ATTRIBUTE = 27,
01579     TLP_BEFORE_ADD_LOCAL_PROPERTY = 28,
01580     TLP_BEFORE_ADD_INHERITED_PROPERTY = 29
01581   };
01582 
01583   // constructor for node/edge events
01584   GraphEvent(const Graph& g, GraphEventType graphEvtType, unsigned int id,
01585              Event::EventType evtType = Event::TLP_MODIFICATION)
01586     : Event(g, evtType), evtType(graphEvtType) {
01587     info.eltId = id;
01588   }
01589   // constructor for nodes events
01590   GraphEvent(const Graph& g, GraphEventType graphEvtType,
01591              const std::vector<node>& nodes,
01592              Event::EventType evtType = Event::TLP_MODIFICATION)
01593     : Event(g, evtType), evtType(graphEvtType) {
01594     info.nodes = &nodes;
01595   }
01596   // constructor for edges events
01597   GraphEvent(const Graph& g, GraphEventType graphEvtType,
01598              const std::vector<edge>& edges,
01599              Event::EventType evtType = Event::TLP_MODIFICATION)
01600     : Event(g, evtType), evtType(graphEvtType) {
01601     info.edges = &edges;
01602   }
01603   // constructor for subgraph events
01604   GraphEvent(const Graph& g, GraphEventType graphEvtType,
01605              const Graph* sg)
01606     : Event(g, Event::TLP_MODIFICATION), evtType(graphEvtType) {
01607     info.subGraph = sg;
01608   }
01609 
01610   // constructor for attribute/property events
01611   GraphEvent(const Graph& g, GraphEventType graphEvtType,
01612              const std::string& str,
01613              Event::EventType evtType = Event::TLP_MODIFICATION)
01614     : Event(g, evtType), evtType(graphEvtType) {
01615     info.name = new std::string(str);
01616   }
01617 
01618   // constructor for rename property events
01619   GraphEvent(const Graph& g, GraphEventType graphEvtType,
01620              PropertyInterface* prop,
01621              const std::string& newName)
01622     : Event(g, Event::TLP_MODIFICATION), evtType(graphEvtType) {
01623     info.renamedProp =
01624       new std::pair<PropertyInterface*,std::string>(prop, newName);
01625   }
01626 
01627   // destructor needed to cleanup name if any
01628   ~GraphEvent() {
01629     if (evtType > TLP_AFTER_DEL_SUBGRAPH) {
01630       if (evtType == TLP_BEFORE_RENAME_LOCAL_PROPERTY ||
01631           evtType == TLP_AFTER_RENAME_LOCAL_PROPERTY)
01632         delete info.renamedProp;
01633       else
01634         delete info.name;
01635     }
01636   }
01637 
01638   Graph* getGraph() const {
01639     return static_cast<Graph *>(sender());
01640   }
01641 
01642   node getNode() const {
01643     assert(evtType < TLP_ADD_EDGE);
01644     return node(info.eltId);
01645   }
01646 
01647   edge getEdge() const {
01648     assert(evtType > TLP_DEL_NODE && evtType < TLP_ADD_NODES);
01649     return edge(info.eltId);
01650   }
01651 
01652   const std::vector<node>& getNodes() const {
01653     assert(evtType == TLP_ADD_NODES);
01654     return *(info.nodes);
01655   }
01656 
01657   const std::vector<edge>& getEdges() const {
01658     assert(evtType == TLP_ADD_EDGES);
01659     return *(info.edges);
01660   }
01661 
01662   const Graph* getSubGraph() const {
01663     assert(evtType > TLP_ADD_EDGES && evtType < TLP_ADD_LOCAL_PROPERTY);
01664     return info.subGraph;
01665   }
01666 
01667   const std::string& getAttributeName() const {
01668     assert(evtType > TLP_AFTER_DEL_INHERITED_PROPERTY);
01669     return *(info.name);
01670   }
01671 
01672   const std::string& getPropertyName() const;
01673 
01674   PropertyInterface* getProperty() const {
01675     assert(evtType == TLP_BEFORE_RENAME_LOCAL_PROPERTY ||
01676            evtType == TLP_AFTER_RENAME_LOCAL_PROPERTY);
01677     return info.renamedProp->first;
01678   }
01679 
01680   const std::string& getPropertyNewName() const {
01681     assert(evtType == TLP_BEFORE_RENAME_LOCAL_PROPERTY);
01682     return info.renamedProp->second;
01683   }
01684 
01685   const std::string& getPropertyOldName() const {
01686     assert(evtType == TLP_AFTER_RENAME_LOCAL_PROPERTY);
01687     return info.renamedProp->second;
01688   }
01689 
01690   GraphEventType getType() const {
01691     return evtType;
01692   }
01693 
01694 protected:
01695   GraphEventType evtType;
01696   union {
01697     unsigned int eltId;
01698     const Graph* subGraph;
01699     std::string* name;
01700     const std::vector<node>* nodes;
01701     const std::vector<edge>* edges;
01702     std::pair<PropertyInterface*, std::string>* renamedProp;
01703   } info;
01704 };
01705 
01706 }
01707 
01708 ///Print the graph (only nodes and edges) in ostream, in the tulip format
01709 TLP_SCOPE std::ostream& operator<< (std::ostream &,const tlp::Graph *);
01710 
01711 //================================================================================
01712 // these functions allow to use tlp::Graph as a key in a hash-based data structure (e.g. hashmap).
01713 //================================================================================
01714 #ifndef DOXYGEN_NOTFOR_DEVEL
01715 
01716 TLP_BEGIN_HASH_NAMESPACE {
01717   template <>
01718   struct TLP_SCOPE hash<const tlp::Graph *> {
01719     size_t operator()(const tlp::Graph *s) const {return size_t(s->getId());}
01720   };
01721   template <>
01722   struct TLP_SCOPE hash<tlp::Graph *> {
01723     size_t operator()(tlp::Graph *s) const {return size_t(s->getId());}
01724   };
01725 } TLP_END_HASH_NAMESPACE
01726 
01727 #endif // DOXYGEN_NOTFOR_DEVEL
01728 #include "cxx/Graph.cxx"
01729 #endif
 All Classes Files Functions Variables Enumerations Enumerator Properties