votca 2024-dev
Loading...
Searching...
No Matches
graphalgorithm.cc
Go to the documentation of this file.
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 writingraph, 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// Standard includes
21#include <list>
22
23// Local VOTCA includes
24#include "votca/tools/graph.h"
29
30using namespace std;
31
32namespace votca {
33namespace tools {
34
35/**********************
36 * Internal Functions *
37 **********************/
38
39/********************
40 * Public Functions *
41 ********************/
42bool singleNetwork(Graph& graph, GraphVisitor& graph_visitor) {
43 exploreGraph(graph, graph_visitor);
44 return graph_visitor.getExploredVertices().size() ==
45 graph.getVertices().size() &&
46 graph.getIsolatedNodes().size() == 0;
47}
48
49std::set<Edge> exploreBranch(Graph g, Index starting_vertex, const Edge& edge) {
50 // Check if the starting vertex is in the graph
51 if (!g.vertexExist(starting_vertex)) {
52 throw invalid_argument(
53 "Cannot explore a branch of the graph when the "
54 "exploration is started from a vertex that does not exist within the "
55 "graph.");
56 }
57 if (!g.edgeExist(edge)) {
58 throw invalid_argument(
59 "Edge does not exist in the graph so exploration of"
60 " the graph branch cannot continue");
61 }
62 if (!edge.contains(starting_vertex)) {
63 throw invalid_argument(
64 "The edge determining which branch to explore does "
65 "not contain the starting vertex.");
66 }
67
68 set<Edge> branch_edges;
69 if (edge.getEndPoint1() == edge.getEndPoint2()) {
70 branch_edges.insert(edge);
71 return branch_edges;
72 }
73 Graph_BF_Visitor gv_breadth_first;
74 GraphNode gn;
75 pair<Index, GraphNode> pr_gn(starting_vertex, gn);
76 gv_breadth_first.exploreNode(pr_gn, g);
77 gv_breadth_first.setStartingVertex(edge.getOtherEndPoint(starting_vertex));
78 gv_breadth_first.initialize(g);
79
80 branch_edges.insert(edge);
81 while (!gv_breadth_first.queEmpty()) {
82 Edge ed = gv_breadth_first.nextEdge(g);
83 branch_edges.insert(ed);
84 gv_breadth_first.exec(g, ed);
85 }
86
87 vector<Edge> neigh_edges = g.getNeighEdges(starting_vertex);
88 for (Edge& ed : neigh_edges) {
89 Index neigh_vertex = ed.getOtherEndPoint(starting_vertex);
90 if (neigh_vertex != starting_vertex) {
91 if (gv_breadth_first.vertexExplored(neigh_vertex)) {
92 branch_edges.insert(ed);
93 }
94 }
95 }
96
97 return branch_edges;
98}
99
101
102 /****************************
103 * Internal Function Class
104 ****************************/
105
113 class ExplorationRecord {
114 private:
115 unordered_map<Index, std::pair<bool, Index>> vertex_explored_;
116 size_t unexplored_vertex_count_;
117
118 public:
119 explicit ExplorationRecord(
120 const unordered_map<Index, std::pair<bool, Index>>& vertex_explored)
121 : vertex_explored_(vertex_explored),
122 unexplored_vertex_count_(vertex_explored.size()){};
123
124 void explore(Index vertex) {
125 vertex_explored_[vertex].first = true;
126 --unexplored_vertex_count_;
127 }
128
129 bool unexploredVerticesExist() { return unexplored_vertex_count_ > 0; }
130
131 Index getUnexploredVertex() {
132
133 vector<Index> remaining_unexplored;
134 for (const pair<const Index, pair<bool, Index>>& vertex_record :
135 vertex_explored_) {
136 bool vertex_explored = vertex_record.second.first;
137 if (!vertex_explored) {
138 Index degree = vertex_record.second.second;
139 if (degree > 2) {
140 return vertex_record.first;
141 }
142 remaining_unexplored.push_back(vertex_record.first);
143 }
144 }
145
146 // Search tips next
147 for (const Index& vertex : remaining_unexplored) {
148 if (vertex_explored_[vertex].second == 1) {
149 return vertex;
150 }
151 }
152
153 // Finally if there are no tips or junctions left we will return a vertex
154 // of degree 2 if one exists
155 for (const Index& vertex : remaining_unexplored) {
156 if (!vertex_explored_[vertex].first) {
157 return vertex;
158 }
159 }
160
161 throw runtime_error(
162 "You cannot get an unexplored vertex as they have all"
163 " been explored.");
164 }
165 }; // Class ExplorationRecord
166
167 unordered_map<Index, pair<bool, Index>> unexplored_vertices;
168 vector<Index> vertices = graph.getVertices();
169 for (const Index& vertex : vertices) {
170 unexplored_vertices[vertex] =
171 pair<bool, Index>(false, graph.getDegree(vertex));
172 }
173
174 ExplorationRecord exploration_record(unexplored_vertices);
175
176 vector<vector<Index>> chains;
177
178 while (exploration_record.unexploredVerticesExist()) {
179 Graph_DF_Visitor graph_visitor;
180 Index starting_vertex = exploration_record.getUnexploredVertex();
181 exploration_record.explore(starting_vertex);
182 graph_visitor.setStartingVertex(starting_vertex);
183 graph_visitor.initialize(graph);
184
185 vector<Index> chain{starting_vertex};
186 Index old_vertex = starting_vertex;
187 bool new_chain = false;
188 while (!graph_visitor.queEmpty()) {
189 Edge edge = graph_visitor.nextEdge(graph);
190 vector<Index> unexplored_vertex = graph_visitor.getUnexploredVertex(edge);
191
192 if (new_chain) {
193 if (unexplored_vertex.size() == 0) {
194 old_vertex = edge.getEndPoint1();
195 chain.push_back(old_vertex);
196 new_chain = false;
197 } else {
198 old_vertex = edge.getOtherEndPoint(unexplored_vertex.at(0));
199 chain.push_back(old_vertex);
200 new_chain = false;
201 }
202 }
203 Index new_vertex = edge.getOtherEndPoint(old_vertex);
204 if (unexplored_vertex.size() == 0) {
205 chain.push_back(new_vertex);
206 chains.push_back(chain);
207 chain.clear();
208 new_chain = true;
209 } else if (graph.getDegree(new_vertex) == 1) {
210 chain.push_back(new_vertex);
211 chains.push_back(chain);
212 chain.clear();
213 exploration_record.explore(new_vertex);
214 new_chain = true;
215 } else if (graph.getDegree(new_vertex) > 2) {
216 chain.push_back(new_vertex);
217 chains.push_back(chain);
218 chain.clear();
219 exploration_record.explore(new_vertex);
220 new_chain = true;
221 } else if (unexplored_vertex.size() == 1) {
222 chain.push_back(new_vertex);
223 old_vertex = new_vertex;
224 exploration_record.explore(new_vertex);
225 }
226
227 graph_visitor.exec(graph, edge);
228 }
229 }
230 vector<ReducedEdge> reduced_edges;
231 for (vector<Index> chain : chains) {
232 ReducedEdge reduced_edge(chain);
233 reduced_edges.push_back(reduced_edge);
234 }
235
236 ReducedGraph reduced_g(reduced_edges);
237 auto nodes_graph = graph.getNodes();
238 reduced_g.clearNodes();
239 reduced_g.copyNodes(graph);
240 auto nodes_reduced_g = reduced_g.getNodes();
241 return reduced_g;
242}
243
244vector<Graph> decoupleIsolatedSubGraphs(Graph graph) {
245
246 const std::vector<Index>& vertices = graph.getVertices();
247 // bool vector to see if vertex is already part of graph
248 std::vector<bool> vertex_analysed = std::vector<bool>(vertices.size(), false);
249
250 std::vector<Graph> subGraphs;
251 Index i = 0;
252 while (i < Index(vertices.size())) {
253 if (vertex_analysed[i]) {
254 i++;
255 continue;
256 }
257 Graph_BF_Visitor graph_visitor_breadth_first;
258 graph_visitor_breadth_first.setStartingVertex(vertices[i]);
259 exploreGraph(graph, graph_visitor_breadth_first);
260 set<Index> sub_graph_explored_vertices =
261 graph_visitor_breadth_first.getExploredVertices();
262
263 for (Index vertex : sub_graph_explored_vertices) {
264 for (Index j = 0; j < Index(vertices.size()); j++) {
265 if (vertex_analysed[j]) {
266 continue;
267 }
268 if (vertex == vertices[j]) {
269 vertex_analysed[j] = true;
270 break;
271 }
272 }
273 }
274
275 set<Edge> sub_graph_edges;
276 unordered_map<Index, GraphNode> sub_graph_nodes;
277 for (Index vertex : sub_graph_explored_vertices) {
278
279 for (const Edge& sub_graph_edge : graph.getNeighEdges(vertex)) {
280 sub_graph_edges.insert(sub_graph_edge);
281 }
282 sub_graph_nodes[vertex] = graph.getNode(vertex);
283 }
284 subGraphs.push_back(
285 Graph(std::vector<Edge>(sub_graph_edges.begin(), sub_graph_edges.end()),
286 sub_graph_nodes));
287 }
288 return subGraphs;
289}
290
291void exploreGraph(Graph& graph, GraphVisitor& graph_visitor) {
292
293 if (!graph.vertexExist(graph_visitor.getStartingVertex())) {
294 string err = "Cannot explore graph starting at vertex " +
295 to_string(graph_visitor.getStartingVertex()) +
296 " because it does not exist in the "
297 "graph. You can change the starting vertex by using the "
298 "setStartingVertex method of the visitor instance.";
299 throw invalid_argument(err);
300 }
301 // Create a list of all vertices and determine if they have all been
302 // explored when the visitor que is empty
303 graph_visitor.initialize(graph);
304 while (!graph_visitor.queEmpty()) {
305 Edge edge = graph_visitor.nextEdge(graph);
306 graph_visitor.exec(graph, edge);
307 }
308}
309} // namespace tools
310} // namespace votca
Connects to vertices.
Definition edge.h:42
Index getEndPoint1() const
grab the smaller integer
Definition edge.h:55
Index getEndPoint2() const
grab the larger integer
Definition edge.h:57
Index getOtherEndPoint(Index ver) const
Given one of the integers in the edge the other will be output.
Definition edge.cc:37
bool contains(Index ID) const
Determine if the edge contains the Index ID.
Definition edge.cc:45
A graph node that will take a variety of different values.
Definition graphnode.h:46
virtual void exec(Graph &graph, Edge edge)
std::vector< Index > getUnexploredVertex(const Edge edge) const
Determine which vertices in the edge, if any, have not been explored.
std::set< Index > getExploredVertices() const
Get the set of all the vertices that have been explored.
virtual bool queEmpty() const
virtual void exploreNode(std::pair< Index, GraphNode > &vertex_and_node, Graph &graph, Edge edge=DUMMY_EDGE)
Edge(0,0) is a dummy value.
void setStartingVertex(Index vertex)
Index getStartingVertex() const
Edge nextEdge(Graph graph)
void initialize(Graph &graph)
Initialize the graphvisitor the default starting point is 0.
bool vertexExplored(const Index vertex) const
Has the vertex been explored.
std::vector< std::pair< Index, GraphNode > > getIsolatedNodes(void) const
Definition graph.cc:65
void copyNodes(Graph &graph)
Definition graph.cc:122
GraphNode getNode(const Index vertex) const
Return a copy of the graph node at vertex 'vert'.
Definition graph.cc:97
std::vector< Index > getVertices() const
Returns all the vertices in the graph.
Definition graph.cc:166
void clearNodes()
Remove contents of all nodes.
Definition graph.cc:120
std::vector< Edge > getNeighEdges(Index vertex) const
Returns all the edges in the graph connected to vertex vertex
Definition graph.h:106
virtual bool edgeExist(const Edge &edge) const
Determines if an edge is stored in the graph.
Definition graph.h:132
virtual std::vector< std::pair< Index, GraphNode > > getNodes() const
Return all the vertices and their graph nodes that are within the graph.
Definition graph.cc:102
Index getDegree(Index vertex) const
Calcualtes the degree, or number of edges connected to vertex vertex
Definition graph.cc:140
bool vertexExist(Index vertex) const
Determines if a vertex exists within the graph.
Definition graph.cc:152
Connects two vertices, also stores the vertices between the endpoints.
Definition reducededge.h:49
Contains a graph that consits of vertices with degree of 1 or greater than 3.
std::vector< std::pair< Index, GraphNode > > getNodes(void) const override
Gets the junctions in the graph.
STL namespace.
ReducedGraph reduceGraph(Graph graph)
Will take a graph and reduce it, by removing all vertices with degree of 2.
bool singleNetwork(Graph &graph, GraphVisitor &graph_visitor)
Determine if every vertex is connected to every other one through some combination of edges.
std::set< Edge > exploreBranch(Graph g, Index starting_vertex, const Edge &edge)
Explore one of the branches if exploration is initiated at vertex starting_vertex.
std::vector< Graph > decoupleIsolatedSubGraphs(Graph graph)
Break graph into smaller graph instances if the network is made up of isolated sub networks.
void exploreGraph(Graph &graph, GraphVisitor &graph_visitor)
Explore a graph with a graph visitor.
base class for all analysis tools
Definition basebead.h:33
Eigen::Index Index
Definition types.h:26