2
\$\begingroup\$

I wrote an improvement from my previous graph class: Link


#include <algorithm>
#include <concepts>
#include <list>
#include <map>
#include <ranges>
#include <unordered_map>
#include <unordered_set>
#include <stdexcept>
#include <vector>


namespace frozenca {

template <typename T>
concept Arithmetic = std::is_arithmetic_v<T>;

template <typename T>
concept Descriptor = std::is_default_constructible_v<T> && std::is_assignable_v<T &, T> &&
    std::equality_comparable<T>;

template <typename Derived> struct EdgePropertyTag {};

struct EdgeWeightTag : public EdgePropertyTag<EdgeWeightTag> {};

EdgeWeightTag e_w;

template <typename Derived> struct VertexPropertyTag {};

struct VertexDistanceTag : public VertexPropertyTag<VertexDistanceTag> {};

VertexDistanceTag v_dist;

template <typename Derived> struct EmptyProperty {
  void operator()() const noexcept {
    // do nothing
  }
};

template <Descriptor VertexType, typename Traits, typename Properties>
class Graph : public Traits::template Impl<VertexType>,
              public Properties::template Impl<VertexType> {
public:
  using TraitBase = Traits::template Impl<VertexType>;

  using TraitBase::add_edge;
  using TraitBase::add_vertex;
  using TraitBase::adj;
  using TraitBase::has_edge;
  using TraitBase::has_vertex;
  using TraitBase::vertices;
};

template <Descriptor Vertex, typename Derived> struct AdjListTraits {
  using vertex_type = Vertex;
  using vertices_type = std::unordered_set<vertex_type>;
  using vertex_iterator_type = vertices_type::iterator;

  using edge_type = std::pair<vertex_type, vertex_type>;
  using adj_list_type = std::list<edge_type>;
  using edges_type = std::list<adj_list_type>;
  using edge_iterator_type = adj_list_type::iterator;
  using const_edge_iterator_type = adj_list_type::const_iterator;
  using out_edges_type =
      std::unordered_map<vertex_type, typename edges_type::iterator>;

  vertices_type vertices_;
  edges_type edges_;
  out_edges_type out_edges_;

  const auto &vertices() const noexcept { return vertices_; }

  void add_vertex(const vertex_type &vertex) {
    vertices_.insert(vertex);
    if (!out_edges_.contains(vertex)) {
      edges_.emplace_front();
      out_edges_.emplace(vertex, edges_.begin());
    }
  }

  bool has_vertex(const vertex_type &vertex) const {
    return vertices_.contains(vertex);
  }

  std::ranges::subrange<edge_iterator_type, edge_iterator_type>
  adj(const vertex_type &vertex) {
    return *out_edges_.at(vertex);
  }

  std::ranges::subrange<const_edge_iterator_type, const_edge_iterator_type>
  adj(const vertex_type &vertex) const {
    return *out_edges_.at(vertex);
  }

  bool has_edge(const edge_type &edge) const {
    auto edge_range = adj(edge.first);
    return std::ranges::find(edge_range, edge) != edge_range.end();
  }

  void add_edge(const vertex_type &src, const vertex_type &dst) {
    out_edges_[src]->emplace_front(src, dst);
  }
};

struct AdjListTraitTag {
  template <Descriptor VertexType, typename Derived>
  using Trait = AdjListTraits<VertexType, Derived>;
};

template <Descriptor VertexType, bool Directed, typename ContainerTraitTag>
struct GraphTraitsImpl
    : public ContainerTraitTag::template Trait<
          VertexType,
          GraphTraitsImpl<VertexType, Directed, ContainerTraitTag>> {
  using vertex_type = VertexType;
  using Base = ContainerTraitTag::template Trait<
      VertexType, GraphTraitsImpl<VertexType, Directed, ContainerTraitTag>>;
  static constexpr bool directed_ = Directed;

  using Base::add_vertex;
  using Base::adj;
  using Base::has_edge;
  using Base::has_vertex;
  using Base::vertices;

  void add_edge(const vertex_type &src, const vertex_type &dst) {
    add_vertex(src);
    add_vertex(dst);
    Base::add_edge(src, dst);
    if constexpr (!directed_) {
      Base::add_edge(dst, src);
    }
  }
};

template <bool Directed, typename ContainerTraitTag> struct GraphTraits {
  template <Descriptor VertexType>
  using Impl = GraphTraitsImpl<VertexType, Directed, ContainerTraitTag>;
};

template <typename ContainerTraitTag>
using DiGraphTraits = GraphTraits<true, ContainerTraitTag>;

template <Descriptor VertexType, typename... BaseProperties>
struct GraphProperties : public BaseProperties::template Impl<VertexType>... {
  using BaseProperties::template Impl<VertexType>::operator()...;
};

template <Arithmetic WeightType, typename EdgeType> struct EdgeWeightImpl {
  WeightType &operator()(EdgeWeightTag, const EdgeType &edge) {
    return weights_[edge];
  }
  const WeightType &operator()(EdgeWeightTag, const EdgeType &edge) const {
    return weights_.at(edge);
  }

  std::map<EdgeType, WeightType> weights_;
};

template <Arithmetic WeightType> struct EdgeWeightProperty {
  template <Descriptor VertexType>
  using Impl = EdgeWeightImpl<WeightType, std::pair<VertexType, VertexType>>;
};

template <Arithmetic DistanceType, Descriptor VertexType>
struct VertexDistanceImpl {

