8
\$\begingroup\$

As a personal side project I started building a graph library in C++ (I know, very original). The code is open source, but for the purpose of this question I will provide the relevant details and the to-be reviewed code below.

Architecture overview

What I want to achieve

The goal of the project is to make a lightweight general-purpose graph library in C++. I do not have particular use cases in mind and therefore want to keep everything as general and easily extendible as possible.

Main classes and data structures

The main class of the library is the abstract graph class (who would have guessed):

enum class edge_type { WEIGHTED, UNWEIGHTED };
enum class graph_spec { DIRECTED, UNDIRECTED };

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V, graph_spec GRAPH_SPEC_V>
class graph {...};

An instance of a graph can have user provided types for the vertices and edges. Internally, it stores the graph in an adjacency list, and has separate containers for the vertex and edge instances.

There are two classes which publicly derive from graph:

  • directed_graph
  • undirected_graph

They provide implementations for the pure virtual methods related to handling edges. The undirected_graph first sorts the pair of vertex ids related to an edge before interacting with the internal edges_ data structure. This ensures that an edge a->b is the same as an edge from b->a.

Weighted graphs

Certain algorithms (such as A*) operate on weighted graphs. To instantiate a weighted graph, an enum value edge_type needs to be passed when constructing either a directed_graph or an undirected_graph:

enum class edge_type { WEIGHTED, UNWEIGHTED };

directed_graph<int, float, edge_type::WEIGHTED> my_graph{};

Since the edge type is passed as a template parameter, we need a common interface for determining the weight of an edge.

In the context of a weighted graph, this edge type can either be a primitive numeric type or a user defined classes. To provide a common interface between the two, a user defined class must publicly inherit from weighted_edge and implement the pure virtual get_weight method.

When a primitive numeric is used for the edge type, it is automatically wrapped in a primitive_numeric_adapter, which inherits from weighted_edge.

Since we rely on inheritance here, these edges are internally stored as std::shared_ptr<weighted_edge<T>>. Calling my_graph.get_edge(v1, v2) returns a shared pointer to the weighted_edge.

Design choices I am unsure about

  1. Handling of directed/undirected and weighted/unweighted graphs
    Directed and undirected graphs are handled through inheritance, while the weighted graphs are handled using tag dispatch. I am not completely satisfied with mixing and matching these two different approaches.
  2. Interface for weighted edges
    Calling get_edge on an unweighted graph yield a reference to the passed template type EDGE_T. Calling that same get_edge on a weighted graph yields an std::shared_ptr<weighted_edge<t>>.

If you have any opinion or solution to the above two points I would be very happy to hear it.

Code to be reviewed

Here I would like to focus on the graph class and the undirected_graph class.

types.h

#pragma once

#include <cstddef>
#include <functional>
#include <utility>

namespace graaf {

using vertex_id_t = std::size_t;
using edge_id_t = std::pair<vertex_id_t, vertex_id_t>;

struct edge_id_hash {
  [[nodiscard]] std::size_t operator()(const edge_id_t& key) const {
    const auto h1{std::hash<vertex_id_t>{}(key.first)};
    const auto h2{std::hash<vertex_id_t>{}(key.second)};

    // TODO: use something like boost::hash_combine
    return h1 ^ h2;
  }
};

/**
 * @brief Interface for a weighted edge.
 *
 * This is what is stored internally and returned from a weighted graph in
 * order to make sure each edge in a weighted graph has a common interface to
 * extract the weight.
 *
 * @tparam WEIGHT_T The type of the weight.
 */
template <typename WEIGHT_T>
class weighted_edge {
 public:
  [[nodiscard]] virtual WEIGHT_T get_weight() const noexcept = 0;
};

/**
 * @brief Adapter for a weighted edge which wraps a primitive type.
 *
 * Weighted graphs support having primitive numeric types for the edges.
 * In this case, the edges are internally wrapped in this adapter to provide a
 * common interface for weighted edges.
 *
 * @tparam WEIGHT_T The type of the weight.
 */
template <typename WEIGHT_T>
class primitive_numeric_adapter final : public weighted_edge<WEIGHT_T> {
 public:
  explicit primitive_numeric_adapter(WEIGHT_T value) : value_{value} {}

