Terminates a BGL Dijkstra search as soon as 1/ a single vertex is found or 2/ multiple vertices are found

terminate_early.cc

#pragma once

#include <iterator>
#include <unordered_set>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>


namespace simplerouter {

  // Signals early termination for an algorithm from within a visitor.
  struct stopSearchSignal final {};


  // Stops Dijkstra's algorithm as soon as we are done with a single target.
  // Throws stopOneToOneSearchSignal.
  template <typename Graph>
  struct stopOnTarget final : boost::default_dijkstra_visitor {
    using Vertex = typename boost::graph_traits<Graph>::vertex_descriptor;

    explicit stopOnTarget(const Vertex target_) : target{target_} {}

    void examine_vertex(const Vertex vertex, const Graph&) const {
      if (vertex == target)
        throw stopSearchSignal{};
    };

    Vertex target;
  };


  // Stops Dijkstra's algorithm as soon as we are done with all targets.
  // Throws stopManyToManyOnLastTarget.
  template <typename Graph, typename Vertices>
  struct stopOnTargets final : boost::default_dijkstra_visitor {
    using Vertex = typename boost::graph_traits<Graph>::vertex_descriptor;

    explicit stopOnTargets(const Vertices targets_) : targets{begin(targets_), end(targets_)} {}

    void examine_vertex(const Vertex vertex, const Graph&) {
      targets.erase(vertex);

      if (targets.empty())
        throw stopSearchSignal{};
    };

    std::unordered_set<Vertex> targets;
  };
}