  DistanceType &operator()(VertexDistanceTag, const VertexType &vertex) {
    return distances_[vertex];
  }
  const DistanceType &operator()(VertexDistanceTag,
                                 const VertexType &vertex) const {
    return distances_.at(vertex);
  }

  std::unordered_map<VertexType, DistanceType> distances_;
};

template <Arithmetic DistanceType> struct VertexDistanceProperty {
  template <Descriptor VertexType>
  using Impl = VertexDistanceImpl<DistanceType, VertexType>;
};

template <Arithmetic DistType> struct DijkstraProperties {
  template <Descriptor VertexType>
  using Impl = GraphProperties<VertexType, VertexDistanceProperty<DistType>,
                               EdgeWeightProperty<DistType>>;
};

} // namespace frozenca

Test code(Dijkstra's algorithm):

#include <graph.h>
#include <iostream>
#include <limits>
#include <vector>
#include <queue>


namespace fc = frozenca;

using DijkstraGraph = fc::Graph<int, fc::DiGraphTraits<fc::AdjListTraitTag>, fc::DijkstraProperties<float>>;

std::pair<float, int> dijkstra(DijkstraGraph &g, int src) {
  auto min_dist_comp = [&g](int v1, int v2) {
    return g(fc::v_dist, v1) > g(fc::v_dist, v2);
  };

  constexpr auto INF = std::numeric_limits<float>::max();

  std::priority_queue<int, std::vector<int>, decltype(min_dist_comp)> q(min_dist_comp);
  for (auto vertex : g.vertices()) {
    g(fc::v_dist, vertex) = INF;
  }
  

  int min_dst = -1;
  float min_dist = INF;

  g(fc::v_dist, src) = 0;
  q.push(src);
  while (!q.empty()) {
    auto u = q.top();
    q.pop();

    for (auto [_, v] : g.adj(u)) {
      auto alt = g(fc::v_dist, u) + g(fc::e_w, {u, v});
      if (alt < g(fc::v_dist, v) && g(fc::v_dist, u) != INF) {
        g(fc::v_dist, v) = alt;
        min_dst = v;
        min_dist = std::min(min_dist, alt);
      }
    }
  }
  return {min_dist, min_dst};
}

int main() {
  DijkstraGraph g;

  g.add_edge(0, 2);
  g.add_edge(1, 3);
  g.add_edge(1, 4);
  g.add_edge(2, 1);
  g.add_edge(2, 3);
  g.add_edge(3, 4);
  g.add_edge(4, 0);
  g.add_edge(4, 1);

  g(fc::e_w, {0, 2}) = 1;
  g(fc::e_w, {1, 3}) = 1;
  g(fc::e_w, {1, 4}) = 2;
  g(fc::e_w, {2, 1}) = 7;
  g(fc::e_w, {2, 3}) = 3;
  g(fc::e_w, {3, 4}) = 1;
  g(fc::e_w, {4, 0}) = 1;
  g(fc::e_w, {4, 1}) = 1;

  auto [dist, dst] = dijkstra(g, 0);
  std::cout << "Shortest distance: " << dist << " with destination " << dst << '\n';
}

Output

Shortest distance: 1 with destination 2

I'm not sure I can handle this TMP monstrosity...

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Miscellaneous issues

  • You can use [] instead of .at() in the non-const adj().
  • #include <vector> is not necessary.
  • #include <graph.h> is dangerous, use "graph.h" instead, otherwise you risk a graph.h that's in the system header search path from being found before your local header file.

Store adjacency lists directly in out_edges_

I don't see why you have a std::list storing adjacency lists, and a std::unordered_map that maps vertices to iterators into that std::list. Why not store the adjacency lists directly in the std::unordered_map? This simplifies the code.

Use of std::list

A std::list has the problem that looking up things is slow. Consider has_edge(), which has \$O(V)\$ complexity because it has to do a linear search.

Use of std::map

Nothing in EdgeWeightImpl depends on weights_ being sorted. So ideally, you would use a std::unordered_map instead. Of course, the issue is that there is no overload for std::hash for EdgeType. However, you could make one yourself, or pass a custom hash function to the constructor of weights_ if you make it a std::unordered_map.

Make things private where appropriate

If you add accessor functions to a struct or class to access its member variables, I expect those member variables to be private. Even if some of your structs are only used internally, it is good practice to use public/protected/private to reduce bugs in your own code.

Missing typename?

C++20 is supposed to reduce the need for writing typename. I am not a language lawyer, so I won't comment on whether your code is techinally correct, however Clang seems to think typename is missing in some of your using declarations. So from a practical standpoint, add typename whenever there is a dependent type to avoid compiler issues.

Naming things

There are a few things I would do differently regarding naming. First, adding Type to template parameter names seems unnecessary; you already make them start with a capital so they are easily distinguished from the (member) variables. I think it just adds noise.

Properties vs traits: these words mean very similar things. Without reading the code, I wouldn't know where to put what if I had to create a custom trait and a custom property class.

DijkstraProperties is misnamed and hints at possible issues. First, there might be other algorithms that work on a graph that has edge weights and vertex distances. You might also want to run multiple algorithms on a given graph. Naming a graph type after one of the possible algorithms you could use on it doesn't seem like a good idea. Furthermore, storing information in a graph that is only used while a given algorithm runs on it wastes memory when you are not running that algorithm, and also prevents you from running that algorithm on a const graph. Of course, if you run Dijkstra's a lot and it's the fastest way to do it, it is fine, but I wouldn't expect this from such a generic graph library.

Usability

I'm not sure I can handle this TMP monstrosity...

It's just lots of templates, I don't see any real metaprogramming here. But yes, it's a bit of a monstrosity. And while the end-user doesn't have to look at the implementation, they still have to write things like this:

using DijkstraGraph = fc::Graph<int, fc::DiGraphTraits<fc::AdjListTraitTag>, fc::DijkstraProperties<float>>;

Which doesn't look particularly appealing. Again, I don't think it's clear what the distinction between the Trait and Property is, so I'd much rather see Graph having just one template parameter that contains all the information necessary. That type will then be more complicated of course, but with some real template meta-programming you can have it deduce many of the traits and properties instead of having to explicitly specify them.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Thanks as always, for minor things, has_edge() is at most O(V) because it scans the edge from only out edges from the source vertex of the edge. For encapsulation, I changed inheritance of Graph from Traits and Properties from public to private inheritance. For typename, Clang still doesn't support P0634R3 as of clang15 (en.cppreference.com/w/cpp/compiler_support) \$\endgroup\$
    – frozenca
    Jul 30, 2022 at 9:33
  • 1
    \$\begingroup\$ I'm considering extracting out Properties from Graph, IMO Graph should only hold the references to Properties only if necessary, and users have to be free to put on and off Properties, they shouldn't restrict Graph's type system. Binding Properties to Graph's type system was an idea inspired from Boost.Graph, but after coding, I thought that design decision was a big mistake \$\endgroup\$
    – frozenca
    Jul 30, 2022 at 9:36
  • \$\begingroup\$ Oops, it's indeed \$O(V)\$. private inheritance is already good, but you could also make the member variables of AdjListTraits private for example, and it will still compile. As for Boost Graph, the first release was apparently in 2000, so they had to work with C++98. I guess a lot of design decisions came from the limitations of the language at that time. \$\endgroup\$
    – G. Sliepen
    Jul 30, 2022 at 9:56
  • \$\begingroup\$ I separated Properties from Graph's type system now, Graph now holds a member variable std::map<GraphPropertyTag, std::unique_ptr<PropertyMap>>. GraphPropertyTag is now just a enum class, all property maps inherit PropertyMap \$\endgroup\$
    – frozenca
    Jul 30, 2022 at 10:13
  • \$\begingroup\$ There are now just three bases classes for PropertyMap: VertexProperty, EdgeProperty and GraphProperty, all three inherit PropertyMap, and all of them are parametrized \$\endgroup\$
    – frozenca
    Jul 30, 2022 at 10:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.