  [[nodiscard]] WEIGHT_T get_weight() const noexcept override { return value_; }

 private:
  WEIGHT_T value_{};
};

}  // namespace graaf

graph.h

#pragma once

#include <graaflib/types.h>

#include <memory>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

namespace graaf {

namespace detail {

// Type trait to check if the type is a primitive numeric type
template <typename T>
struct is_primitive_numeric;

// Type trait to check if a type derives from weighted_edge
template <typename T>
struct is_weighted_edge;

}  // namespace detail

enum class edge_type { WEIGHTED, UNWEIGHTED };
enum class graph_spec { DIRECTED, UNDIRECTED };

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V,
          graph_spec GRAPH_SPEC_V>
class graph {
  using weighted_edge_t =
      std::conditional_t<detail::is_primitive_numeric<EDGE_T>::value,
                         std::shared_ptr<primitive_numeric_adapter<EDGE_T>>,
                         std::shared_ptr<EDGE_T>>;

  static_assert(EDGE_TYPE_V == edge_type::UNWEIGHTED ||
                detail::is_weighted_edge<
                    typename weighted_edge_t::element_type>::impl::value);

 public:
  using vertex_t = VERTEX_T;

  using edge_t = std::conditional_t<EDGE_TYPE_V == edge_type::UNWEIGHTED,
                                    EDGE_T, weighted_edge_t>;

  using vertices_t = std::unordered_set<vertex_id_t>;

  using vertex_id_to_vertex_t = std::unordered_map<vertex_id_t, VERTEX_T>;
  using edge_id_to_edge_t = std::unordered_map<edge_id_t, edge_t, edge_id_hash>;

  /**
   * Checks whether graph is directed.
   *
   * @return bool - Return true for directed graphs otherwise false
   */
  [[nodiscard]] constexpr bool is_directed() const {
    return GRAPH_SPEC_V == graph_spec::DIRECTED;
  }

  /**
   * Checks whether graph is undirected.
   *
   * @return bool - Returns true for undirected graphs otherwise false
   */
  [[nodiscard]] constexpr bool is_undirected() const {
    return GRAPH_SPEC_V == graph_spec::UNDIRECTED;
  }

  /**
   * Checks whether the edges of a graph are weighted.
   *
   * @return bool
   */
  [[nodiscard]] constexpr bool is_weighted() const {
    return EDGE_TYPE_V == edge_type::WEIGHTED;
  }

  /**
   * Checks whether the edges of a graph are unweighted.
   *
   * @return bool
   */
  [[nodiscard]] constexpr bool is_unweighted() const {
    return EDGE_TYPE_V == edge_type::UNWEIGHTED;
  }

  /**
   * Query the number of vertices
   *
   * @return size_t - Number of vertices
   */
  [[nodiscard]] std::size_t vertex_count() const noexcept;

  /**
   * Query the number of edges
   *
   * @return size_t - Number of edges
   */
  [[nodiscard]] std::size_t edge_count() const noexcept;

  [[nodiscard]] const vertex_id_to_vertex_t& get_vertices() const noexcept {
    return vertices_;
  }

  [[nodiscard]] const edge_id_to_edge_t& get_edges() const noexcept {
    return edges_;
  }

  /**
   * Checks whether a vertex with a given ID is contained in the graph.
   *
   * @param  vertex_id The ID of the vertex we want to check
   * @return boolean - This return Ture to indicate the vertex is contained in
   * the graph otherwise False
   */
  [[nodiscard]] bool has_vertex(vertex_id_t vertex_id) const noexcept;

  /**
   * Checks whether two vertices are connected
   *
   * @param  vertex_id_lhs The ID of the first vertex
   * @param  vertex_id_rhs The ID of the second vertex
   * @return boolean - This return Ture to indicate there is an edge between the
   * two vertices otherwise False
   */

  [[nodiscard]] bool has_edge(vertex_id_t vertex_id_lhs,
                              vertex_id_t vertex_id_rhs) const noexcept;

  /**
   * Get a reference to the vertex using its vertex_id
   *
   * @param vertex_id The ID of the vertex
   * @return vertex_t - A reference to the vertex
   * @throws out_of_range exception - If vertex_id does not existing within the
   * graph
   */
  [[nodiscard]] vertex_t& get_vertex(vertex_id_t vertex_id);

