Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
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
27namespace tlp {
28
29class Graph;
30struct 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 **/
39class TLP_SCOPE BiconnectedTest {
40
41public:
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.