Tulip
4.6.0
Better Visualization Through Research
|
00001 /* 00002 * 00003 * This file is part of Tulip (www.tulip-software.org) 00004 * 00005 * Authors: David Auber and the Tulip development Team 00006 * from LaBRI, University of Bordeaux 00007 * 00008 * Tulip is free software; you can redistribute it and/or modify 00009 * it under the terms of the GNU Lesser General Public License 00010 * as published by the Free Software Foundation, either version 3 00011 * of the License, or (at your option) any later version. 00012 * 00013 * Tulip is distributed in the hope that it will be useful, 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00016 * See the GNU General Public License for more details. 00017 * 00018 */ 00019 00020 #ifndef TULIP_ACYCLICITY_TEST_H 00021 #define TULIP_ACYCLICITY_TEST_H 00022 #include <vector> 00023 #include <tulip/Observable.h> 00024 #include <tulip/MutableContainer.h> 00025 #include <tulip/Graph.h> 00026 00027 namespace tlp { 00028 class BooleanProperty; 00029 00030 /** 00031 * @ingroup Checks 00032 * 00033 * @brief Stores all the added information on self loops. 00034 * 00035 * Self loops are removed by adding two nodes and three edges. 00036 * 00037 * These are stores here, along with the old self looping edge. 00038 * 00039 * From Wikipedia: "A directed acyclic graph (DAG), is a directed graph with no directed cycles." 00040 **/ 00041 struct SelfLoops { 00042 public: 00043 SelfLoops(node n1,node n2,edge e1, edge e2,edge e3,edge old): 00044 n1(n1),n2(n2),e1(e1),e2(e2),e3(e3),old(old) { 00045 } 00046 node n1,n2; 00047 edge e1,e2,e3,old; 00048 }; 00049 00050 /** 00051 * @ingroup Checks 00052 * 00053 * @brief This class provides tests for acyclicity on a graph. 00054 * Results are cached in a map of graphs and result. 00055 * This class observes the graphs that have been tested to remove the result from this graph if it is modified. 00056 * This forces the use of the singleton pattern instead of simply using static functions/members. 00057 **/ 00058 class TLP_SCOPE AcyclicTest : private Observable { 00059 public: 00060 00061 /** 00062 * @brief Checks whether the graph is acyclic or not. 00063 * The result is cached so subsequent calls are in O(1). 00064 * 00065 * @param graph The graph on which to perform the acyclicity test. 00066 * @return bool True if the graph is acyclic, false otherwise. 00067 **/ 00068 static bool isAcyclic(const Graph *graph); 00069 00070 /** 00071 * @brief Makes the graph acyclic by removing edges. 00072 * 00073 * @param graph The graph to make acyclic. 00074 * @param reversed The edges that were reversed during the process. 00075 * @param selfLoops Sets of two nodes and three edges that were added in stead of self loops. 00076 * @return void 00077 **/ 00078 static void makeAcyclic(Graph* graph, std::vector<edge> &reversed, std::vector<tlp::SelfLoops> &selfLoops); 00079 00080 /** 00081 * @brief Returns whether the graph is acyclic. 00082 * Collection of obstruction edges takes a bit of time, as iteration over the graph must continue even when it has been found cyclic. 00083 * 00084 * @param graph the graph to test for acyclicity 00085 * @param obstructionEdges If not null, will be filled with edges that cause the graph to be cyclic. Defaults to 0. 00086 * @return bool 00087 **/ 00088 static bool acyclicTest(const Graph * graph, std::vector<edge> *obstructionEdges = NULL); 00089 00090 private: 00091 AcyclicTest(); 00092 /** 00093 * @brief Singleton instance of this class. 00094 **/ 00095 static AcyclicTest * instance; 00096 /** 00097 * @brief Stored results for graphs. When a graph is updated, its entry is removed from the hashmap. 00098 **/ 00099 TLP_HASH_MAP<const Graph*, bool> resultsBuffer; 00100 00101 //override of Observable::treatEvent to remove the cached result for a graph if it is modified. 00102 virtual void treatEvent(const Event&); 00103 }; 00104 } 00105 00106 #endif //TULIP_ACYCLICITY_TEST_H