1 /****************************************************************************** 2 3 This source file is part of the Avogadro project. 4 5 Copyright 2011-2012 Kitware, Inc. 6 7 This source code is released under the New BSD License, (the "License"). 8 9 Unless required by applicable law or agreed to in writing, software 10 distributed under the License is distributed on an "AS IS" BASIS, 11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 See the License for the specific language governing permissions and 13 limitations under the License. 14 15 ******************************************************************************/ 16 17 #ifndef AVOGADRO_CORE_GRAPH_H 18 #define AVOGADRO_CORE_GRAPH_H 19 20 #include "avogadrocore.h" 21 22 #include <cstddef> 23 #include <vector> 24 25 namespace Avogadro { 26 namespace Core { 27 28 /** 29 * @class Graph graph.h <avogadro/core/graph.h> 30 * @brief The Graph class represents a graph data structure. 31 */ 32 33 class AVOGADROCORE_EXPORT Graph 34 { 35 public: 36 /** Creates a new, empty graph. */ 37 Graph(); 38 39 /** Creates a new graph containing size @p n vertices. */ 40 explicit Graph(size_t n); 41 42 /** Destroys the graph. */ 43 ~Graph(); 44 45 /** Sets the number of verticies in the graph to size @p n. */ 46 void setSize(size_t n); 47 48 /** Returns the number of verticies in the graph. */ 49 size_t size() const; 50 51 /** Returns \c true if the graph is empty (i.e. size() == \c 0). */ 52 bool isEmpty() const; 53 54 /** Removes all verticies and edges from the graph. */ 55 void clear(); 56 57 /** Adds a vertex to the graph and returns its index. */ 58 size_t addVertex(); 59 60 /** Removes the vertex at @p index from the graph. */ 61 void removeVertex(size_t index); 62 63 /** Returns the number of verticies in the graph. */ 64 size_t vertexCount() const; 65 66 /** Adds an edge between verticies @p a and @p b. */ 67 void addEdge(size_t a, size_t b); 68 69 /** Removes the edge between veritices @p a and @p b. */ 70 void removeEdge(size_t a, size_t b); 71 72 /** Removes all of the edges from the graph. */ 73 void removeEdges(); 74 75 /** 76 * Removes all of the edges that contain the vertex at @p index from the 77 * graph. 78 */ 79 void removeEdges(size_t index); 80 81 /** Returns the number of edges in the graph. */ 82 size_t edgeCount() const; 83 84 /** 85 * Returns a vector containing the indicies of each vertex that the vertex at 86 * index shares an edge with. 87 */ 88 const std::vector<size_t>& neighbors(size_t index) const; 89 90 /** Returns the degree of the vertex at @p index. */ 91 size_t degree(size_t index) const; 92 93 /** 94 * Returns \c true if the graph contains an edge between verticies @p a and 95 * @p b. 96 */ 97 bool containsEdge(size_t a, size_t b) const; 98 99 /** 100 * Returns a vector of vector containing the indicies of each vertex in each 101 * connected component in the graph. 102 */ 103 std::vector<std::vector<size_t>> connectedComponents() const; 104 105 private: 106 std::vector<std::vector<size_t>> m_adjacencyList; 107 }; 108 109 } // end Core namespace 110 } // end Avogadro namespace 111 112 #endif // AVOGADRO_CORE_GRAPH_H 113