Tulip  4.4.0
Better Visualization Through Research
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Groups Pages
AcyclicTest.h
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux 1 and Inria Bordeaux - Sud Ouest
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_ACYCLICITY_TEST_H
21 #define TULIP_ACYCLICITY_TEST_H
22 #include <vector>
23 #include <tulip/Observable.h>
24 #include <tulip/MutableContainer.h>
25 #include <tulip/Graph.h>
26 
27 namespace tlp {
28 class BooleanProperty;
29 
30 /**
31  * @ingroup Checks
32  *
33  * @brief Stores all the added information on self loops.
34  *
35  * Self loops are removed by adding two nodes and three edges.
36  *
37  * These are stores here, along with the old self looping edge.
38  *
39  * From Wikipedia: "A directed acyclic graph (DAG), is a directed graph with no directed cycles."
40  **/
41 struct SelfLoops {
42 public:
43  SelfLoops(node n1,node n2,edge e1, edge e2,edge e3,edge old):
44  n1(n1),n2(n2),e1(e1),e2(e2),e3(e3),old(old) {
45  }
46  node n1,n2;
47  edge e1,e2,e3,old;
48 };
49 
50 /**
51  * @ingroup Checks
52  *
53  * @brief This class provides tests for acyclicity on a graph.
54  * Results are cached in a map of graphs and result.
55  * This class observes the graphs that have been tested to remove the result from this graph if it is modified.
56  * This forces the use of the singleton pattern instead of simply using static functions/members.
57  **/
58 class TLP_SCOPE AcyclicTest : private Observable {
59 public:
60 
61  /**
62  * @brief Checks whether the graph is acyclic or not.
63  * The result is cached so subsequent calls are in O(1).
64  *
65  * @param graph The graph on which to perform the acyclicity test.
66  * @return bool True if the graph is acyclic, false otherwise.
67  **/
68  static bool isAcyclic(const Graph *graph);
69 
70  /**
71  * @brief Makes the graph acyclic by removing edges.
72  *
73  * @param graph The graph to make acyclic.
74  * @param reversed The edges that were reversed during the process.
75  * @param selfLoops Sets of two nodes and three edges that were added in stead of self loops.
76  * @return void
77  **/
78  static void makeAcyclic(Graph* graph, std::vector<edge> &reversed, std::vector<tlp::SelfLoops> &selfLoops);
79 
80  /**
81  * @brief Returns whether the graph is acyclic.
82  * Collection of obstruction edges takes a bit of time, as iteration over the graph must continue even when it has been found cyclic.
83  *
84  * @param graph the graph to test for acyclicity
85  * @param obstructionEdges If not null, will be filled with edges that cause the graph to be cyclic. Defaults to 0.
86  * @return bool
87  **/
88  static bool acyclicTest(const Graph * graph, std::vector<edge> *obstructionEdges = NULL);
89 
90 private:
91  AcyclicTest();
92  /**
93  * @brief Singleton instance of this class.
94  **/
95  static AcyclicTest * instance;
96  /**
97  * @brief Stored results for graphs. When a graph is updated, its entry is removed from the hashmap.
98  **/
99  TLP_HASH_MAP<const Graph*, bool> resultsBuffer;
100 
101  //override of Observable::treatEvent to remove the cached result for a graph if it is modified.
102  virtual void treatEvent(const Event&);
103 };
104 }
105 
106 #endif //TULIP_ACYCLICITY_TEST_H