  /**
   * Get a const reference to the vertex using its vertex_id
   *
   * @see graph#get_vertex()
   * @param  vertex_id The ID of the vertex
   * @return vertex_t - A const reference to the vertex
   */

  [[nodiscard]] const vertex_t& get_vertex(vertex_id_t vertex_id) const;

  /**
   * Get edge between two vertices with theirs ID
   *
   * @param  vertex_id_lhs The ID of the first vertex
   * @param  vertex_id_rhs The ID of the second vertex
   * @return edge_t - A reference to edge
   * @throws out_of_range exception - If No edge exit between the two vertices
   */
  [[nodiscard]] edge_t& get_edge(vertex_id_t vertex_id_lhs,
                                 vertex_id_t vertex_id_rhs);

  /**
   * Get const version of edge between two vertices with their ID by calling
   * get_edge()
   *
   * @see    graph#get_edge()
   * @param  vertex_id_lhs The ID of the first vertex
   * @param  vertex_id_rhs The ID of the second vertex
   * @return edge_t - A const reference to the edge
   */
  [[nodiscard]] const edge_t& get_edge(vertex_id_t vertex_id_lhs,
                                       vertex_id_t vertex_id_rhs) const;

  /**
   * Get a list of neighbour vertices
   *
   * @param  vertex_id The ID of the vertex
   * @return vertices_t - A list of neigbounthood vertices
   */
  [[nodiscard]] vertices_t get_neighbors(vertex_id_t vertex_id) const;

  /**
   * Add a vertex to the graph
   *
   * @param  vertex The vertex to be added
   * @return vertices_id_t - The ID of the new vertex
   */
  vertex_id_t add_vertex(VERTEX_T vertex);

  /**
   * Remove a vertex from the graph and update all its neighbors
   *
   * @param  vertex_id - The ID of the vertex
   */
  void remove_vertex(vertex_id_t vertex_id);

  /**
   * Add a new edge between two existing vertices
   *
   * @param  vertex_id The ID of the vertex
   * @throws out_of_range - If either of the vertex does not exist in graph
   */
  void add_edge(vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs,
                EDGE_T edge);

  /**
   * Add two connected new vertices to the graph
   *
   * @param  vertex_id_lhs The ID of the first vertex
   * @param  vertex_id_rhs The ID of the second vertex
   * @param  edge
   * @return edge_id_t - The ID of the new edge
   */
  edge_id_t add_edge(VERTEX_T vertex_lhs, VERTEX_T vertex_rhs, EDGE_T edge);

  /**
   * Remove the edge between two vertices
   *
   * @param  vertex_id_lhs The ID of the first vertex
   * @param  vertex_id_rhs The ID of the second vertex
   */
  void remove_edge(vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs);

 protected:
  std::unordered_map<vertex_id_t, vertices_t> adjacency_list_{};

  vertex_id_to_vertex_t vertices_{};
  edge_id_to_edge_t edges_{};

 private:
  [[nodiscard]] virtual bool do_has_edge(
      vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs) const noexcept = 0;
  [[nodiscard]] virtual edge_t& do_get_edge(vertex_id_t vertex_id_lhs,
                                            vertex_id_t vertex_id_rhs) = 0;
  virtual void do_add_edge(vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs,
                           edge_t edge) = 0;
  virtual void do_remove_edge(vertex_id_t vertex_id_lhs,
                              vertex_id_t vertex_id_rhs) = 0;

  size_t vertex_id_supplier_{0};
};

}  // namespace graaf

#include "graph.tpp"

graph.tpp

#pragma once

#include <fmt/core.h>

#include <stdexcept>

