Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
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
27namespace tlp {
28
29class Graph;
30struct 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 **/
40class TLP_SCOPE SimpleTest {
41public:
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.