ImplicitBoundsGraph.h

Go to the documentation of this file.

#ifndef INCLUDE_DISTANCE_GEOMETRY_IMPLICIT_BOUNDS_GRAPH_H
#define INCLUDE_DISTANCE_GEOMETRY_IMPLICIT_BOUNDS_GRAPH_H

// #define MOLASSEMBLER_IMPLICIT_GRAPH_USE_SPECIALIZED_GOR1_ALGORITHM

#include "boost/property_map/property_map.hpp"
#include "Eigen/Core"
#include "Utils/Geometry/ElementTypes.h"

#include "Molassembler/DistanceGeometry/ValueBounds.h"
#include "Molassembler/Conformers.h"

#include <array>
#include <map>
#include <tuple>

namespace Scine {
namespace Molassembler {

namespace Random {
class Engine;
} // namespace Random

// Forward-declare PrivateGraph
class PrivateGraph;

namespace DistanceGeometry {

// Forward-declarations
class DistanceBoundsMatrix;

class ImplicitBoundsGraph {
public:
  using VertexDescriptor = unsigned long;
  using EdgeDescriptor = std::pair<VertexDescriptor, VertexDescriptor>;

  /* To outer indexing */
  [[gnu::const]] inline static VertexDescriptor left(const VertexDescriptor a) noexcept {
    return 2 * a;
  }

  [[gnu::const]] inline static VertexDescriptor right(const VertexDescriptor a) noexcept {
    return 2 * a + 1;
  }

  [[gnu::const]] inline static VertexDescriptor internal(const VertexDescriptor i) noexcept {
    // Integer division rounds down, which is perfect
    return i / 2;
  }

private:
  const PrivateGraph* innerGraphPtr_;

  std::array<Utils::ElementType, 2> heaviestAtoms_;

  Eigen::MatrixXd distances_;

  static void explainContradictionPaths_(
    VertexDescriptor a,
    VertexDescriptor b,
    const std::vector<VertexDescriptor>& predecessors,
    const std::vector<double>& distances
  );

public:
  using BoundsMatrix = Eigen::MatrixXd;

  ImplicitBoundsGraph(
    const PrivateGraph& inner,
    BoundsMatrix bounds
  );

  /* Information */
  VertexDescriptor num_vertices() const;

  VertexDescriptor num_edges() const;

  std::pair<EdgeDescriptor, bool> edge(VertexDescriptor i, VertexDescriptor j) const;

  bool hasExplicit(const EdgeDescriptor& edge) const;

  /* To inner indexing */
  [[gnu::const]] inline static bool isLeft(const VertexDescriptor i) noexcept {
    return i % 2 == 0;
  }

  [[gnu::const]] inline static bool sameSide(const VertexDescriptor i, const VertexDescriptor j) noexcept {
    return i % 2 == j % 2;
  }

  Result<Eigen::MatrixXd> makeDistanceBounds() const noexcept;

  Result<Eigen::MatrixXd> makeDistanceMatrix(Random::Engine& engine) noexcept;

  Result<Eigen::MatrixXd> makeDistanceMatrix(Random::Engine& engine, Partiality partiality) noexcept;

  inline VertexDescriptor source(const EdgeDescriptor& e) const {
    return e.first;
  }

  inline VertexDescriptor target(const EdgeDescriptor& e) const {
    return e.second;
  }

  inline const Eigen::MatrixXd& getMatrix() const {
    return distances_;
  }

  VertexDescriptor out_degree(VertexDescriptor i) const;

  /* These are all O(1) */
  double& lowerBound(VertexDescriptor a, VertexDescriptor b);
  double& upperBound(VertexDescriptor a, VertexDescriptor b);

  double lowerBound(VertexDescriptor a, VertexDescriptor b) const;
  double upperBound(VertexDescriptor a, VertexDescriptor b) const;

  double maximalImplicitLowerBound(VertexDescriptor i) const;

  struct EdgeWeightMap : public boost::put_get_helper<double, EdgeWeightMap> {
    using value_type = double;
    using reference = double;
    using key_type = EdgeDescriptor;

    const ImplicitBoundsGraph* basePtr_;

    EdgeWeightMap(const ImplicitBoundsGraph& base);
    double operator [] (const EdgeDescriptor& e) const;
    double operator () (const EdgeDescriptor& e) const;
  };

  EdgeWeightMap getEdgeWeightPropertyMap() const;

  struct VertexIndexMap : public boost::put_get_helper<VertexDescriptor, VertexIndexMap> {
    using value_type = VertexDescriptor;
    using key_type = VertexDescriptor;
    using reference = VertexDescriptor;

    inline VertexDescriptor operator [] (const VertexDescriptor v) const { return v; }
    inline VertexDescriptor operator () (const VertexDescriptor v) const { return v; }
  };

  class vertex_iterator {
    VertexDescriptor index = 0;

