/usr/include/tulip/BiconnectedTest.h is in libtulip-dev 4.4.0dfsg2-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 | /*
*
* This file is part of Tulip (www.tulip-software.org)
*
* Authors: David Auber and the Tulip development Team
* from LaBRI, University of Bordeaux 1 and Inria Bordeaux - Sud Ouest
*
* Tulip is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License
* as published by the Free Software Foundation, either version 3
* of the License, or (at your option) any later version.
*
* Tulip is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU General Public License for more details.
*
*/
#ifndef TULIP_BICONNEX_H
#define TULIP_BICONNEX_H
#include <tulip/MutableContainer.h>
#include <tulip/Observable.h>
#include <tulip/Graph.h>
namespace tlp {
/**
* @ingroup Checks
* @brief Performs a test of biconnexity on the graph, and provides a function to make a graph biconnected.
* From Wikipedia: "A biconnected graph is connected and nonseparable, meaning that if any vertex were to be removed, the graph will remain connected."
**/
class TLP_SCOPE BiconnectedTest : private Observable {
public:
/**
* @brief Checks whether the graph is biconnected (i.e. removing one edge does not disconnect the graph, at least two must be removed).
*
* @param graph The graph to check for biconnectivity.
* @return bool True if the graph is biconnected, false otherwise.
**/
static bool isBiconnected(const Graph *graph);
/**
* If the graph is not biconnected, adds edges in order to make the graph
* biconnected. The new edges are added in addedEdges.
*/
/**
* @brief Adds edges to make the graph biconnected.
*
* @param graph The graph to make biconnected.
* @param addedEdges The edges that were added in the process.
* @return void
**/
static void makeBiconnected(Graph *graph, std::vector<edge>& addedEdges);
private:
BiconnectedTest();
/**
* @brief Makes the graph biconnected.
* Starts by making the graph connected (using ConnectgedTest::makeConnected()),
* then calls another function that will visit the graph using a recursive dfs algorithm and make it biconnected.
*
* @param graph The graph to make biconnected.
* @param addedEdges The edges that were added to make it biconnected.
* @return void
**/
void connect(Graph * graph, std::vector<edge>& addedEdges);
/**
* @brief check if the graph is biconnected.
*
* @param graph the graph to check.
* @return bool true if the graph is biconnected, false otherwise.
**/
bool compute(const Graph * graph);
//override of Observable::treatEvent to remove the cached result for a graph if it is modified.
virtual void treatEvent(const Event&);
/**
* @brief Singleton instance of this class.
**/
static BiconnectedTest * instance;
/**
* @brief Stored results for graphs. When a graph is updated, its entry is removed from the hashmap.
**/
TLP_HASH_MAP<const Graph*,bool> resultsBuffer;
};
}
#endif
|