graphalgorithm.h

Go to the documentation of this file.

/*
 *            Copyright 2009-2020 The VOTCA Development Team
 *                       (http://www.votca.org)
 *
 *      Licensed under the Apache License, Version 2.0 (the "License")
 *
 * You may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *              http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 */
 
#ifndef VOTCA_TOOLS_GRAPHALGORITHM_H
#define VOTCA_TOOLS_GRAPHALGORITHM_H
 
// Standard includes
#include <memory>
#include <string>
 
// Local VOTCA includes
#include "graphnode.h"
#include "reducedgraph.h"
 
namespace votca {
namespace tools {
 
class Graph;
class GraphVisitor;
 
bool singleNetwork(Graph& graph, GraphVisitor& graph_visitor);
 
std::set<Edge> exploreBranch(Graph g, Index starting_vertex, const Edge& edge);
 
ReducedGraph reduceGraph(Graph graph);
 
std::vector<Graph> decoupleIsolatedSubGraphs(Graph graph);
 
void exploreGraph(Graph& graph, GraphVisitor& graph_visitor);
 
template <typename GV>
std::string findStructureId(Graph& graph) {
 
  // Determine the highest degree in the graph
  Index maxD = graph.getMaxDegree();
  // Get the vertices with this degree
  std::vector<Index> vertices = graph.getVerticesDegree(maxD);
 
  // Get the nodes and determine which node has the greatest stringID
  // When compared using compare function
  std::string str_id = "";
  std::vector<Index> graph_node_ids;
  for (const Index& vertex : vertices) {
    GraphNode graph_node = graph.getNode(vertex);
    Index comp_int = str_id.compare(graph_node.getStringId());
    if (comp_int > 0) {
      str_id = graph_node.getStringId();
      graph_node_ids.clear();
      graph_node_ids.push_back(vertex);
    } else if (comp_int == 0) {
      graph_node_ids.push_back(vertex);
    }
  }
  // If the str_id is empty it means the nodes are empty and we will
  // simply have to rely on the degree to choose the vertices to explore from
  if (str_id.compare("") == 0) {
    graph_node_ids = vertices;
  }
  // If two or more graph nodes are found to be equal then
  // they must all be explored
  std::string chosenId = "";
  Graph graph_chosen = graph;
 
  for (const Index& vertex : graph_node_ids) {
    GV graph_visitor;
    graph_visitor.setStartingVertex(vertex);
    Graph graph_temp = graph;
    exploreGraph(graph_temp, graph_visitor);
    std::string temp_struct_id = graph_temp.getId();
    if (chosenId.compare(temp_struct_id) < 0) {
      chosenId = temp_struct_id;
      graph_chosen = graph_temp;
    }
  }
 
  graph = graph_chosen;
  return chosenId;
}
}  // namespace tools
}  // namespace votca
 
#endif  // VOTCA_TOOLS_GRAPHALGORITHM_H