Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
ConnectedTest.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
20#ifndef TULIP_CONNECTEDTEST_H
21#define TULIP_CONNECTEDTEST_H
22
23#include <vector>
24
25#include <tulip/tulipconf.h>
26
27namespace tlp {
28
29class Graph;
30struct node;
31struct edge;
32
33/**
34 * @ingroup Checks
35 * @brief @brief Performs a test of connexity on the graph, and provides a function to make a graph
36 *connected.
37 * From Wikipedia: "A graph is said to be connected if every pair of vertices in the graph are
38 *connected." (i.e. there is a path between every pair of vertices).
39 **/
40class TLP_SCOPE ConnectedTest {
41public:
42 /**
43 * @brief Checks if a graph is connected (i.e. there is a path between every pair of vertices).
44 *
45 * @param graph The graph to check.
46 * @return bool True if the graph is connected, false otherwise.
47 **/
48 static bool isConnected(const Graph *const graph);
49
50 /**
51 * @brief If the graph is not connected, adds edges to make it connected.
52 *
53 * @param graph The graph to make connected.
54 * @param addedEdges The edges that were added to make it connected.
55 * @return void
56 **/
57 static void makeConnected(Graph *graph, std::vector<edge> &addedEdges);
58
59 /**
60 * @brief Gets the number of connected components in the graph.
61 *
62 * @param graph The graph in which to count the number of connected components.
63 * @return unsigned int The number of connected componments.
64 **/
65 static unsigned int numberOfConnectedComponents(const Graph *const graph);
66
67 /**
68 * @brief Computes the sets of connected components and stores the result in the components
69 *vector.
70 *
71 * @param graph The graph on which to compute connected components.
72 * @param components The components that were found. It is passed as a reference to avoid copying
73 *the data when returning.
74 * @return void
75 * @note The components parameter can be returned with c++11 thanks to move constructors without
76 *performance loss, change this function once c++11 compilers are used.
77 **/
78 static void computeConnectedComponents(const Graph *graph,
79 std::vector<std::vector<node>> &components);
80
81private:
82 /**
83 * @brief Makes the graph connected.
84 *
85 * @param graph The graph to make connected.
86 * @param toLink The nodes that need to be linked so the graph is connected.
87 * @return void
88 **/
89 static void connect(const Graph *const, std::vector<node> &toLink);
90};
91} // namespace tlp
92
93#endif
Performs a test of connexity on the graph, and provides a function to make a graph connected....
Definition: ConnectedTest.h:40
static void computeConnectedComponents(const Graph *graph, std::vector< std::vector< node > > &components)
Computes the sets of connected components and stores the result in the components vector.
static bool isConnected(const Graph *const graph)
Checks if a graph is connected (i.e. there is a path between every pair of vertices).
static void makeConnected(Graph *graph, std::vector< edge > &addedEdges)
If the graph is not connected, adds edges to make it connected.
static unsigned int numberOfConnectedComponents(const Graph *const graph)
Gets the number of connected components in the graph.