Tulip  5.0.0
Large graphs analysis and drawing
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
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 <map>
25 #include <set>
26 #include <list>
27 #include <vector>
28 #include <tulip/tulipconf.h>
29 #include <tulip/tuliphash.h>
30 #include <tulip/Node.h>
31 #include <tulip/Edge.h>
32 
33 namespace tlp {
34 class BooleanProperty;
35 class DoubleProperty;
36 class Graph;
37 class IntegerProperty;
38 class NumericProperty;
39 class PlanarConMap;
40 class PluginProgress;
41 
42 /**
43  * This ordering was first introduced by C. Gutwenger and P. Mutzel in \n
44  * "Grid embeddings of biconnected planar graphs", \n
45  * "Extended Abstract, Max-Planck-Institut für Informatik," \n
46  * "Saarbrücken, Germany, 1997" \n
47  * Let n be the number of nodes, the original algorithm complexity is in O(n).\n
48  * But the implementation of the canonical ordering has not been made in O(n).\n
49  */
50 TLP_SCOPE std::vector<std::vector<node> > computeCanonicalOrdering(PlanarConMap *,
51  std::vector<edge> *dummyEdges = NULL,
52  PluginProgress *pluginProgress = NULL);
53 /**
54  * Find all the graph centers, that version does not manage edge weight.
55  * complexity O(n * m). Only works on connected graphs.
56  */
57 TLP_SCOPE std::vector<node> computeGraphCenters(Graph * graph);
58 /**
59  * return a node that can be considered as the graph center.
60  * It is an heuristic, thus it is not absolutely sure that this
61  * node is a graph center. Only works on connected graphs.
62  */
63 TLP_SCOPE node graphCenterHeuristic(Graph * graph,
64  PluginProgress *pluginProgress = NULL);
65 /**
66  * return a new node connected to all previously
67  * existing nodes which had a null indegree
68  */
69 TLP_SCOPE node makeSimpleSource(Graph* graph);
70 
71 TLP_SCOPE void makeProperDag(Graph* graph,std::list<node> &addedNodes,
72  TLP_HASH_MAP<edge,edge> &replacedEdges,
73  IntegerProperty* edgeLength = NULL);
74 
75 /**
76  * Select a spanning forest of the graph,
77  * i.e for all graph elements (nodes or edges) belonging to that forest
78  * the selectionProperty associated value is true. The value is false
79  * for the other elements
80  */
81 TLP_SCOPE void selectSpanningForest(Graph* graph, BooleanProperty *selectionProperty,
82  PluginProgress *pluginProgress = NULL);
83 
84 /**
85  * Select a spanning tree of a graph assuming it is connected;
86  * i.e for all graph elements (nodes or edges) belonging to that tree
87  * the selectionProperty associated value is true. The value is false
88  * for the other elements
89  */
90 TLP_SCOPE void selectSpanningTree(Graph* graph, BooleanProperty *selection,
91  PluginProgress *pluginProgress = NULL);
92 
93 /**
94  * Select the minimum spanning tree (Kruskal algorithm) of a weighted graph,
95  * i.e for all graph elements (nodes or edges) belonging to that tree
96  * the selectionProperty associated value is true. The value is false
97  * for the other elements
98  */
99 TLP_SCOPE void selectMinimumSpanningTree(Graph* graph,
100  BooleanProperty *selectionProperty,
101  NumericProperty *weight = NULL,
102  PluginProgress *pluginProgress = NULL);
103 
104 /**
105  * @brief Performs a breadth-first search on a graph.
106  * @param graph The graph to traverse with a BFS.
107  * @param nodes a vector to fill with the nodes of the graph in the order they have been visited by the BFS.
108  * @param root The node from whom to start the BFS. If not provided, the root
109  * node will be assigned to a source node in the graph (node with input degree equals to 0).
110  * If there is no source node in the graph, a random node will be picked.
111  */
112 TLP_SCOPE void bfs(const Graph *graph, node root, std::vector<node>& nodes);
113 
114 /**
115  * @brief Performs a cumulative breadth-first search on every node of a graph.
116  * @param graph The graph to traverse with a BFS.
117  * @param nodes a vector to fill with the nodes of the graph in the order they have been visited by the BFS.
118  */
119 TLP_SCOPE void bfs(const Graph *graph, std::vector<node>& nodes);
120 
121 /**
122 * @brief deprecated function,
123 * use bfs(const Graph*, node, std::vector<node>&) instead
124 */
125 TLP_SCOPE _DEPRECATED std::vector<node> bfs(const Graph *graph,
126  node root = node());
127 
128 /**
129  * @brief Performs a depth-first search on a graph.
130  * @param graph The graph to traverse with a DFS.
131  * @param nodes a vector to fill with the nodes of the graph in the order they have been visited by the DFS.
132  * @param root The node from whom to start the DFS. If not provided, the root
133  * node will be assigned to a source node in the graph (node with input degree equals to 0).
134  * If there is no source node in the graph, a random node will be picked.
135  * @return A vector containing the nodes of the graph in the order they have been visited by the DFS.
136  */
137 TLP_SCOPE void dfs(const Graph *graph, node root, std::vector<node>& nodes);
138 
139 /**
140  * @brief Performs a cumulative depth-first search on every node of a graph.
141  * @param graph The graph to traverse with a DFS.
142  * @param nodes a vector to fill with the nodes of the graph in the order they have been visited by the DFS.
143  */
144 TLP_SCOPE void dfs(const Graph *graph, std::vector<node>& nodes);
145 
146 /**
147  * @brief deprecated function,
148  * use dfs(const Graph*, node, std::vector<node>&) instead
149  */
150 TLP_SCOPE _DEPRECATED std::vector<node> dfs(const Graph *graph,
151  node root = node());
152 
153 /*
154  * builds a uniform quantification with the NumericProperty associated values
155  * of the nodes of a graph
156  */
157 TLP_SCOPE void buildNodesUniformQuantification(const Graph* graph, const NumericProperty* prop, unsigned int k, std::map<double, int>& mapping);
158 
159 /*
160  * builds a uniform quantification with the NumericProperty associated values
161  * of the edges of a graph
162  */
163 TLP_SCOPE void buildEdgesUniformQuantification(const Graph* graph, const NumericProperty* prop, unsigned int k, std::map<double, int>& mapping);
164 
165 /**
166  * @brief Extends selection to have a graph (no dangling edge)
167  * @param graph The graph to compute on.
168  * @param selection The Boolean property to consider. The selection will be extend using this property.
169  * @return The number of element added to the selection property.
170  */
171 TLP_SCOPE unsigned makeSelectionGraph(const Graph* graph, BooleanProperty* selection, bool* test=NULL);
172 }
173 #endif
174 ///@endcond