PrivateGraph.h

Go to the documentation of this file.

 
#ifndef INCLUDE_MOLASSEMBLER_INNER_GRAPH_H
#define INCLUDE_MOLASSEMBLER_INNER_GRAPH_H
 
#include "boost/graph/adjacency_list.hpp"
#include "Utils/Geometry/ElementTypes.h"
 
#include "Utils/Typenames.h"
 
#include "Molassembler/Cycles.h"
 
#include <limits>
 
namespace Scine {
namespace Molassembler {
 
class PrivateGraph {
public:
  struct VertexData {
    Utils::ElementType elementType;
  };
 
  struct EdgeData {
    BondType bondType;
  };
 
  using BglType = boost::adjacency_list<
    /* OutEdgeListS = Type of Container for edges of a vertex
     * Options: vector, list, slist, set, multiset, unordered_set
     * Choice: vecS, we have to rigorously test that no parallel edges are
     *   created
     */
    boost::vecS,
    /* VertexListS = Type of Container for vertices
     * Options: vector, list, slist, set, multiset, unordered_set
     * Choice: vecS, removing vertices is rare, keep memory use limited
     * Consequence: operation remove_vertex() invalidates:
     *   - Vertex descriptors / iterators
     *   - Edge descriptors / iterators
     *   - Adjacency iterators
     */
    boost::vecS,
    // Molecular graphs are undirected
    boost::undirectedS,
    // VertexProperty: What information is stored about vertices?
    VertexData,
    // EdgeProperty: What information is stored about edges?
    EdgeData
    // GraphProperty: Omitted, defaults
    // EdgeListS: Omitted, defaults
  >;
 
  using Vertex = BglType::vertex_descriptor;
  using Edge = BglType::edge_descriptor;
 
  using VertexRange = IteratorRange<BglType::vertex_iterator>;
  using EdgeRange = IteratorRange<BglType::edge_iterator>;
  using AdjacentVertexRange = IteratorRange<BglType::adjacency_iterator>;
  using IncidentEdgeRange = IteratorRange<BglType::out_edge_iterator>;
 
  struct RemovalSafetyData {
    std::unordered_set<PrivateGraph::Vertex> articulationVertices;
    std::set<PrivateGraph::Edge> bridges;
  };
 
  PrivateGraph();
  PrivateGraph(Vertex N);
 
  PrivateGraph(const PrivateGraph& other);
  PrivateGraph(PrivateGraph&& other);
  PrivateGraph& operator = (const PrivateGraph& other);
  PrivateGraph& operator = (PrivateGraph&& other) noexcept;
  ~PrivateGraph();
 
  static constexpr Vertex removalPlaceholder = std::numeric_limits<Vertex>::max();
 
 
  Edge addEdge(Vertex a, Vertex b, BondType bondType);
 
  Vertex addVertex(Utils::ElementType elementType);
 
  void applyPermutation(const std::vector<Vertex>& permutation);
 
  BondType& bondType(const Edge& edge);
 
  BglType& bgl();
 
  void clearVertex(Vertex a);
 
  Utils::ElementType& elementType(Vertex a);
 
  void removeEdge(const Edge& e);
 
  void removeVertex(Vertex a);
 
  std::unordered_map<Vertex, Vertex> merge(
    const PrivateGraph& other,
    const std::vector<Vertex>& copyVertices = {}
  );
 
  bool adjacent(Vertex a, Vertex b) const;
 
  Utils::ElementType elementType(Vertex a) const;
  BondType bondType(const Edge& edge) const;
  const BglType& bgl() const;
 
  bool canRemove(Vertex a) const;
  bool canRemove(const Edge& edge) const;
 
  unsigned connectedComponents() const;
 
  unsigned connectedComponents(std::vector<unsigned>& componentMap) const;
 
  Edge edge(Vertex a, Vertex b) const;
 
  boost::optional<Edge> edgeOption(Vertex a, Vertex b) const;
 
  Utils::ElementTypeCollection elementCollection() const;
 
  Vertex source(const Edge& edge) const;
  Vertex target(const Edge& edge) const;
 
  unsigned degree(Vertex a) const;
 
  std::string graphviz() const;
 
  [[deprecated("Prefer V")]]
  Vertex N() const;
  [[deprecated("Prefer E")]]
  Vertex B() const;
 
  Vertex V() const;
  unsigned E() const;
 
  boost::optional<std::vector<AtomIndex>> modularIsomorphism(
    const PrivateGraph& other,
    AtomEnvironmentComponents components = AtomEnvironmentComponents::All
  ) const;
 
  bool identicalGraph(const PrivateGraph& other) const;
 
  std::pair<
    std::vector<AtomIndex>,
    std::vector<AtomIndex>
  > splitAlongBridge(Edge bridge) const;
 
  std::pair<
    std::vector<AtomIndex>,
    std::vector<AtomIndex>
  > splitAlongBridge(AtomIndex left, const std::vector<AtomIndex>& right) const;
 
  void populateProperties() const;
  const Cycles& cycles() const;
  const RemovalSafetyData& removalSafetyData() const;
  const Cycles& etaPreservedCycles() const;
 
  VertexRange vertices() const;
  EdgeRange edges() const;
  AdjacentVertexRange adjacents(Vertex a) const;
  IncidentEdgeRange edges(Vertex a) const;
 
  bool operator == (const PrivateGraph& other) const;
  inline bool operator != (const PrivateGraph& other) const {
    return !(*this == other);
  }
 
private:
  struct Properties {
    boost::optional<RemovalSafetyData> removalSafetyDataOption;
    boost::optional<Cycles> cyclesOption;
    boost::optional<Cycles> etaPreservedCyclesOption;
 
    inline void invalidate() {
      removalSafetyDataOption = boost::none;
      cyclesOption = boost::none;
      etaPreservedCyclesOption = boost::none;
    }
  };
 
  RemovalSafetyData generateRemovalSafetyData_() const;
  Cycles generateCycles_() const;
  Cycles generateEtaPreservedCycles_() const;
 
  BglType graph_;
  mutable Properties properties_;
};
 
} // namespace Molassembler
} // namespace Scine
#endif