2
\$\begingroup\$

This is yet another improvement from my graph class - Link

Now property maps are no longer parts of Graph type, they are just stored in a member variable.

This seems much more reasonable for me! It is wise to combine dynamic polymorphism and static polymorphism appropriately.

#include "GraphProperties.h"
#include <memory>
#include <concepts>

template <typename T>
concept GraphConcept = T::is_graph_;

template <typename T>
concept DiGraphConcept = GraphConcept<T> && T::directed_;


template <Descriptor VertexType, typename Traits>
class Graph : private Traits::template Impl<VertexType> {
public:
  using TraitBase = Traits::template Impl<VertexType>;
  using vertex_type = TraitBase::vertex_type;
  using edge_type = TraitBase::edge_type;
  static constexpr bool directed_ = TraitBase::directed_;
  static constexpr bool is_graph_ = true;

  Graph() : TraitBase() {}

  void add_vertex(const vertex_type &v) { TraitBase::add_vertex(v); }

  void add_edge(const vertex_type &src, const vertex_type &dst) {
    TraitBase::add_edge(src, dst);
  }

  auto adj(const vertex_type &src) { return TraitBase::adj(src); }

  auto adj(const vertex_type &src) const { return TraitBase::adj(src); }

  const auto &vertices() const noexcept { return TraitBase::vertices(); }

  [[nodiscard]] auto size() const noexcept {
    return TraitBase::vertices().size();
  }

  const auto &edges() const noexcept { return TraitBase::edges(); }

  const auto &out_edges() const noexcept { return TraitBase::out_edges(); }

  bool has_vertex(const vertex_type &src) const noexcept {
    return TraitBase::has_vertex(src);
  }

  bool has_edge(const edge_type &edge) const noexcept {
    return TraitBase::has_edge(edge);
  }

  template <typename PropertyType>
  VertexProperty<PropertyType, vertex_type> &
  add_vertex_property(const GraphPropertyTag &tag) {
    properties_.emplace(
        tag, std::make_unique<VertexProperty<PropertyType, vertex_type>>());
    return get_vertex_property<PropertyType>(tag);
  }

  template <typename PropertyType>
  EdgeProperty<PropertyType, edge_type> &
  add_edge_property(const GraphPropertyTag &tag) {
    properties_.emplace(tag,
                        std::make_unique<EdgeProperty<PropertyType, edge_type>>());
    return get_edge_property<PropertyType>(tag);
  }

  template <typename PropertyType>
  GraphProperty<PropertyType> &add_graph_property(const GraphPropertyTag &tag) {
    properties_.emplace(tag, std::make_unique<GraphProperty<PropertyType>>());
    return get_graph_property<PropertyType>(tag);
  }

  template <typename PropertyType>
  VertexProperty<PropertyType, vertex_type> &
  get_vertex_property(const GraphPropertyTag &tag) {
    return dynamic_cast<VertexProperty<PropertyType, vertex_type> &>(
        *properties_.at(tag));
  }

  template <typename PropertyType>
  const VertexProperty<PropertyType, vertex_type> &
  get_vertex_property(const GraphPropertyTag &tag) const {
    return dynamic_cast<const VertexProperty<PropertyType, vertex_type> &>(
        *properties_.at(tag));
  }

  template <typename PropertyType>
  EdgeProperty<PropertyType, edge_type> &
  get_edge_property(const GraphPropertyTag &tag) {
    return dynamic_cast<EdgeProperty<PropertyType, edge_type> &>(
        *properties_.at(tag));
  }

  template <typename PropertyType>
  const EdgeProperty<PropertyType, edge_type> &
  get_edge_property(const GraphPropertyTag &tag) const {
    return dynamic_cast<const EdgeProperty<PropertyType, edge_type> &>(
        *properties_.at(tag));
  }

  template <typename PropertyType>
  GraphProperty<PropertyType> &get_graph_property(const GraphPropertyTag &tag) {
    return dynamic_cast<GraphProperty<PropertyType> &>(*properties_.at(tag));
  }

  template <typename PropertyType>
  const GraphProperty<PropertyType> &
  get_graph_property(const GraphPropertyTag &tag) const {
    return dynamic_cast<const GraphProperty<PropertyType> &>(
        *properties_.at(tag));
  }

private:
  std::unordered_map<GraphPropertyTag, std::unique_ptr<Property>> properties_;
};

// omit AdjList Traits

GraphProperties.h

#include <bit>
#include <functional>
#include <vector>
#include <unordered_map>
#include <type_traits>



enum class GraphPropertyTag : std::int32_t {
  VertexDistance,
  VertexVisited,
  VertexRank,
  VertexSize,
  VertexParent,
  VertexLink,
  EdgeWeight,
  GraphTopSort,
};

template<> struct std::hash<GraphPropertyTag> {
  std::size_t operator()(const GraphPropertyTag &tag) const {
    return std::hash<std::uint32_t>{}(std::bit_cast<std::uint32_t>(tag));
  }
};

struct Property {
  virtual ~Property() {}
};

enum class VisitMark {
  Unvisited,
  Visiting,
  Visited
};

template <typename PropertyType, Descriptor VertexType>
struct VertexProperty final : public Property {

  static constexpr bool int_vertex_ = std::is_integral_v<VertexType>;

