Tulip  5.7.4
Large graphs analysis and drawing
GraphTools.h
1 /*
2  *
3  * This file is part of Tulip (https://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 <list>
26 #include <set>
27 #include <stack>
28 #include <vector>
29 #include <unordered_map>
30 #include <tulip/tulipconf.h>
31 #include <tulip/Node.h>
32 #include <tulip/Edge.h>
33 #include <tulip/MutableContainer.h>
34 #include <tulip/StaticProperty.h>
35 #include <tulip/Iterator.h>
36 
37 namespace tlp {
38 class BooleanProperty;
39 class DoubleProperty;
40 class Graph;
41 class IntegerProperty;
42 class NumericProperty;
43 class PlanarConMap;
44 class PluginProgress;
45 
46 enum EDGE_TYPE { UNDIRECTED = 0, INV_DIRECTED = 1, DIRECTED = 2 };
47 #define IN_EDGE INV_DIRECTED
48 #define OUT_EDGE DIRECTED
49 #define INOUT_EDGE UNDIRECTED
50 
51 typedef Iterator<node> *(*NodesIteratorFn)(const tlp::Graph *, const tlp::node);
52 typedef Iterator<edge> *(*EdgesIteratorFn)(const tlp::Graph *, const tlp::node);
53 
54 /**
55  * return a function to get an Iterator on the adjacent nodes of a graph node
56  * according the given direction
57  */
58 TLP_SCOPE NodesIteratorFn getNodesIterator(EDGE_TYPE direction);
59 
60 /**
61  * return a function to get an Iterator on the adjacent edges of a graph node
62  * according the given direction
63  */
64 TLP_SCOPE EdgesIteratorFn getEdgesIterator(EDGE_TYPE direction);
65 
66 /**
67  * This ordering was first introduced by C. Gutwenger and P. Mutzel in \n
68  * "Grid embeddings of biconnected planar graphs", \n
69  * "Extended Abstract, Max-Planck-Institut für Informatik," \n
70  * "Saarbrücken, Germany, 1997" \n
71  * Let n be the number of nodes, the original algorithm complexity is in O(n).\n
72  * But the implementation of the canonical ordering has not been made in O(n).\n
73  */
74 TLP_SCOPE std::vector<std::vector<node>>
75 computeCanonicalOrdering(PlanarConMap *, std::vector<edge> *dummyEdges = nullptr,
76  PluginProgress *pluginProgress = nullptr);
77 /**
78  * Find all the graph centers, that version does not manage edge weight.
79  * complexity O(n * m). Only works on connected graphs.
80  */
81 TLP_SCOPE std::vector<node> computeGraphCenters(Graph *graph);
82 /**
83  * return a node that can be considered as the graph center.
84  * It is an heuristic, thus it is not absolutely sure that this
85  * node is a graph center. Only works on connected graphs.
86  */
87 TLP_SCOPE node graphCenterHeuristic(Graph *graph, PluginProgress *pluginProgress = nullptr);
88 /**
89  * return a new node connected to all previously
90  * existing nodes which had a null indegree
91  */
92 TLP_SCOPE node makeSimpleSource(Graph *graph);
93 
94 TLP_SCOPE void makeProperDag(Graph *graph, std::list<node> &addedNodes,
95  std::unordered_map<edge, edge> &replacedEdges,
96  IntegerProperty *edgeLength = nullptr);
97 
98 /**
99  * Select a spanning forest of the graph,
100  * i.e for all graph elements (nodes or edges) belonging to that forest
101  * the selectionProperty associated value is true. The value is false
102  * for the other elements
103  */
104 TLP_SCOPE void selectSpanningForest(Graph *graph, BooleanProperty *selectionProperty,
105  PluginProgress *pluginProgress = nullptr);
106 
107 /**
108  * Select a spanning tree of a graph assuming it is connected;
109  * i.e for all graph elements (nodes or edges) belonging to that tree
110  * the selectionProperty associated value is true. The value is false
111  * for the other elements
112  */
113 TLP_SCOPE void selectSpanningTree(Graph *graph, BooleanProperty *selection,
114  PluginProgress *pluginProgress = nullptr);
115 
116 /**
117  * Select the minimum spanning tree (Kruskal algorithm) of a weighted graph,
118  * i.e for all graph elements (nodes or edges) belonging to that tree
119  * the selectionProperty associated value is true. The value is false
120  * for the other elements
121  */
122 TLP_SCOPE void selectMinimumSpanningTree(Graph *graph, BooleanProperty *selectionProperty,
123  NumericProperty *weight = nullptr,
124  PluginProgress *pluginProgress = nullptr);
125 
126 /**
127  * @brief Performs a breadth-first search on a graph.
128  * @param graph The graph to traverse with a BFS.
129  * @param nodes a vector to fill with the nodes of the graph in the order they have been visited by
130  * the BFS.
131  * @param root The node from whom to start the BFS. If not provided, the root
132  * node will be assigned to a source node in the graph (node with input degree equals to 0).
133  * If there is no source node in the graph, a random node will be picked.
134  */
135 TLP_SCOPE void bfs(const Graph *graph, node root, std::vector<node> &nodes);
136 
137 /**
138  * @brief Performs a cumulative breadth-first search on every node of a graph.
139  * @param graph The graph to traverse with a BFS.
140  * @param nodes a vector to fill with the nodes of the graph in the order they have been visited by
141  * the BFS.
142  */
143 TLP_SCOPE void bfs(const Graph *graph, std::vector<node> &nodes);
144 
145 /**
146  * @brief Performs a depth-first search on a graph.
147  * @param graph The graph to traverse with a DFS.
148  * @param nodes a vector to fill with the nodes of the graph in the order they have been visited by
149  * the DFS.
150  * @param root The node from whom to start the DFS. If not provided, the root
151  * node will be assigned to a source node in the graph (node with input degree equals to 0).
152  * If there is no source node in the graph, a random node will be picked.
153  * @return A vector containing the nodes of the graph in the order they have been visited by the
154  * DFS.
155  */
156 TLP_SCOPE void dfs(const Graph *graph, node root, std::vector<node> &nodes);
157 
158 /**
159  * @brief Performs a cumulative depth-first search on every node of a graph.
160  * @param graph The graph to traverse with a DFS.
161  * @param nodes a vector to fill with the nodes of the graph in the order they have been visited by
162  * the DFS.
163  */
164 TLP_SCOPE void dfs(const Graph *graph, std::vector<node> &nodes);
165 
166 /*
167  * builds a uniform quantification with the NumericProperty associated values
168  * of the nodes of a graph
169  */
170 TLP_SCOPE void buildNodesUniformQuantification(const Graph *graph, const NumericProperty *prop,
171  unsigned int k, std::map<double, int> &mapping);
172 
173 /*
174  * builds a uniform quantification with the NumericProperty associated values
175  * of the edges of a graph
176  */
177 TLP_SCOPE void buildEdgesUniformQuantification(const Graph *graph, const NumericProperty *prop,
178  unsigned int k, std::map<double, int> &mapping);
179 
180 /**
181  * @brief Extends selection to have a graph (no dangling edge)
182  * @param graph The graph to compute on.
183  * @param selection The Boolean property to consider. The selection will be extend using this
184  * property.
185  * @return The number of element added to the selection property.
186  */
187 TLP_SCOPE unsigned makeSelectionGraph(const Graph *graph, BooleanProperty *selection,
188  bool *test = nullptr);
189 
190 /**
191  * @enum This Enum describes the possible types of path to select between a source and target nodes
192  * It is used in tlp::selectShortestPaths. Reversed means the same than Directed from target node to
193  *source node.
194  **/
195 enum ShortestPathType {
196  OnePath = 0,
197  OneDirectedPath = 1,
198  OneReversedPath = 2,
199  AllPaths = 3,
200  AllDirectedPaths = 4,
201  AllReversedPaths = 5
202 };
203 
204 /**
205  * @brief select the shortest paths between two nodes
206  * @param graph The graph to compute on.
207  * @param src The source node of the paths
208  * @param tgt The target node of the paths
209  * @param pathType The type of path to consider (chosen among tlp::ShortestPathType enumeration
210  * values)
211  * @param weights A Double property giving the edges weight if weighted paths have to be considered.
212  * Can be set to null to select unweighted paths.
213  * @param selection The Boolean property to consider as selection for which the values corresponding
214  * to the nodes/edges owning to the shortests path(s) will be set to True.
215  * @return true if a path exists between the src and tgt nodes; false if not.
216  */
217 TLP_SCOPE bool selectShortestPaths(const Graph *const graph, node src, node tgt,
218  ShortestPathType pathType, const DoubleProperty *const weights,
219  BooleanProperty *selection);
220 
221 /*
222  * mark as reachable (set the corresponding value in "reachables" map to true),
223  * all the nodes, according to direction,
224  * at distance less or equal to maxDistance of startNode.
225  * If direction is set to UNDIRECTED use undirected graph,
226  * DIRECTED use directed graph
227  * and INV_DIRECTED use reverse directed graph (ie. all edges are reversed)
228  */
229 TLP_SCOPE void markReachableNodes(const Graph *graph, const node startNode,
230  std::unordered_map<node, bool> &reachables,
231  unsigned int maxDistance, EDGE_TYPE direction = UNDIRECTED);
232 
233 TLP_SCOPE void computeDijkstra(const Graph *const graph, node src,
234  const EdgeStaticProperty<double> &weights,
235  NodeStaticProperty<double> &nodeDistance, EDGE_TYPE direction,
236  std::unordered_map<node, std::list<node>> &ancestors,
237  std::stack<node> *queueNodes = nullptr,
238  MutableContainer<int> *numberOfPaths = nullptr);
239 } // namespace tlp
240 #endif
241 ///@endcond
The node struct represents a node in a Graph object.
Definition: Node.h:40