namespace graaf {

namespace detail {

template <typename T>
struct is_primitive_numeric
    : std::integral_constant<bool,
                             std::is_arithmetic_v<T> && !std::is_class_v<T>> {};

std::false_type is_weighted_edge_impl(...);
template <typename T>
std::true_type is_weighted_edge_impl(weighted_edge<T>*);

template <typename T>
struct is_weighted_edge {
  using impl = decltype(is_weighted_edge_impl(std::declval<T*>()));
};

}  // namespace detail

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V,
          graph_spec GRAPH_SPEC_V>
std::size_t graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::vertex_count()
    const noexcept {
  return vertices_.size();
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V,
          graph_spec GRAPH_SPEC_V>
std::size_t graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::edge_count()
    const noexcept {
  return edges_.size();
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V,
          graph_spec GRAPH_SPEC_V>
bool graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::has_vertex(
    vertex_id_t vertex_id) const noexcept {
  return vertices_.contains(vertex_id);
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V,
          graph_spec GRAPH_SPEC_V>
bool graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::has_edge(
    vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs) const noexcept {
  return do_has_edge(vertex_id_lhs, vertex_id_rhs);
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V,
          graph_spec GRAPH_SPEC_V>
VERTEX_T& graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::get_vertex(
    vertex_id_t vertex_id) {
  if (!has_vertex(vertex_id)) {
    throw std::out_of_range{
        fmt::format("Vertex with ID [{}] not found in graph.", vertex_id)};
    // May be more accurate to throw std::invalid_argument.
  }
  return vertices_.at(vertex_id);
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V,
          graph_spec GRAPH_SPEC_V>
const VERTEX_T& graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::get_vertex(
    vertex_id_t vertex_id) const {
  return get_vertex(vertex_id);
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V,
          graph_spec GRAPH_SPEC_V>
graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::edge_t&
graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::get_edge(
    vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs) {
  if (!has_edge(vertex_id_lhs, vertex_id_rhs)) {
    throw std::out_of_range{
        fmt::format("No edge found between vertices [{}] -> [{}].",
                    vertex_id_lhs, vertex_id_rhs)};
  }
  return do_get_edge(vertex_id_lhs, vertex_id_rhs);
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V,
          graph_spec GRAPH_SPEC_V>
const graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::edge_t&
graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::get_edge(
    vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs) const {
  return get_edge(vertex_id_lhs, vertex_id_rhs);
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V,
          graph_spec GRAPH_SPEC_V>
graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::vertices_t
graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::get_neighbors(
    vertex_id_t vertex_id) const {
  if (!adjacency_list_.contains(vertex_id)) {
    return {};
  }
  return adjacency_list_.at(vertex_id);
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V,
          graph_spec GRAPH_SPEC_V>
vertex_id_t graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::add_vertex(
    VERTEX_T vertex) {
  // TODO: check overflow
  const auto vertex_id{vertex_id_supplier_++};
  vertices_.emplace(vertex_id, std::move(vertex));
  return vertex_id;
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V,
          graph_spec GRAPH_SPEC_V>
void graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::remove_vertex(
    vertex_id_t vertex_id) {
  if (adjacency_list_.contains(vertex_id)) {
    for (auto& target_vertex_id : adjacency_list_.at(vertex_id)) {
      edges_.erase({vertex_id, target_vertex_id});
    }
  }

  adjacency_list_.erase(vertex_id);
  vertices_.erase(vertex_id);

  for (auto& [source_vertex_id, neighbors] : adjacency_list_) {
    neighbors.erase(vertex_id);
    edges_.erase({source_vertex_id, vertex_id});
  }
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V,
          graph_spec GRAPH_SPEC_V>
void graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::add_edge(
    vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs, EDGE_T edge) {
  if (!has_vertex(vertex_id_lhs) || !has_vertex(vertex_id_rhs)) {
    throw std::out_of_range{
        fmt::format("Vertices with ID [{}] and [{}] not found in graph.",
                    vertex_id_lhs, vertex_id_rhs)};
  }
  if constexpr (EDGE_TYPE_V == edge_type::WEIGHTED) {
    do_add_edge(vertex_id_lhs, vertex_id_rhs,
                std::make_shared<typename edge_t::element_type>(edge));
  } else {
    do_add_edge(vertex_id_lhs, vertex_id_rhs, edge);
  }
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V,
          graph_spec GRAPH_SPEC_V>
edge_id_t graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::add_edge(
    VERTEX_T vertex_lhs, VERTEX_T vertex_rhs, EDGE_T edge) {
  const auto vertex_id_lhs{add_vertex(std::move(vertex_lhs))};
  const auto vertex_id_rhs{add_vertex(std::move(vertex_rhs))};
  add_edge(vertex_id_lhs, vertex_id_rhs, std::move(edge));
  return {vertex_id_lhs, vertex_id_rhs};
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V,
          graph_spec GRAPH_SPEC_V>
void graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, GRAPH_SPEC_V>::remove_edge(
    vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs) {
  do_remove_edge(vertex_id_lhs, vertex_id_rhs);
}

}  // namespace graaf

undirected_graph.h

#pragma once

#include <graaflib/graph.h>
#include <graaflib/types.h>

namespace graaf {

template <typename VERTEX_T, typename EDGE_T,
          edge_type EDGE_TYPE_V = edge_type::UNWEIGHTED>
class undirected_graph final
    : public graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, graph_spec::UNDIRECTED> {
 private:
  using edge_t =
      graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, graph_spec::UNDIRECTED>::edge_t;

  [[nodiscard]] bool do_has_edge(
      vertex_id_t vertex_id_lhs,
      vertex_id_t vertex_id_rhs) const noexcept override;

  [[nodiscard]] edge_t& do_get_edge(vertex_id_t vertex_id_lhs,
                                    vertex_id_t vertex_id_rhs) override;

  void do_add_edge(vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs,
                   edge_t edge) override;

  void do_remove_edge(vertex_id_t vertex_id_lhs,
                      vertex_id_t vertex_id_rhs) override;
};

}  // namespace graaf

#include "undirected_graph.tpp"

undirected_graph.tpp

#pragma once

namespace graaf {

namespace detail {
inline std::pair<vertex_id_t, vertex_id_t> make_sorted_pair(
    vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs) {
  if (vertex_id_lhs < vertex_id_rhs) {
    return std::make_pair(vertex_id_lhs, vertex_id_rhs);
  }
  return std::make_pair(vertex_id_rhs, vertex_id_lhs);
}
}  // namespace detail

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V>
bool undirected_graph<VERTEX_T, EDGE_T, EDGE_TYPE_V>::do_has_edge(
    vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs) const noexcept {
  return this->edges_.contains(
      detail::make_sorted_pair(vertex_id_lhs, vertex_id_rhs));
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V>
undirected_graph<VERTEX_T, EDGE_T, EDGE_TYPE_V>::edge_t&
undirected_graph<VERTEX_T, EDGE_T, EDGE_TYPE_V>::do_get_edge(
    vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs) {
  return this->edges_.at(
      detail::make_sorted_pair(vertex_id_lhs, vertex_id_rhs));
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V>
void undirected_graph<VERTEX_T, EDGE_T, EDGE_TYPE_V>::do_add_edge(
    vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs, edge_t edge) {
  this->adjacency_list_[vertex_id_lhs].insert(vertex_id_rhs);
  this->adjacency_list_[vertex_id_rhs].insert(vertex_id_lhs);

  this->edges_.emplace(detail::make_sorted_pair(vertex_id_lhs, vertex_id_rhs),
                       std::move(edge));
}

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V>
void undirected_graph<VERTEX_T, EDGE_T, EDGE_TYPE_V>::do_remove_edge(
    vertex_id_t vertex_id_lhs, vertex_id_t vertex_id_rhs) {
  this->adjacency_list_.at(vertex_id_lhs).erase(vertex_id_rhs);
  this->adjacency_list_.at(vertex_id_rhs).erase(vertex_id_lhs);
  this->edges_.erase(detail::make_sorted_pair(vertex_id_lhs, vertex_id_rhs));
}

}  // namespace graaf
\$\endgroup\$
4
  • 2
    \$\begingroup\$ The directed / undirected distinction is very nice, and admits of alternate datastructures under the hood. The UNWEIGHTED aspect doesn't seem to have a motivating use case, though. Default all edges to unit weight and be done with it, no? One could save a little RAM in the unweighted case, but wait until some problem actually cares about that and then implement it. \$\endgroup\$
    – J_H
    Jun 3, 2023 at 20:11
  • \$\begingroup\$ Hi @J_H, thanks for your reply, that makes a lot of sense! I think I will completely get rid of the unweighted specialization then \$\endgroup\$
    – Bobray
    Jun 3, 2023 at 20:15
  • 2
    \$\begingroup\$ Cool. Understand that the specialization might come back, depending on which problems you choose to add to your test suite. One way to think of it is as a "compression" problem -- if some giant graph has most or all of its weights set to unity, a refactor might seek to compute same result while using less RAM. As a separate matter, for now you might enforce non-negative weights. Later if you move on, say, from Dijkstra's algorithm to Bellman-Ford, you can always revisit such assumptions. \$\endgroup\$
    – J_H
    Jun 3, 2023 at 20:18
  • 1
    \$\begingroup\$ I dont see any good reason to use virtual dispatch for handling directed and undirected graphs. We already know the type of the graph at compile time, you can just use tag dispatch here. This will also eliminate the need for shared_ptrs. \$\endgroup\$ Jul 3, 2023 at 13:39

1 Answer 1

4
\$\begingroup\$
  1. Architecture: Your graph class seems trying to be too many things at the same time. It is simultaneously trying to implement wieghted-vs-unwieghtedness and directed-undirectedness. We can instead let the graph just deal with the directedness and delegate the weightedness to the edges. We can create this by simply creating a templated struct Weighted.

  2. Use if constexpr: Instead of overloading on tag type, use if constexpr to make the code concise and readable.

  3. Proper Indentation: Your indentation is horrible. It I am not able to tell where arguments end and body a function begins. Watch this talk.

  4. Use proper header guards: #pragma once tend to fail with symlinks and have issues dealing with build systems that may copy files around.

  5. Perfect forwarding: Use auto&& and std::forward to forward arguments to emplace_back. Right now the add_* member function is creating a copy of the node negating any benefits of emplace_back.

  6. Primitive Type: Use std::is_fundamental_v instead of rolling your own template. Also, with C++17, you can use templated constexpr bool instead of having to do SFINAE on a struct.

  7. this : There is no need to use this-> unless there is a shadow variable. Since you are using _ suffix, it is redundant in your code.

Here is my implementation based on the review:

#include <cstddef>
#include <cstdint>
#include <unordered_map>
#include <unordered_set>

namespace graaf{

using vertex_id_t = size_t;
using edge_id_t = size_t;

template<typename T, typename Weight>
struct weighted_edge {
    using value_type = T;
    static constexpr bool is_weighted = true;

    T value;
    Weight weight;
};

template<typename T>
struct unweighted_edge {
    using value_type = T;
    static constexpr bool is_weighted = false;

    T value;
};

namespace detail {
inline std::pair<vertex_id_t, vertex_id_t> make_sorted_pair(
    vertex_id_t vertex_id_lhs,
    vertex_id_t vertex_id_rhs
){    
    if(vertex_id_lhs < vertex_id_rhs) {
        return std::make_pair(vertex_id_lhs, vertex_id_rhs);
    } else {
        return std::make_pair(vertex_id_rhs, vertex_id_lhs);
    }
}

}  // namespace detail


template<typename Vertex, typename Edge, bool IsDirected = false>
class graph {
public:

    using edge_type = typename Edge::value_type;
    using vertex_type = Vertex;
    static constexpr bool is_directed = IsDirected;
    static constexpr bool is_weighted = Edge::is_weighted;

    [[nodiscard]] std::size_t vertex_count() const noexcept {
        return vertices_.size();
    }

    [[nodiscard]] std::size_t edge_count() const noexcept {
        return edges_.size();
    }

    [[nodiscard]] bool has_vertex(vertex_id_t vertex_id) const noexcept {
        return vertices_.contains(vertex_id); 
    }

    [[nodiscard]] bool has_edge(
        vertex_id_t vertex_id_lhs,
        vertex_id_t vertex_id_rhs
    ) const noexcept {
        if constexpr (!IsDirected) {
            return edges_.contains(detail::make_sorted_pair(vertex_id_lhs, vertex_id_rhs));
        } else {
            //TODO: Implement for directed
            static_assert(false, "Not Implemented");
            return false;
        }
    }

    //TODO: Implement other similarly

private:


    std::unordered_map<vertex_id_t, std::unordered_set<vertex_id_t>> adjacency_list_{};
    std::unordered_map<edge_id_t, edge_type> edges_{};
    std::unordered_map<vertex_id_t, Vertex> vertices_{};

};

}

int main(){
    auto graph = graaf::graph<int, graaf::weighted_edge<int, float>>{};
}
\$\endgroup\$

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.