Tulip  5.7.4
Large graphs analysis and drawing
AcyclicTest.h
1 /*
2  *
3  * This file is part of Tulip (https://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 
24 #include <tulip/tulipconf.h>
25 #include <tulip/Node.h>
26 #include <tulip/Edge.h>
27 
28 namespace tlp {
29 
30 class Graph;
31 
32 /**
33  * @ingroup Checks
34  *
35  * @brief Stores all the added information on self loops.
36  *
37  * Self loops are removed by adding two nodes and three edges.
38  *
39  * These are stores here, along with the old self looping edge.
40  *
41  * From Wikipedia: "A directed acyclic graph (DAG), is a directed graph with no directed cycles."
42  **/
43 struct SelfLoops {
44 public:
45  SelfLoops(node n1, node n2, edge e1, edge e2, edge e3, edge old)
46  : n1(n1), n2(n2), e1(e1), e2(e2), e3(e3), old(old) {}
47  node n1, n2;
48  edge e1, e2, e3, old;
49 };
50 
51 /**
52  * @ingroup Checks
53  *
54  * @brief This class provides tests for acyclicity on a graph.
55  * Results are cached in a map of graphs and result.
56  * This class observes the graphs that have been tested to remove the result from this graph if it
57  *is modified.
58  * This forces the use of the singleton pattern instead of simply using static functions/members.
59  **/
60 class TLP_SCOPE AcyclicTest {
61 public:
62  /**
63  * @brief Checks whether the graph is acyclic or not.
64  * The result is cached so subsequent calls are in O(1).
65  *
66  * @param graph The graph on which to perform the acyclicity test.
67  * @return bool True if the graph is acyclic, false otherwise.
68  **/
69  static bool isAcyclic(const Graph *graph);
70 
71  /**
72  * @brief Makes the graph acyclic by removing edges.
73  *
74  * @param graph The graph to make acyclic.
75  * @param reversed The edges that were reversed during the process.
76  * @param selfLoops Sets of two nodes and three edges that were added instead of self loops.
77  * @return void
78  **/
79  static void makeAcyclic(Graph *graph, std::vector<edge> &reversed,
80  std::vector<tlp::SelfLoops> &selfLoops);
81 
82  /**
83  * @brief Returns whether the graph is acyclic.
84  * Collection of obstruction edges takes a bit of time, as iteration over the graph must continue
85  *even when it has been found cyclic.
86  *
87  * @param graph the graph to test for acyclicity
88  * @param obstructionEdges If not null, will be filled with edges that cause the graph to be
89  *cyclic. Defaults to 0.
90  * @return bool
91  **/
92  static bool acyclicTest(const Graph *graph, std::vector<edge> *obstructionEdges = nullptr);
93 };
94 } // namespace tlp
95 
96 #endif // TULIP_ACYCLICITY_TEST_H
This class provides tests for acyclicity on a graph. Results are cached in a map of graphs and result...
Definition: AcyclicTest.h:60
static void makeAcyclic(Graph *graph, std::vector< edge > &reversed, std::vector< tlp::SelfLoops > &selfLoops)
Makes the graph acyclic by removing edges.
static bool acyclicTest(const Graph *graph, std::vector< edge > *obstructionEdges=nullptr)
Returns whether the graph is acyclic. Collection of obstruction edges takes a bit of time,...
static bool isAcyclic(const Graph *graph)
Checks whether the graph is acyclic or not. The result is cached so subsequent calls are in O(1).
Stores all the added information on self loops.
Definition: AcyclicTest.h:43
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