Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/GraphTools.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 ///@cond DOXYGEN_HIDDEN
00020 
00021 #ifndef _TLPGRAPHTOOLS_H
00022 #define _TLPGRAPHTOOLS_H
00023 
00024 #include <set>
00025 #include <list>
00026 #include <tulip/tuliphash.h>
00027 #include <tulip/Node.h>
00028 #include <tulip/Edge.h>
00029 
00030 #include <tulip/PlanarConMap.h>
00031 
00032 namespace tlp {
00033 
00034 class BooleanProperty;
00035 class DoubleProperty;
00036 class IntegerProperty;
00037 class NumericProperty;
00038 
00039 /**
00040  *  This ordering was first introduced by C. Gutwenger and P. Mutzel in \n
00041  *  "Grid embeddings of biconnected planar graphs", \n
00042  *  "Extended Abstract, Max-Planck-Institut für Informatik," \n
00043  *  "Saarbrücken, Germany, 1997" \n
00044  *  Let n be the number of nodes, the original algorithm complexity is in O(n).\n
00045  *  But the implementation of the canonical ordering has not been made in O(n).\n
00046  */
00047 TLP_SCOPE std::vector<std::vector<node> > computeCanonicalOrdering(PlanarConMap *,
00048     std::vector<edge>  *dummyEdges = NULL,
00049     PluginProgress *pluginProgress = NULL);
00050 /**
00051  * Find all the graph centers, that version does not manage edge weight.
00052  * complexity O(n * m). Only works on connected graphs.
00053  */
00054 TLP_SCOPE std::vector<node> computeGraphCenters(Graph * graph);
00055 /**
00056  * return a node that can be considered as the graph center.
00057  * It is an heuristic, thus it is not absolutely sure that this
00058  * node is a graph center. Only works on connected graphs.
00059  */
00060 TLP_SCOPE node graphCenterHeuristic(Graph * graph,
00061                                     PluginProgress *pluginProgress = NULL);
00062 /**
00063  * return a new node connected to all previously
00064  * existing nodes which had a null indegree
00065  */
00066 TLP_SCOPE node makeSimpleSource(Graph* graph);
00067 
00068 TLP_SCOPE void makeProperDag(Graph* graph,std::list<node> &addedNodes,
00069                              TLP_HASH_MAP<edge,edge> &replacedEdges,
00070                              IntegerProperty* edgeLength = NULL);
00071 
00072 /**
00073    * Select a spanning forest of the graph,
00074    * i.e for all graph elements (nodes or edges) belonging to that forest
00075    * the selectionProperty associated value is true. The value is false
00076    * for the other elements
00077    */
00078 TLP_SCOPE void selectSpanningForest(Graph* graph, BooleanProperty *selectionProperty,
00079                                     PluginProgress *pluginProgress = NULL);
00080 
00081 /**
00082  * Select a spanning tree of a graph assuming it is connected;
00083  * i.e for all graph elements (nodes or edges) belonging to that tree
00084  * the selectionProperty associated value is true. The value is false
00085  * for the other elements
00086  */
00087 TLP_SCOPE void selectSpanningTree(Graph* graph, BooleanProperty *selection,
00088                                   PluginProgress *pluginProgress = NULL);
00089 
00090 /**
00091  * Select the minimum spanning tree (Kruskal algorithm) of a weighted graph,
00092  * i.e for all graph elements (nodes or edges) belonging to that tree
00093  * the selectionProperty associated value is true. The value is false
00094  * for the other elements
00095  */
00096 TLP_SCOPE void selectMinimumSpanningTree(Graph* graph, BooleanProperty *selectionProperty,
00097     NumericProperty *weight = NULL,
00098     PluginProgress *pluginProgress = NULL);
00099 
00100 
00101 /**
00102  * @brief Performs a breadth-first search on a graph.
00103  * @param graph The graph to traverse with a BFS.
00104  * @param root The node from whom to start the BFS. If not provided, the root
00105  * node will be assigned to a source node in the graph (node with input degree equals to 0).
00106  * If there is no source node in the graph, a random node will be picked.
00107  * @return A vector containing the nodes of the graph in the order they have been visited by the BFS.
00108  */
00109 TLP_SCOPE std::vector<node> bfs(const Graph *graph, node root = node());
00110 
00111 /**
00112  * @brief Performs a depth-first search on a graph.
00113  * @param graph The graph to traverse with a DFS.
00114  * @param root The node from whom to start the DFS. If not provided, the root
00115  * node will be assigned to a source node in the graph (node with input degree equals to 0).
00116  * If there is no source node in the graph, a random node will be picked.
00117  * @return A vector containing the nodes of the graph in the order they have been visited by the DFS.
00118  */
00119 TLP_SCOPE std::vector<node> dfs(const Graph *graph, node root = node());
00120 
00121 /*
00122  * builds a uniform quantification with the NumericProperty associated values
00123  * of the nodes of a graph
00124  */
00125 TLP_SCOPE void buildNodesUniformQuantification(const Graph* graph, const NumericProperty* prop, unsigned int k, std::map<double, int>& mapping);
00126 
00127 /*
00128  * builds a uniform quantification with the NumericProperty associated values
00129  * of the edges of a graph
00130  */
00131 TLP_SCOPE void buildEdgesUniformQuantification(const Graph* graph, const NumericProperty* prop, unsigned int k, std::map<double, int>& mapping);
00132 
00133 }
00134 #endif
00135 ///@endcond
 All Classes Files Functions Variables Enumerations Enumerator Properties