  public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = VertexDescriptor;
    using difference_type = int;
    using pointer = VertexDescriptor*;
    using reference = const VertexDescriptor&;

    vertex_iterator();
    vertex_iterator(VertexDescriptor i);
    vertex_iterator(const vertex_iterator& other);
    vertex_iterator(vertex_iterator&& other) noexcept;
    vertex_iterator& operator = (const vertex_iterator& other);
    vertex_iterator& operator = (vertex_iterator&& other) noexcept;

    bool operator == (const vertex_iterator& other) const;

    bool operator != (const vertex_iterator& other) const;

    vertex_iterator& operator ++ ();

    vertex_iterator operator ++ (int);

    vertex_iterator& operator -- ();

    vertex_iterator operator -- (int);

    vertex_iterator& operator + (unsigned i);

    vertex_iterator& operator - (unsigned i);

    VertexDescriptor operator * () const;

    int operator - (const vertex_iterator& other) const;
  };

  vertex_iterator vbegin () const;

  vertex_iterator vend() const;

  class edge_iterator {
    const ImplicitBoundsGraph* basePtr_;

    VertexDescriptor i_, b_;
    bool crossGroup_;

    void increment_();

  public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = EdgeDescriptor;
    using difference_type = int;
    using pointer = EdgeDescriptor*;
    using reference = const EdgeDescriptor&;

    edge_iterator();
    edge_iterator(
      const ImplicitBoundsGraph& base,
      VertexDescriptor i
    );
    edge_iterator(const edge_iterator& other);
    edge_iterator(edge_iterator&& other) noexcept;
    edge_iterator& operator = (const edge_iterator& other);
    edge_iterator& operator = (edge_iterator&& other) noexcept;

    edge_iterator& operator ++ ();

    edge_iterator operator ++ (int);

    bool operator == (const edge_iterator& other) const;

    bool operator != (const edge_iterator& other) const;

    std::string state() const;

    EdgeDescriptor operator * () const;

    double weight() const;
    VertexDescriptor target() const;
  };

  edge_iterator ebegin() const;

  edge_iterator eend() const;

  edge_iterator obegin(VertexDescriptor i) const;

  edge_iterator oend(VertexDescriptor i) const;

  class in_group_edge_iterator {
    const ImplicitBoundsGraph* basePtr_;
    VertexDescriptor i_;
    VertexDescriptor b_;
    bool isLeft_;

  public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = EdgeDescriptor;
    using difference_type = int;
    using pointer = EdgeDescriptor*;
    using reference = const EdgeDescriptor&;

    // Default constructor
    in_group_edge_iterator();
    // Constructor for the begin iterator
    in_group_edge_iterator(const ImplicitBoundsGraph& base, VertexDescriptor i);
    // Constructor for the end iterator
    in_group_edge_iterator(
      const ImplicitBoundsGraph& base,
      VertexDescriptor i,
      bool /* tag */
    );
    in_group_edge_iterator(const in_group_edge_iterator& other);
    in_group_edge_iterator(in_group_edge_iterator&& other) noexcept;
    in_group_edge_iterator& operator = (in_group_edge_iterator&& other) noexcept;
    in_group_edge_iterator& operator = (const in_group_edge_iterator& other);

    inline in_group_edge_iterator& operator ++ () {
      /* Find the next position in the matrix with information
       * The fastest way to check if there is information is to just access
       * either the lower or upper bound, and convert the double there to
       * boolean. That boolean is true only if the double is != 0.
       */
      ++b_;
      while(
        b_ < static_cast<VertexDescriptor>(basePtr_->distances_.outerSize())
        && (basePtr_->distances_(internal(i_), b_) == 0.0)
      ) {
        ++b_;
      }
      return *this;
    }

    inline in_group_edge_iterator operator ++ (int) {
      auto copy = *this;
      ++(*this);
      return copy;
    }

    inline bool operator == (const in_group_edge_iterator& other) {
      return (
        isLeft_ == other.isLeft_
        && i_ == other.i_
        && b_ == other.b_
        && basePtr_ == other.basePtr_
      );
    }
    inline bool operator != (const in_group_edge_iterator& other) {
      return !(*this == other);
    }

    inline EdgeDescriptor operator *() const {
      return {i_, target()};
    }

    inline VertexDescriptor target() const {
      if(isLeft_) {
        return left(b_);
      }

      return right(b_);
    }

    inline double weight() const {
      return basePtr_->upperBound(internal(i_), b_);
    }
  };

  inline in_group_edge_iterator in_group_edges_begin(const VertexDescriptor i) const {
    return {*this, i};
  }

  inline in_group_edge_iterator in_group_edges_end(const VertexDescriptor i) const {
    return {*this, i, true};
  }
};

} // namespace DistanceGeometry
} // namespace Molassembler
} // namespace Scine

#endif