Tulip  5.7.4
Large graphs analysis and drawing
BiconnectedTest.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_BICONNEX_H
21 #define TULIP_BICONNEX_H
22 
23 #include <vector>
24 
25 #include <tulip/tulipconf.h>
26 
27 namespace tlp {
28 
29 class Graph;
30 struct edge;
31 
32 /**
33  * @ingroup Checks
34  * @brief Performs a test of biconnexity on the graph, and provides a function to make a graph
35  *biconnected.
36  * From Wikipedia: "A biconnected graph is connected and nonseparable, meaning that if any vertex
37  *were to be removed, the graph will remain connected."
38  **/
39 class TLP_SCOPE BiconnectedTest {
40 
41 public:
42  /**
43  * @brief Checks whether the graph is biconnected (i.e. removing one edge does not disconnect the
44  *graph, at least two must be removed).
45  *
46  * @param graph The graph to check for biconnectivity.
47  * @return bool True if the graph is biconnected, false otherwise.
48  **/
49  static bool isBiconnected(const Graph *graph);
50 
51  /**
52  * If the graph is not biconnected, adds edges in order to make the graph
53  * biconnected. The new edges are added in addedEdges.
54  */
55  /**
56  * @brief Adds edges to make the graph biconnected.
57  *
58  * @param graph The graph to make biconnected.
59  * @param addedEdges The edges that were added in the process.
60  * @return void
61  **/
62  static void makeBiconnected(Graph *graph, std::vector<edge> &addedEdges);
63 };
64 } // namespace tlp
65 
66 #endif
Performs a test of biconnexity on the graph, and provides a function to make a graph biconnected....
static bool isBiconnected(const Graph *graph)
Checks whether the graph is biconnected (i.e. removing one edge does not disconnect the graph,...
static void makeBiconnected(Graph *graph, std::vector< edge > &addedEdges)
Adds edges to make the graph biconnected.