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