  PropertyType &operator()(const VertexType &vertex) {
    if constexpr (int_vertex_) {
      if (vertex >= std::ssize(vertex_properties_)) {
        vertex_properties_.resize(vertex + 1);
      }
    }
    return vertex_properties_[vertex];
  }
  const PropertyType &operator()(const VertexType &vertex) const {
    return vertex_properties_.at(vertex);
  }

private:
  std::conditional_t<int_vertex_, std::vector<PropertyType>,
                std::unordered_map<VertexType, PropertyType>>
      vertex_properties_;
};

template <typename PropertyType, typename EdgeType>
struct EdgeProperty final : public Property {
  PropertyType &operator()(const EdgeType &edge) {
    return edge_properties_[edge];
  }
  const PropertyType &operator()(const EdgeType &edge) const {
    return edge_properties_.at(edge);
  }

private:
  std::unordered_map<EdgeType, PropertyType, std::hash<EdgeType>> edge_properties_;
};

template <typename PropertyType>
struct GraphProperty final : public Property {
  PropertyType& operator()() {
    return graph_property_;
  }

  const PropertyType& operator()() const {
    return graph_property_;
  }
private:
  PropertyType graph_property_;
};

Topological sort example


template <DiGraphConcept DiGraphType>
bool topological_sort_helper(
    DiGraphType &g,
    VertexProperty<VisitMark, typename DiGraphType::vertex_type> &visited,
    GraphProperty<std::list<typename DiGraphType::vertex_type>> &top_sort,
    const typename DiGraphType::vertex_type &vertex) {
  visited(vertex) = VisitMark::Visiting;

  for (const auto &[_, dst] : g.adj(vertex)) {
    auto status = visited(dst);
    if (status == VisitMark::Unvisited) {
      if (!topological_sort_helper(g, visited, top_sort, dst)) {
        top_sort().clear();
        return false;
      }
    } else if (status == VisitMark::Visiting) {
      std::cerr << "Not a DAG, can't topological sort\n";
      top_sort().clear();
      return false;
    }
  }
  visited(vertex) = VisitMark::Visited;
  top_sort().push_back(vertex);
  return true;
}

template <DiGraphConcept DiGraphType> void topological_sort(DiGraphType &g) {
  using vertex_type = DiGraphType::vertex_type;

  auto &visited =
      g.add_vertex_property<VisitMark>(GraphPropertyTag::VertexVisited);
  auto &top_sort =
      g.add_graph_property<std::list<vertex_type>>(GraphPropertyTag::GraphTopSort);

  for (const auto &vertex : g.vertices()) {
    if (visited(vertex) == VisitMark::Unvisited) {
      topological_sort_helper(g, visited, top_sort, vertex);
    }
  }
}

Union Find example

template <Descriptor V>
void make_set(VertexProperty<V, V> &parent, VertexProperty<int, V> &rank,
              VertexProperty<V, V> &link, const V &vertex) {
  parent(vertex) = vertex;
  rank(vertex) = 0;
  link(vertex) = vertex;
}

template <Descriptor V>
V find_set(UndirGraph<V> &g, VertexProperty<V, V> &parent, const V &v) {
  if (parent(v) != v) {
    parent(v) = find_set(g, parent, parent(v));
  }
  return parent(v);
}

template <Descriptor V>
void link_by_size(VertexProperty<V, V> &parent, VertexProperty<int, V> &rank,
                  VertexProperty<V, V> &link, const V &x, const V &y) {
  auto temp = link(y);
  link(y) = link(x);
  link(x) = temp;
  if (rank(x) > rank(y)) {
    parent(y) = x;
  } else {
    parent(x) = y;
    if (rank(x) == rank(y)) {
      rank(y) += rank(x);
    }
  }
}

template <Descriptor V> void union_find_by_size(UndirGraph<V> &g) {
  auto &parent = g.add_vertex_property<V>(GraphPropertyTag::VertexParent);
  auto &rank = g.add_vertex_property<int>(GraphPropertyTag::VertexRank);
  auto &link = g.add_vertex_property<V>(GraphPropertyTag::VertexLink);
  for (const auto &vertex : g.vertices()) {
    make_set(parent, rank, link, vertex);
  }

  for (const auto &v : g.vertices()) {
    for (const auto &[_, u] : g.adj(v)) {
      auto vr = find_set(g, parent, v);
      auto ur = find_set(g, parent, u);
      link_by_size(parent, rank, link, vr, ur);
    }
  }
}
```
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

This is certainly an interesting way to have a generic graph class that is dynamically extensible. It's very nice to be able to write code like visited(vertex) = ....

Use more [[nodiscard]]

I see you use [[nodiscard]] for size(), but there are many more functions where [[nodiscard]] would be appropriate.

No need to overload std::hash for enums

std::hash already has specializations for all possible enum types, you don't need to specialize it for GraphPropertyTag.

Consider using operator[] instead of operator() for properties

Since a graph is like a container, I think it feels more natural to use bracket notation to access its elements. Since everything has to be accessed via properties, I would add operator[] member functions to them instead of operator().

\$\endgroup\$
1
  • \$\begingroup\$ Yup, my friend bashed me for using operator() instead of operator[], because not only it confuses notational convention, but also declaring operator() makes it a callable object. Current code is like this: github.com/frozenca/CLRS/blob/main/core/… \$\endgroup\$
    – frozenca
    Commented Aug 3, 2022 at 1:07

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.