GraphAlgorithms.h

Go to the documentation of this file.

 
#ifndef INCLUDE_MOLASSEMBLER_OUTER_GRAPH_ALGORITHMS_H
#define INCLUDE_MOLASSEMBLER_OUTER_GRAPH_ALGORITHMS_H
 
#include "Utils/Geometry/ElementTypes.h"
#include "Types.h"
#include "boost/functional/hash.hpp"
 
#include <unordered_map>
#include <vector>
#include <memory>
#include <limits>
 
namespace Scine {
namespace Molassembler {
 
// Forward-declarations
class Graph;
 
MASM_EXPORT std::vector<unsigned> distance(AtomIndex source, const Graph& graph);
 
struct MASM_EXPORT PredecessorMap {
  std::vector<AtomIndex> predecessors;
 
  std::vector<AtomIndex> path(AtomIndex target) const;
};
 
MASM_EXPORT PredecessorMap shortestPaths(AtomIndex source, const Graph& graph);
 
struct MASM_EXPORT EditCost {
  virtual ~EditCost() = default;
 
  // Alteration means insertion or deletion
  virtual unsigned vertexAlteration() const = 0;
  virtual unsigned edgeAlteration() const = 0;
  virtual unsigned elementSubstitution(Utils::ElementType from, Utils::ElementType to) const = 0;
  virtual unsigned bondSubstitution(BondType from, BondType to) const = 0;
};
 
struct MASM_EXPORT FuzzyCost : public EditCost {
  unsigned vertexAlteration() const override { return 1; }
  unsigned edgeAlteration() const override { return 1; }
  unsigned elementSubstitution(Utils::ElementType from, Utils::ElementType to) const override {
    return (from != to) ? 1 : 0;
  }
  unsigned bondSubstitution(BondType from, BondType to) const override {
    return (from != to) ? 1 : 0;
  }
};
 
struct MASM_EXPORT ElementsConservedCost : public FuzzyCost {
  unsigned vertexAlteration() const override { return 100; }
  unsigned elementSubstitution(Utils::ElementType from, Utils::ElementType to) const override {
    return (from != to) ? 100 : 0;
  }
};
 
struct MASM_EXPORT MinimalGraphEdits {
  using IndexMap = std::vector<AtomIndex>;
 
  struct VertexEdit {
    VertexEdit() = default;
    VertexEdit(AtomIndex i, AtomIndex j, unsigned c) : first(i), second(j), cost(c) {}
 
    AtomIndex first;
    AtomIndex second;
    unsigned cost;
  };
 
  struct EdgeEdit {
    EdgeEdit() = default;
    EdgeEdit(BondIndex i, BondIndex j, unsigned c) : first(i), second(j), cost(c) {}
 
    BondIndex first;
    BondIndex second;
    unsigned cost;
  };
 
  static constexpr AtomIndex epsilon = std::numeric_limits<AtomIndex>::max();
 
  unsigned distance;
  IndexMap indexMap;
  std::vector<VertexEdit> vertexEdits;
  std::vector<EdgeEdit> edgeEdits;
};
 
MASM_EXPORT MinimalGraphEdits minimalEdits(const Graph& a, const Graph& b, const EditCost& cost = FuzzyCost {});
 
struct MASM_EXPORT MinimalReactionEdits {
  using ComponentIndexPair = std::pair<unsigned, AtomIndex>;
 
  struct VertexEdit {
    VertexEdit() = default;
    VertexEdit(ComponentIndexPair i, ComponentIndexPair j, unsigned c)
      : first(std::move(i)), second(std::move(j)), cost(c) {}
 
    ComponentIndexPair first;
    ComponentIndexPair second;
    unsigned cost;
  };
 
  struct EdgeEdit {
    using ComponentBondIndex = std::pair<ComponentIndexPair, ComponentIndexPair>;
 
    EdgeEdit() = default;
    EdgeEdit(ComponentBondIndex i, ComponentBondIndex j, unsigned c)
      : first(std::move(i)), second(std::move(j)), cost(c) {}
 
    ComponentBondIndex first;
    ComponentBondIndex second;
    unsigned cost;
  };
 
  unsigned distance;
  std::unordered_map<ComponentIndexPair, ComponentIndexPair, boost::hash<ComponentIndexPair>> indexMap;
  std::vector<VertexEdit> vertexEdits;
  std::vector<EdgeEdit> edgeEdits;
};
 
using GraphList = std::vector<std::reference_wrapper<Graph>>;
 
MASM_EXPORT MinimalReactionEdits reactionEdits(const GraphList& lhsGraphs, const GraphList& rhsGraphs);
 
std::string reactionGraphvizSvg(
  const GraphList& lhs,
  const GraphList& rhs,
  const MinimalReactionEdits& edits
);
 
} // namespace Molassembler
} // namespace Scine
 
#endif