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