Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
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
28namespace tlp {
29
30class 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 **/
43struct SelfLoops {
44public:
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 **/
60class TLP_SCOPE AcyclicTest {
61public:
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