1 /* 2 * Copyright 2009-2020 The VOTCA Development Team 3 * (http://www.votca.org) 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License") 6 * 7 * You may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 * 18 */ 19 20 #ifndef VOTCA_TOOLS_GRAPH_H 21 #define VOTCA_TOOLS_GRAPH_H 22 23 // Standard includes 24 #include <string> 25 #include <unordered_map> 26 #include <utility> 27 #include <vector> 28 29 // Local VOTCA includes 30 #include "edgecontainer.h" 31 #include "graphnode.h" 32 33 namespace votca { 34 namespace tools { 35 36 /** 37 * \brief A graph object that contains the graph nodes and the edges describing 38 * the bonds between nodes. 39 * 40 */ 41 class GraphNode; 42 43 class Graph { 44 protected: 45 EdgeContainer edge_container_; 46 47 /// Parameter description 48 /// @param Index - is the index of the graph nodes / vertex ids 49 /// @param GraphNode - this is the node object at each vertex and contains 50 /// all the informatino that is relevant to that object 51 std::unordered_map<Index, GraphNode> nodes_; 52 53 /// This is the id of the graph to graphs that contain the same content 54 /// are considered equal 55 std::string id_; 56 57 protected: 58 /// Calculate the id of the graph 59 void calcId_(); 60 61 public: Graph()62 Graph() : id_(""){}; 63 virtual ~Graph() = default; 64 /// Constructor 65 /// @param edgs - vector of edges where each edge is composed of two 66 /// s (vertex ids) describing a link between the vertices 67 /// @param nodes - unordered_map where the key is the vertex id and the 68 /// target is the graph node 69 Graph(std::vector<Edge> edges, std::unordered_map<Index, GraphNode> nodes); 70 71 /// Equivalence and non equivalence operators work by determine if the 72 /// contents of each graph node in each of the graphs are the same. 73 bool operator!=(const Graph& graph) const; 74 bool operator==(const Graph& graph) const; 75 76 /// Find all the vertices that are isolated (not connected to any other 77 /// vertex) and return them in a vector with their corresponding graph node. 78 std::vector<std::pair<Index, GraphNode>> getIsolatedNodes(void) const; 79 80 /// Returns a vector of the vertices and their graph nodes that are directly 81 /// connected to the vertex 'vert' 82 std::vector<std::pair<Index, GraphNode>> getNeighNodes(Index vertex) const; 83 84 /// set the Node associated with vertex 'vert' 85 void setNode(Index vertex, GraphNode& graph_node); 86 void setNode(std::pair<Index, GraphNode>& id_and_node); 87 88 /// Gets all vertices with degree of 3 or greater 89 std::vector<Index> getJunctions() const; 90 91 /// Return a copy of the graph node at vertex 'vert' 92 GraphNode getNode(const Index vertex) const; 93 94 /// Return all the vertices and their graph nodes that are within the graph 95 virtual std::vector<std::pair<Index, GraphNode>> getNodes() const; 96 97 /// Returns all the vertices of the graph connected to vertex `vert` through 98 /// an edge. getNeighVertices(Index vertex)99 std::vector<Index> getNeighVertices(Index vertex) const { 100 return edge_container_.getNeighVertices(vertex); 101 } 102 103 /// Returns the id of graph getId()104 std::string getId() const { return id_; } 105 106 /// Returns all the edges in the graph getEdges()107 virtual std::vector<Edge> getEdges() { return edge_container_.getEdges(); } 108 109 /// Returns all the edges in the graph connected to vertex `vertex` getNeighEdges(Index vertex)110 std::vector<Edge> getNeighEdges(Index vertex) const { 111 return edge_container_.getNeighEdges(vertex); 112 } 113 114 /// Returns all the vertices in the graph 115 std::vector<Index> getVertices() const; 116 117 /** 118 * \brief Finds the max degree of a vertex in the graph. 119 * 120 * Will look at each of the vertices and find the vertex with the most edges 121 * connected to it. It will count the number of edges this corresponds to the 122 * maximum degree of the graph. 123 **/ getMaxDegree()124 Index getMaxDegree() const { return edge_container_.getMaxDegree(); } 125 126 /// Calcualtes the degree, or number of edges connected to vertex `vertex` 127 Index getDegree(Index vertex) const; 128 129 /// Returns all the vertices with degree specified by `degree` 130 virtual std::vector<Index> getVerticesDegree(Index degree) const; 131 132 /// Determines if a vertex exists within the graph 133 bool vertexExist(Index vertex) const; 134 135 /// Determines if an edge is stored in the graph edgeExist(const Edge & edge)136 virtual bool edgeExist(const Edge& edge) const { 137 return edge_container_.edgeExist(edge); 138 } 139 140 /// Remove contents of all nodes 141 void clearNodes(); 142 /// Copies nodes from one graph to another. This should only be used in cases 143 /// where the graph does not contain nodes before the copy. 144 void copyNodes(Graph& graph); 145 146 friend std::ostream& operator<<(std::ostream& os, const Graph graph); 147 }; 148 149 /** 150 * \brief Compare function pair<Index ,GraphNode> object 151 * 152 * This function is meant to be used with the stl sort algorithm. It will sort 153 * a vector of pairs containing the vertex ids and the graphnodes. Only the 154 * contetns of the graph node object are used to determine precidence e.g. 155 * 156 * pair<Index ,GraphNode> pr_grn1{ 1, gn }; 157 * pair<Index ,GraphNode> pr_grn2{ 2, gn2 }; 158 * 159 * vector<pair<Index ,GraphNode> > vec_pr_gn = { pr_grn1, pr_grn2 , ... etc }; 160 * 161 * sort(vec_pr_gn.begin(),vec_pr_gn.end(),cmpVertNodePair); 162 */ 163 bool cmpVertNodePair(const std::pair<Index, GraphNode>& id_and_node1, 164 const std::pair<Index, GraphNode>& id_and_node2); 165 } // namespace tools 166 } // namespace votca 167 #endif // VOTCA_TOOLS_GRAPH_H 168