Tulip  4.3.0
Better Visualization Through Research
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Groups Pages
GraphTools.h
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux 1 and Inria Bordeaux - Sud Ouest
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 ///@cond DOXYGEN_HIDDEN
20 
21 #ifndef _TLPGRAPHTOOLS_H
22 #define _TLPGRAPHTOOLS_H
23 
24 #include <set>
25 #include <list>
26 #include <tulip/tuliphash.h>
27 #include <tulip/Node.h>
28 #include <tulip/Edge.h>
29 
30 #include <tulip/PlanarConMap.h>
31 
32 namespace tlp {
33 
34 class BooleanProperty;
35 class DoubleProperty;
36 class IntegerProperty;
37 class NumericProperty;
38 
39 /**
40  * This ordering was first introduced by C. Gutwenger and P. Mutzel in \n
41  * "Grid embeddings of biconnected planar graphs", \n
42  * "Extended Abstract, Max-Planck-Institut für Informatik," \n
43  * "Saarbrücken, Germany, 1997" \n
44  * Let n be the number of nodes, the original algorithm complexity is in O(n).\n
45  * But the implementation of the canonical ordering has not been made in O(n).\n
46  */
47 TLP_SCOPE std::vector<std::vector<node> > computeCanonicalOrdering(PlanarConMap *,
48  std::vector<edge> *dummyEdges = NULL,
49  PluginProgress *pluginProgress = NULL);
50 /**
51  * Find all the graph centers, that version does not manage edge weight.
52  * complexity O(n * m). Only works on connected graphs.
53  */
54 TLP_SCOPE std::vector<node> computeGraphCenters(Graph * graph);
55 /**
56  * return a node that can be considered as the graph center.
57  * It is an heuristic, thus it is not absolutely sure that this
58  * node is a graph center. Only works on connected graphs.
59  */
60 TLP_SCOPE node graphCenterHeuristic(Graph * graph,
61  PluginProgress *pluginProgress = NULL);
62 /**
63  * return a new node connected to all previously
64  * existing nodes which had a null indegree
65  */
66 TLP_SCOPE node makeSimpleSource(Graph* graph);
67 
68 TLP_SCOPE void makeProperDag(Graph* graph,std::list<node> &addedNodes,
69  TLP_HASH_MAP<edge,edge> &replacedEdges,
70  IntegerProperty* edgeLength = NULL);
71 
72 /**
73  * Select a spanning forest of the graph,
74  * i.e for all graph elements (nodes or edges) belonging to that forest
75  * the selectionProperty associated value is true. The value is false
76  * for the other elements
77  */
78 TLP_SCOPE void selectSpanningForest(Graph* graph, BooleanProperty *selectionProperty,
79  PluginProgress *pluginProgress = NULL);
80 
81 /**
82  * Select a spanning tree of a graph assuming it is connected;
83  * i.e for all graph elements (nodes or edges) belonging to that tree
84  * the selectionProperty associated value is true. The value is false
85  * for the other elements
86  */
87 TLP_SCOPE void selectSpanningTree(Graph* graph, BooleanProperty *selection,
88  PluginProgress *pluginProgress = NULL);
89 
90 /**
91  * Select the minimum spanning tree (Kruskal algorithm) of a weighted graph,
92  * i.e for all graph elements (nodes or edges) belonging to that tree
93  * the selectionProperty associated value is true. The value is false
94  * for the other elements
95  */
96 TLP_SCOPE void selectMinimumSpanningTree(Graph* graph, BooleanProperty *selectionProperty,
97  NumericProperty *weight = NULL,
98  PluginProgress *pluginProgress = NULL);
99 
100 
101 /**
102  * @brief Performs a breadth-first search on a graph.
103  * @param graph The graph to traverse with a BFS.
104  * @param root The node from whom to start the BFS. If not provided, the root
105  * node will be assigned to a source node in the graph (node with input degree equals to 0).
106  * If there is no source node in the graph, a random node will be picked.
107  * @return A vector containing the nodes of the graph in the order they have been visited by the BFS.
108  */
109 TLP_SCOPE std::vector<node> bfs(const Graph *graph, node root = node());
110 
111 /**
112  * @brief Performs a depth-first search on a graph.
113  * @param graph The graph to traverse with a DFS.
114  * @param root The node from whom to start the DFS. If not provided, the root
115  * node will be assigned to a source node in the graph (node with input degree equals to 0).
116  * If there is no source node in the graph, a random node will be picked.
117  * @return A vector containing the nodes of the graph in the order they have been visited by the DFS.
118  */
119 TLP_SCOPE std::vector<node> dfs(const Graph *graph, node root = node());
120 
121 /*
122  * builds a uniform quantification with the NumericProperty associated values
123  * of the nodes of a graph
124  */
125 TLP_SCOPE void buildNodesUniformQuantification(const Graph* graph, const NumericProperty* prop, unsigned int k, std::map<double, int>& mapping);
126 
127 /*
128  * builds a uniform quantification with the NumericProperty associated values
129  * of the edges of a graph
130  */
131 TLP_SCOPE void buildEdgesUniformQuantification(const Graph* graph, const NumericProperty* prop, unsigned int k, std::map<double, int>& mapping);
132 
133 }
134 #endif
135 ///@endcond