![]() |
Tulip
4.6.0
Better Visualization Through Research
|
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