Tulip  5.7.4
Large graphs analysis and drawing
SimpleTest.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_SIMPLETEST_H
21 #define TULIP_SIMPLETEST_H
22 
23 #include <vector>
24 
25 #include <tulip/tulipconf.h>
26 
27 namespace tlp {
28 
29 class Graph;
30 struct edge;
31 
32 /**
33  * @ingroup Checks
34  * @brief Performs test to check if a graph is Simple.
35  * An undirected graph is simple if it has no loops and no more than one
36  * edge between any unordered pair of vertices.
37  * A directed graph is simple if has no loops and no more than one
38  * edge between any ordered pair of vertices.
39  **/
40 class TLP_SCOPE SimpleTest {
41 public:
42  /**
43  * @brief Checks if the graph is simple (i.e. it contains no self loops or parallel edges).
44  *
45  * @param graph The graph to check.
46  * @param directed Whether the graph shall be considered directed or not.
47  * @return bool True if the graph is simple, false otherwise.
48  **/
49  static bool isSimple(const Graph *graph, const bool directed = false);
50  /**
51  * @brief Checks if the graph has self loop edges.
52  *
53  * @param graph The graph to check.
54  * @return bool True if the graph has loops, false otherwise.
55  **/
56  static bool hasLoops(const Graph *graph);
57  /**
58  * @brief Checks if the graph has parallel edges.
59  *
60  * @param graph The graph to check.
61  * @param directed Whether the graph shall be considered directed or not.
62  * @return bool True if the graph has parallel edges, false otherwise.
63  **/
64  static bool hasParallelEdges(const Graph *graph, const bool directed = false);
65 
66  /**
67  * Makes the graph simple by removing self loops and parallel edges if any.
68  * The removed edges are stored in the removed vector.
69  */
70  /**
71  * @brief Makes the graph simple, by removing self loops and parallel edges if any.
72  *
73  * @param graph The graph to make simple.
74  * @param removed The edges that were removed to make the graph simple.
75  * @param directed Whether the graph shall be considered directed or not.
76  * @return void
77  **/
78  static void makeSimple(Graph *graph, std::vector<edge> &removed, const bool directed = false);
79 
80  /**
81  * Performs simple test and stores found parallel edges in the multipleEdges vector
82  * and found self loops in the loops vector.
83  * Returns true if the graph is simple, false otherwise.
84  */
85  /**
86  * @brief Checks if the graph is simple, and stores parallel edges and self loops in different
87  *vectors.
88  *
89  * @param graph The graph to check for simplicity.
90  * @param multipleEdges The parallel edges that need to be removed to make the graph simple.
91  *Defaults to 0.
92  * @param loops The self loops that need to be removed to make the graph simple. Defaults to 0.
93  * @param directed Whether the graph shall be considered directed or not.
94  * @return bool True if the graph is simple, false otherwise.
95  **/
96  static bool simpleTest(const Graph *graph, std::vector<edge> *multipleEdges = nullptr,
97  std::vector<edge> *loops = nullptr, const bool directed = false);
98 };
99 } // namespace tlp
100 #endif
Performs test to check if a graph is Simple. An undirected graph is simple if it has no loops and no ...
Definition: SimpleTest.h:40
static bool isSimple(const Graph *graph, const bool directed=false)
Checks if the graph is simple (i.e. it contains no self loops or parallel edges).
static bool simpleTest(const Graph *graph, std::vector< edge > *multipleEdges=nullptr, std::vector< edge > *loops=nullptr, const bool directed=false)
Checks if the graph is simple, and stores parallel edges and self loops in different vectors.
static bool hasLoops(const Graph *graph)
Checks if the graph has self loop edges.
static void makeSimple(Graph *graph, std::vector< edge > &removed, const bool directed=false)
Makes the graph simple, by removing self loops and parallel edges if any.
static bool hasParallelEdges(const Graph *graph, const bool directed=false)
Checks if the graph has parallel edges.