Tulip  5.3.0
Large graphs analysis and drawing
GraphTools.h
1 /*
2  *
3  * This file is part of Tulip (http://tulip.labri.fr)
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>>
51 computeCanonicalOrdering(PlanarConMap *, std::vector<edge> *dummyEdges = nullptr,
52  PluginProgress *pluginProgress = nullptr);
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, PluginProgress *pluginProgress = nullptr);
64 /**
65  * return a new node connected to all previously
66  * existing nodes which had a null indegree
67  */
68 TLP_SCOPE node makeSimpleSource(Graph *graph);
69 
70 TLP_SCOPE void makeProperDag(Graph *graph, std::list<node> &addedNodes,
71  TLP_HASH_MAP<edge, edge> &replacedEdges,
72  IntegerProperty *edgeLength = nullptr);
73 
74 /**
75  * Select a spanning forest of the graph,
76  * i.e for all graph elements (nodes or edges) belonging to that forest
77  * the selectionProperty associated value is true. The value is false
78  * for the other elements
79  */
80 TLP_SCOPE void selectSpanningForest(Graph *graph, BooleanProperty *selectionProperty,
81  PluginProgress *pluginProgress = nullptr);
82 
83 /**
84  * Select a spanning tree of a graph assuming it is connected;
85  * i.e for all graph elements (nodes or edges) belonging to that tree
86  * the selectionProperty associated value is true. The value is false
87  * for the other elements
88  */
89 TLP_SCOPE void selectSpanningTree(Graph *graph, BooleanProperty *selection,
90  PluginProgress *pluginProgress = nullptr);
91 
92 /**
93  * Select the minimum spanning tree (Kruskal algorithm) of a weighted graph,
94  * i.e for all graph elements (nodes or edges) belonging to that tree
95  * the selectionProperty associated value is true. The value is false
96  * for the other elements
97  */
98 TLP_SCOPE void selectMinimumSpanningTree(Graph *graph, BooleanProperty *selectionProperty,
99  NumericProperty *weight = nullptr,
100  PluginProgress *pluginProgress = nullptr);
101 
102 /**
103  * @brief Performs a breadth-first search on a graph.
104  * @param graph The graph to traverse with a BFS.
105  * @param nodes a vector to fill with the nodes of the graph in the order they have been visited by
106  * the BFS.
107  * @param root The node from whom to start the BFS. If not provided, the root
108  * node will be assigned to a source node in the graph (node with input degree equals to 0).
109  * If there is no source node in the graph, a random node will be picked.
110  */
111 TLP_SCOPE void bfs(const Graph *graph, node root, std::vector<node> &nodes);
112 
113 /**
114  * @brief Performs a cumulative breadth-first search on every node of a graph.
115  * @param graph The graph to traverse with a BFS.
116  * @param nodes a vector to fill with the nodes of the graph in the order they have been visited by
117  * 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, node root = node());
126 
127 /**
128  * @brief Performs a depth-first search on a graph.
129  * @param graph The graph to traverse with a DFS.
130  * @param nodes a vector to fill with the nodes of the graph in the order they have been visited by
131  * 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
136  * DFS.
137  */
138 TLP_SCOPE void dfs(const Graph *graph, node root, std::vector<node> &nodes);
139 
140 /**
141  * @brief Performs a cumulative depth-first search on every node of a graph.
142  * @param graph The graph to traverse with a DFS.
143  * @param nodes a vector to fill with the nodes of the graph in the order they have been visited by
144  * the DFS.
145  */
146 TLP_SCOPE void dfs(const Graph *graph, std::vector<node> &nodes);
147 
148 /**
149  * @brief deprecated function,
150  * use dfs(const Graph*, node, std::vector<node>&) instead
151  */
152 TLP_SCOPE _DEPRECATED std::vector<node> dfs(const Graph *graph, node root = node());
153 
154 /*
155  * builds a uniform quantification with the NumericProperty associated values
156  * of the nodes of a graph
157  */
158 TLP_SCOPE void buildNodesUniformQuantification(const Graph *graph, const NumericProperty *prop,
159  unsigned int k, std::map<double, int> &mapping);
160 
161 /*
162  * builds a uniform quantification with the NumericProperty associated values
163  * of the edges of a graph
164  */
165 TLP_SCOPE void buildEdgesUniformQuantification(const Graph *graph, const NumericProperty *prop,
166  unsigned int k, std::map<double, int> &mapping);
167 
168 /**
169  * @brief Extends selection to have a graph (no dangling edge)
170  * @param graph The graph to compute on.
171  * @param selection The Boolean property to consider. The selection will be extend using this
172  * property.
173  * @return The number of element added to the selection property.
174  */
175 TLP_SCOPE unsigned makeSelectionGraph(const Graph *graph, BooleanProperty *selection,
176  bool *test = nullptr);
177 
178 /**
179  * @enum This Enum describes the possible types of path to select between a source and target nodes
180  * It is used in tlp::selectShortestPaths. Reversed means the same than Directed from target node to
181  *source node.
182  **/
183 enum ShortestPathType {
184  OnePath = 0,
185  OneDirectedPath = 1,
186  OneReversedPath = 2,
187  AllPaths = 3,
188  AllDirectedPaths = 4,
189  AllReversedPaths = 5
190 };
191 
192 /**
193  * @brief select the shortest paths between two nodes
194  * @param graph The graph to compute on.
195  * @param src The source node of the paths
196  * @param tgt The target node of the paths
197  * @param pathType The type of path to consider (choosen among tlp::ShortestPathType enumation
198  * values)
199  * @param weights A Double property giving the edges weight if weighted paths have to be considered.
200  * Can be set to null to select unweighted paths.
201  * @param selection The Boolean property to consider as selection.
202  * @return true if a path exists between the src and tgt nodes; false if not.
203  */
204 TLP_SCOPE bool selectShortestPaths(const Graph *const graph, node src, node tgt,
205  ShortestPathType pathType, const DoubleProperty *const weights,
206  BooleanProperty *selection);
207 
208 } // namespace tlp
209 #endif
210 ///@endcond