Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/AcyclicTest.h
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
 All Classes Files Functions Variables Enumerations Enumerator Properties