Tulip  5.2.0
Large graphs analysis and drawing
AcyclicTest.h
1 /*
2  *
3  * This file is part of Tulip (http://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_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  node n1, n2;
46  edge e1, e2, e3, old;
47 };
48 
49 /**
50  * @ingroup Checks
51  *
52  * @brief This class provides tests for acyclicity on a graph.
53  * Results are cached in a map of graphs and result.
54  * This class observes the graphs that have been tested to remove the result from this graph if it
55  *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  * @brief Checks whether the graph is acyclic or not.
62  * The result is cached so subsequent calls are in O(1).
63  *
64  * @param graph The graph on which to perform the acyclicity test.
65  * @return bool True if the graph is acyclic, false otherwise.
66  **/
67  static bool isAcyclic(const Graph *graph);
68 
69  /**
70  * @brief Makes the graph acyclic by removing edges.
71  *
72  * @param graph The graph to make acyclic.
73  * @param reversed The edges that were reversed during the process.
74  * @param selfLoops Sets of two nodes and three edges that were added instead of self loops.
75  * @return void
76  **/
77  static void makeAcyclic(Graph *graph, std::vector<edge> &reversed,
78  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
83  *even when it has been found cyclic.
84  *
85  * @param graph the graph to test for acyclicity
86  * @param obstructionEdges If not null, will be filled with edges that cause the graph to be
87  *cyclic. Defaults to 0.
88  * @return bool
89  **/
90  static bool acyclicTest(const Graph *graph, std::vector<edge> *obstructionEdges = nullptr);
91 
92 private:
93  AcyclicTest();
94  /**
95  * @brief Singleton instance of this class.
96  **/
97  static AcyclicTest *instance;
98  /**
99  * @brief Stored results for graphs. When a graph is updated, its entry is removed from the
100  *hashmap.
101  **/
102  TLP_HASH_MAP<const Graph *, bool> resultsBuffer;
103 
104  // override of Observable::treatEvent to remove the cached result for a graph if it is modified.
105  void treatEvent(const Event &) override;
106 };
107 }
108 
109 #endif // TULIP_ACYCLICITY_TEST_H
Stores all the added information on self loops.
Definition: AcyclicTest.h:41
The edge struct represents an edge in a Graph object.
Definition: Edge.h:40
The node struct represents a node in a Graph object.
Definition: Node.h:40
Event is the base class for all events used in the Observation mechanism.
Definition: Observable.h:51
This class provides tests for acyclicity on a graph. Results are cached in a map of graphs and result...
Definition: AcyclicTest.h:58
The Observable class is the base of Tulip&#39;s observation system.
Definition: Observable.h:141