paths.hpp

Go to the documentation of this file.

#include "../../utils/fwd_declares.hpp"

#include <map>
#include <vector>

#ifndef INDIGOX_ALGORITHM_GRAPH_PATHS_HPP
#define INDIGOX_ALGORITHM_GRAPH_PATHS_HPP

namespace indigox::algorithm {

  template <class V, class E, class S, class D, class VP, class EP>
  std::vector<E> ShortestPath(graph::BaseGraph<V, E, S, D, VP, EP> &G, V source,
                              V target);

  template <class V, class E, class S, class D, class VP, class EP>
  void AllSimplePaths(graph::BaseGraph<V, E, S, D, VP, EP> &G, V source,
                      V target, std::vector<std::vector<E>> &paths,
                      int64_t limit = -1);

  template <class V> struct TraversalResults {
    using OrderType = typename std::vector<V>;
    using PredType = typename std::map<V, V>;
    using LengthType = typename std::map<V, int32_t>;
    OrderType discover_order;
    PredType predecessors;
    LengthType path_lengths;
    V furthest;

    TraversalResults(OrderType &order, PredType &pred, LengthType &length,
                     V &far)
        : discover_order(order), predecessors(pred), path_lengths(length),
          furthest(far) {}
  };

  template <class V, class E, class S, class D, class VP, class EP>
  TraversalResults<V> DepthFirstSearch(graph::BaseGraph<V, E, S, D, VP, EP> &G,
                                       V source = V(), int64_t limit = -1);

  template <class V, class E, class S, class D, class VP, class EP>
  TraversalResults<V>
  BreadthFirstSearch(graph::BaseGraph<V, E, S, D, VP, EP> &G, V source = V(),
                     int64_t limit = -1);
} // namespace indigox::algorithm

#endif /* INDIGOX_ALGORITHM_GRAPH_PATHS_HPP */