Graph.h

Go to the documentation of this file.

 
#ifndef GRAPH_H
#define GRAPH_H
 
#include <algorithm>
#include <concepts>
#include <utility>
#include <vector>
 
template <typename T>
concept NodeConcept = requires(const T &n) {
  { n.getX() } -> std::same_as<int>;
  { n.getY() } -> std::same_as<int>;
  { n.getPosition() } -> std::same_as<std::pair<int, int>>;
};
 
template <typename U, typename T>
concept EdgeConcept = requires(const U &e) {
  { e.getFrom() } -> std::same_as<T>;
  { e.getTo() } -> std::same_as<T>;
  { e.getLength() } -> std::same_as<double>;
  { e.getMaxSpeed() } -> std::same_as<int>;
};
 
template <NodeConcept T, typename U>
  requires EdgeConcept<U, T>
class Graph {
public:
  Graph() = default;
 
  void addNode(const T &node) { nodes_.push_back(node); }
 
  void addEdge(const U &edge) { edges_.push_back(edge); }
 
  enum class AddEdgeResult {
    Success,       
    AlreadyExists, 
    Crosses        
  };
 
  AddEdgeResult addEdgeIfNotExists(const U &edge) {
    auto f = edge.getFrom().getPosition();
    auto t = edge.getTo().getPosition();
 
    if (isDuplicate(f, t))
      return AddEdgeResult::AlreadyExists;
 
    if (crossesAnyEdge(f, t))
      return AddEdgeResult::Crosses;
 
    edges_.push_back(edge);
    return AddEdgeResult::Success;
  }
 
  std::vector<T> getNodes() const { return nodes_; }
 
  std::vector<U> getEdges() const { return edges_; }
 
private:
  std::vector<T> nodes_; 
  std::vector<U> edges_; 
  static long long orient(const std::pair<int, int> &A,
                          const std::pair<int, int> &B,
                          const std::pair<int, int> &C) {
    return static_cast<long long>(B.first - A.first) * (C.second - A.second) -
           static_cast<long long>(B.second - A.second) * (C.first - A.first);
  }
 
  static bool onSegment(const std::pair<int, int> &A,
                        const std::pair<int, int> &B,
                        const std::pair<int, int> &C) {
    return std::min(A.first, B.first) <= C.first &&
           C.first <= std::max(A.first, B.first) &&
           std::min(A.second, B.second) <= C.second &&
           C.second <= std::max(A.second, B.second);
  }
 
  bool isDuplicate(const std::pair<int, int> &f,
                   const std::pair<int, int> &t) const {
    return std::any_of(edges_.begin(), edges_.end(), [&](auto const &e) {
      auto p = e.getFrom().getPosition();
      auto q = e.getTo().getPosition();
      return (p == f) && (q == t);
    });
  }
 
  bool segmentCrosses(const std::pair<int, int> &f,
                      const std::pair<int, int> &t,
                      const std::pair<int, int> &q1,
                      const std::pair<int, int> &q2) const {
    if (q1 == f || q1 == t || q2 == f || q2 == t)
      return false;
 
    long long o1 = orient(f, t, q1);
    long long o2 = orient(f, t, q2);
    long long o3 = orient(q1, q2, f);
    long long o4 = orient(q1, q2, t);
 
    if (((o1 > 0 && o2 < 0) || (o1 < 0 && o2 > 0)) &&
        ((o3 > 0 && o4 < 0) || (o3 < 0 && o4 > 0)))
      return true;
 
    if (o1 == 0 && onSegment(f, t, q1))
      return true;
    if (o2 == 0 && onSegment(f, t, q2))
      return true;
    if (o3 == 0 && onSegment(q1, q2, f))
      return true;
    if (o4 == 0 && onSegment(q1, q2, t))
      return true;
 
    return false;
  }
 
  bool crossesAnyEdge(const std::pair<int, int> &f,
                      const std::pair<int, int> &t) const {
    return std::any_of(edges_.begin(), edges_.end(), [&](auto const &e) {
      auto q1 = e.getFrom().getPosition();
      auto q2 = e.getTo().getPosition();
      return segmentCrosses(f, t, q1, q2);
    });
  }
};
 
#endif // GRAPH_H