1 /* 2 * E 3 * Copyright 2009-2020 The VOTCA Development Team 4 * (http://www.votca.org) 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License") 7 * 8 * You may not use this file except in compliance with the License. 9 * You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, software 14 * distributed under the License is distributed on an "AS IS" BASIS, 15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16 * See the License for the specific language governing permissions and 17 * limitations under the License. 18 * 19 */ 20 21 #ifndef VOTCA_TOOLS_REDUCEDGRAPH_H 22 #define VOTCA_TOOLS_REDUCEDGRAPH_H 23 24 // Local VOTCA includes 25 #include "graph.h" 26 #include "reducededge.h" 27 28 namespace votca { 29 namespace tools { 30 31 /** 32 * \brief Contains a graph that consits of vertices with degree of 1 or greater 33 *than 3 34 * 35 * The point of this class is to reduce the computational complexity of a 36 * regular graph. This is achieved by removing any vertices with degree 2. For 37 * example a graph: 38 * 39 * 1 - 2 - 3 - 4 - 5 - 9 40 * | | | 41 * 6 - 7 8 42 * 43 * Would be reduced to 44 * 45 * 1 - 2 - 3 - 4 - 9 46 * | _ | | 47 * 8 48 * 49 * Notice that the vertices 5, 6 and 7 have been removed, there also exist two 50 * edges connecting 2 to 3. The reduced graph still contains all the information 51 * associated with the full graph but when used with graph algorithms only the 52 * vertices and nodes associated with the reduced graph are used. 53 * 54 **/ 55 class ReducedGraph : public Graph { 56 private: 57 /** 58 * The inherited graph stores all the edges describing the graph after it 59 * has been reduced. However, in order to expand the edges back to the 60 * vertices that make them up a second variable is needed. dbl_str_to_int(a_str)61 * 62 * E.g. 63 * 64 * 1 - 2 - 4 - 9 - 5 65 * 66 * The edge 67 * 68 * 1 - 5 69 * 70 * Would be stored in the parent graph datastructure, the rest of the 71 * vertices are stored as a vector in the expanded_edges_ object 72 **/ 73 std::unordered_map<Edge, std::vector<std::vector<Index>>> expanded_edges_; 74 75 void init_(std::vector<ReducedEdge> reduced_edges, 76 std::unordered_map<Index, GraphNode> nodes); 77 78 // Junctions must be stored internally 79 std::set<Index> junctions_; 80 81 public: 82 ReducedGraph() = default; 83 84 ReducedGraph(std::vector<ReducedEdge> reduced_edges); 85 ReducedGraph(std::vector<ReducedEdge> reduced_edges, 86 std::unordered_map<Index, GraphNode> nodes); 87 88 /** 89 * \brief Allows one to return all edges connecting two vertices of the 90 *reduced graph. 91 * 92 * In this case if edge (2,3) were passed in: 93 * 94 * 1 - 2 - 3 - 4 - 5 - 9 95 * | | | 96 * 6 - 7 8 97 * 98 * Reduced Graph 99 * 100 * 1 - 2 - 3 - 4 - 9 101 * | _ | | 102 * 8 103 * 104 * The following vectors would be returned 105 * 106 * vec_edges = expandEdge(Edge(2,3)); 107 * vec_edges.at(0); // 2-3 108 * vec_edges.at(1); // 2-6, 6-7, 7-3 109 **/ 110 std::vector<std::vector<Edge>> expandEdge(const Edge& edge) const; 111 112 /// This method will return a copy of the full graph 113 Graph expandGraph() const; 114 115 /** 116 * \brief Gets the junctions in the graph. 117 * 118 * This method is different from the regular graph method as it must account 119 * for edges that loop around and refer to the same vertex. 120 * 121 * E.g. 122 * 123 * - - 124 * | | 125 * - -1 - 2 - 3 126 * 127 * This is composed of the edges: 128 * 1, 1 129 * 1, 2 130 * 2, 3 131 * 132 * Thus 1 is the only junction that exists in the reduced graph 133 **/ 134 // std::vector<Index> getJunctions() const; 135 136 std::vector<std::pair<Index, GraphNode>> getNodes(void) const override; 137 138 std::vector<Index> getVerticesDegree(Index degree) const override; 139 140 friend std::ostream& operator<<(std::ostream& os, const ReducedGraph graph); 141 }; 142 143 } // namespace tools 144 } // namespace votca 145 #endif // VOTCA_TOOLS_REDUCEDGRAPH_H 146