Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
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
37namespace tlp {
38class BooleanProperty;
39class DoubleProperty;
40class Graph;
41class IntegerProperty;
42class NumericProperty;
43class PlanarConMap;
44class PluginProgress;
45
46enum 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
51typedef Iterator<node> *(*NodesIteratorFn)(const tlp::Graph *, const tlp::node);
52typedef 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 */
58TLP_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 */
64TLP_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 */
74TLP_SCOPE std::vector<std::vector<node>>
75computeCanonicalOrdering(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 */
81TLP_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 */
87TLP_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 */
92TLP_SCOPE node makeSimpleSource(Graph *graph);
93
94TLP_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 */
104TLP_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 */
113TLP_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 */
122TLP_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 */
135TLP_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 */
143TLP_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 */
156TLP_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 */
164TLP_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 */
170TLP_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 */
177TLP_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 */
187TLP_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 **/
195enum 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 */
217TLP_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 */
229TLP_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
233TLP_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