Simulates a graph from which triangle inequality bounds can be calculated by shortest-paths. More...
#include <ImplicitBoundsGraph.h>
Data Structures | |
class | edge_iterator |
An iterator to enumerate all edges in a graph. More... | |
struct | EdgeWeightMap |
A helper struct permitting read-access to an edge weight via an edge descriptor. More... | |
class | in_group_edge_iterator |
An iterator to enumerate only edges to the same part of the graph from specific vertices. More... | |
class | vertex_iterator |
A random access iterator through all vertex descriptors of the graph. More... | |
struct | VertexIndexMap |
A helper struct to turn vertex descriptors into numeric indices. More... | |
Public Types | |
using | VertexDescriptor = unsigned long |
using | EdgeDescriptor = std::pair< VertexDescriptor, VertexDescriptor > |
using | BoundsMatrix = Eigen::MatrixXd |
Public Member Functions | |
ImplicitBoundsGraph (const PrivateGraph &inner, BoundsMatrix bounds) | |
VertexDescriptor | num_vertices () const |
Returns the number of vertices simulated by the graph, which is 2N. More... | |
VertexDescriptor | num_edges () const |
Returns the number of edges currently simulated by the graph. More... | |
std::pair< EdgeDescriptor, bool > | edge (VertexDescriptor i, VertexDescriptor j) const |
Fetches an edge descriptor for a speculative edge from i to j. More... | |
bool | hasExplicit (const EdgeDescriptor &edge) const |
Checks if there is explicit information present for a left-to-right edge. More... | |
Result< Eigen::MatrixXd > | makeDistanceBounds () const noexcept |
Generates a bare distance bounds matrix by repeated shortest-paths calculations. More... | |
Result< Eigen::MatrixXd > | makeDistanceMatrix (Random::Engine &engine) noexcept |
Generates a distance matrix by randomly fixing distances within triangle inequality bounds. More... | |
Result< Eigen::MatrixXd > | makeDistanceMatrix (Random::Engine &engine, Partiality partiality) noexcept |
VertexDescriptor | source (const EdgeDescriptor &e) const |
Returns the source vertex from an edge descriptor. More... | |
VertexDescriptor | target (const EdgeDescriptor &e) const |
Returns the target vertex from an edge descriptor. More... | |
const Eigen::MatrixXd & | getMatrix () const |
Allows const-ref access to the underlying matrix for debug purposes. More... | |
VertexDescriptor | out_degree (VertexDescriptor i) const |
Returns the number of out-edges for a particular vertex. More... | |
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 |
Returns the length of the maximal implicit lower bound outgoing from a left vertex. More... | |
EdgeWeightMap | getEdgeWeightPropertyMap () const |
Returns an instance of EdgeWeightMap. | |
vertex_iterator | vbegin () const |
Returns a begin-iterator for vertices. | |
vertex_iterator | vend () const |
Returns an end-iterator for vertices. | |
edge_iterator | ebegin () const |
Returns a begin edge iterator. | |
edge_iterator | eend () const |
Returns an end edge iterator. | |
edge_iterator | obegin (VertexDescriptor i) const |
Returns a begin edge iterator for the out-edges of a specific vertex. | |
edge_iterator | oend (VertexDescriptor i) const |
Returns an end edge iterator for the out-edges of a specific vertex. | |
in_group_edge_iterator | in_group_edges_begin (const VertexDescriptor i) const |
in_group_edge_iterator | in_group_edges_end (const VertexDescriptor i) const |
Static Public Member Functions | |
static VertexDescriptor | left (const VertexDescriptor a) noexcept |
static VertexDescriptor | right (const VertexDescriptor a) noexcept |
static VertexDescriptor | internal (const VertexDescriptor i) noexcept |
static bool | isLeft (const VertexDescriptor i) noexcept |
Check if a vertex descriptor is part of the left subgraph. More... | |
static bool | sameSide (const VertexDescriptor i, const VertexDescriptor j) noexcept |
Private Attributes | |
const PrivateGraph * | innerGraphPtr_ |
Pointer to molecule from which the bounds come from. | |
std::array< Utils::ElementType, 2 > | heaviestAtoms_ |
Stores the two heaviest element types. | |
Eigen::MatrixXd | distances_ |
Dense adjacency matrix for O(1) access to fixed distances. | |
Simulates a graph from which triangle inequality bounds can be calculated by shortest-paths.
Based off of pairwise bounds collected from SpatialModel, this class simulates a graph in which one-to-all triangle inequality bounds can be calculated by a single-source shortest paths calculation.
The general construction of the graph is loosely described in: Havel, Timothy F. "Distance geometry: Theory, algorithms, and chemical applications." Encyclopedia of Computational Chemistry 120 (1998): 723-742.
In essence, for every atomic index a ∈ [0, N), the graph contains two vertices, left(a) and right(a). For every pair of atomic indices a, b that have a distance bound, i.e. a lower and upper bound on their spatial distance within the current metric space, there are six directed edges in the graph:
If there is no explicit bounding information present for the pair a, b, then there are still two edges in the graph:
There are never edges from the right part of the graph to the left.
If a distance bound is narrowed to a fixed distance, this is represented as raising the lower bound to the fixed distance and lowering the upper bound to the fixed distance.
A lot of the implemented functions are not strictly necessary for the specialized shortest-paths algorithm that is used in makeDistanceMatrix(), which is the main purpose of the class, but exist to allow this graph to integrate with boost::graph in order to easily benchmark it with other algorithms like Bellman-Ford and compare it with ExplicitBoundsGraph, which uses a fully-explicit boost::graph class as its underlying datastructure.
Why is the implicit nature of the bonds on the basis of an underlying matrix so much faster than ExplicitBoundsGraph when it comes to generating distance matrices?
Notes for reading the implementation:
Some advice on optimization opportunities:
Do not try to apply an algorithm that uses the existing shortest path information from a previous run to calculate the new shortest paths. There are already few shortest paths algorithms well suited to graphs with negative real edge weights. Dynamic algorithms are differentiated into whether they can deal with edge weight changes, vertex additions, vertex removals, etc. A fully dynamic algorithm can deal with any of those (albeit only a singular one at a time). A fully batch dynamic algorithm can deal with an arbitrary number of any type of graph changes. You need one of those, since fixing a distance in ImplicitBoundsGraph either entails changing six edge weights or changing one and adding five new edges.
These algorithms already have a really hard time getting to better bounds than recalculating the solution from scratch, which is where most effort has been poured into.
In the same vein, do not try to decide which parts of the shortest paths tree are volatile after change in order to avoid recalculating the entire solution. The idea here is to avoid recalculating the tree if the next a-b pair is in the stable part of the shortest-paths tree after the prior distance fixture. Creating an oracle to decide this is probably about as hard as creating a batch dynamic SSSP algorithm that can deal with negative edge weights, so: really hard.
std::pair<EdgeDescriptor, bool> Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::edge | ( | VertexDescriptor | i, |
VertexDescriptor | j | ||
) | const |
Fetches an edge descriptor for a speculative edge from i to j.
Fetches an edge descriptor for the edge from i to j, and whether there is such an edge. If there is no such edge (i.e. the pair's second boolean is false), then using the EdgeDescriptor in other functions results in undefined behavior.
Complexity \(\Theta(1)\)
|
inline |
Allows const-ref access to the underlying matrix for debug purposes.
Complexity \(\Theta(1)\)
bool Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::hasExplicit | ( | const EdgeDescriptor & | edge | ) | const |
Checks if there is explicit information present for a left-to-right edge.
Complexity \(\Theta(1)\)
|
inlinestaticnoexcept |
Check if a vertex descriptor is part of the left subgraph.
Complexity \(\Theta(1)\)
|
noexcept |
Generates a bare distance bounds matrix by repeated shortest-paths calculations.
This function generates a matrix representing distance bounds, NOT a DistanceBoundsMatrix.
Complexity: O(N * O(shortest paths algorithm)) Complexity \(\Theta(V^2 \cdot E)\)
|
noexcept |
Generates a distance matrix by randomly fixing distances within triangle inequality bounds.
This function generates a distance matrix. For every pair of atomic indices a, b (traversed at random), a shortest-paths calculation is carried out to determine the triangle inequality limits between a and b. A random distance is chosen between these limits and added to the underlying graph.
The generation procedure is destructive, i.e. the same ImplicitBoundsGraph cannot be reused to generate multiple distance matrices.
Complexity \(\Theta(V^3 \cdot E)\). Benchmarked by analysis/BenchmarkGraphAlgorithms
NOTE: This double definition may seem strange, but is necessary to use the forward-declared enum class Partiality correctly.
|
noexcept |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
double Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::maximalImplicitLowerBound | ( | VertexDescriptor | i | ) | const |
Returns the length of the maximal implicit lower bound outgoing from a left vertex.
Complexity \(\Theta(1)\)
VertexDescriptor Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::num_edges | ( | ) | const |
Returns the number of edges currently simulated by the graph.
Returns the number of edges currently simulated by the graph.
Complexity \(\Theta(N^2)\)
VertexDescriptor Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::num_vertices | ( | ) | const |
Returns the number of vertices simulated by the graph, which is 2N.
Returns the number of vertices simulated by the graph, which is 2 * N
Complexity \(\Theta(1)\)
VertexDescriptor Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::out_degree | ( | VertexDescriptor | i | ) | const |
Returns the number of out-edges for a particular vertex.
Complexity \(\Theta(N)\)
|
inline |
Returns the source vertex from an edge descriptor.
Complexity \(\Theta(1)\)
|
inline |
Returns the target vertex from an edge descriptor.
Complexity \(\Theta(1)\)