5
\$\begingroup\$

I wrote a rudimentary graph class that supports the following eight combinations:

  • Undirected/directed
  • Weighted/unweighted
  • Adj list/Adj matrix implementation

#include <algorithm>
#include <cassert>
#include <cmath>
#include <common.h>
#include <list>
#include <vector>
#include <ranges>
#include <stdexcept>

namespace frozenca::hard {

namespace detail {

template <typename Weight>
struct AdjListDescTrait {
  using desc_type = std::pair<index_t, Weight>;
  using edges_type = std::vector<std::list<desc_type>>;

  static void add_edge(edges_type& edges, index_t src, index_t dst, float weight) {
    edges[src].emplace_back(dst, weight);
  }

  static index_t proj(const desc_type& desc) noexcept {
    return desc.first;
  }
};

template <>
struct AdjListDescTrait<void> {
  using desc_type = index_t;
  using edges_type = std::vector<std::list<desc_type>>;

  static void add_edge(edges_type& edges, index_t src, index_t dst) {
    edges[src].emplace_back(dst);
  }

  static index_t proj(const desc_type& desc) noexcept {
    return desc;
  }
};

template <typename Weight>
struct AdjListTrait {
  using desc_trait = AdjListDescTrait<Weight>;
  using desc_type = desc_trait::desc_type;
  using edges_type = desc_trait::edges_type;
  using edge_iter_type = std::list<desc_type>::iterator;
  using edge_const_iter_type = std::list<desc_type>::const_iterator;
  using edge_range_type = std::ranges::subrange<edge_iter_type>;
  using const_edge_range_type = std::ranges::subrange<edge_const_iter_type>;

  static void resize(edges_type& edges, index_t new_size) {
    auto old_size = curr_size(edges);
    if (new_size < old_size) {
      for (index_t i = 0; i < new_size; ++i) {
        std::erase_if(edges[i], [&new_size](const auto& edge_desc) {
          return desc_trait::proj(edge_desc) >= new_size;
        });
      }
    }
    edges.resize(new_size);
  }

  static index_t curr_size(const edges_type& edges) {
    return std::ssize(edges);
  }

  static edge_range_type get_edges(edges_type& edges, index_t index) {
    return edges[index];
  }

  static const_edge_range_type get_edges(const edges_type& edges, index_t index) {
    return edges[index];
  }
};

template <typename Weight>
struct AdjMatDescTrait {
  using desc_type = Weight;
  using edges_type = std::vector<desc_type>;

  static void add_edge(edges_type& edges, index_t src, index_t dst, float weight) {
    const auto curr_size = static_cast<index_t>(std::sqrt(std::ssize(edges)));
    edges[src * curr_size + dst] = weight;
  }
};

template <>
struct AdjMatDescTrait<void> {
  using desc_type = int;
  using edges_type = std::vector<desc_type>;

  static void add_edge(edges_type& edges, index_t src, index_t dst) {
    const auto curr_size = static_cast<index_t>(std::sqrt(std::ssize(edges)));
    edges[src * curr_size + dst] = 1;
  }
};

template <typename Weight>
struct AdjMatTrait {
  using desc_trait = AdjMatDescTrait<Weight>;
  using desc_type = desc_trait::desc_type;
  using edges_type = desc_trait::edges_type;
  using edge_iter_type = std::vector<desc_type>::iterator;
  using edge_const_iter_type = std::vector<desc_type>::const_iterator;
  using edge_range_type = std::ranges::subrange<edge_iter_type>;
  using const_edge_range_type = std::ranges::subrange<edge_const_iter_type>;

  static void resize(const edges_type& edges, index_t new_size) {
    auto old_size = curr_size(edges);
    if (new_size < old_size) {
      for (index_t i = 0; i < new_size; ++i) {
        for (index_t j = 0; j < new_size; ++j) {
          edges[i * new_size + j] = edges[i * old_size + j];
        }
      }
    }
    edges.resize(new_size * new_size);
    if (new_size > old_size) {
      for (index_t i = old_size - 1; i >= 0; --i) {
        for (index_t j = old_size - 1; j >= 0; --j) {
          edges[i * new_size + j] = edges[i * old_size + j];
          edges[i * old_size + j] = 0;
        }
      }
    }
  }

  static index_t curr_size(const edges_type& edges) {
    return static_cast<index_t>(std::sqrt(std::ssize(edges)));
  }

  static edge_range_type get_edges(edges_type& edges, index_t index) {
    auto sz = curr_size(edges);
    return {edges.begin() + index * sz, edges.begin() + (index + 1) * sz};
  }

  static const_edge_range_type get_edges(const edges_type& edges, index_t index) {
    auto sz = curr_size(edges);
    return {edges.begin() + index * sz, edges.begin() + (index + 1) * sz};
  }
};

struct AdjListTraitTag {
  template <bool Weighted, typename WeightType>
  using edge_trait_type = AdjListTrait<std::conditional_t<Weighted, WeightType, void>>;
};

struct AdjMatTraitTag {
  template <bool Weighted, typename WeightType>
  using edge_trait_type = AdjMatTrait<std::conditional_t<Weighted, WeightType, void>>;
};

template <bool Directed, bool Weighted, typename WeightType,
          typename EdgeTraitTag>
class GraphBase {
public:
  using edge_trait = EdgeTraitTag::template edge_trait_type<Weighted, WeightType>;
  using edges_type = edge_trait::edges_type;
  using edge_iter_type = edge_trait::edge_iter_type;
  using edge_const_iter_type = edge_trait::edge_const_iter_type;

private:
  edges_type edges_;

  [[nodiscard]] bool vertex_large(index_t index) const noexcept {
    return index >= size();
  }

  [[nodiscard]] bool vertex_small(index_t index) const noexcept {
    return index < 0;
  }

  [[nodiscard]] bool vertex_invalid(index_t index) const noexcept {
    return vertex_small(index) || vertex_large(index);
  }

public:

  void index_check(index_t src, index_t dst) {
    auto max_index = max(src, dst);
    if (src < 0 || dst < 0) {
      throw std::invalid_argument("vertex index is negative");
    } else if (vertex_large(max_index)) {
      edge_trait::resize(edges_, max_index + 1);
    }
  }

  void add_edge(index_t src, index_t dst, WeightType w) requires (Weighted) {
    index_check(src, dst);
    edge_trait::desc_trait::add_edge(edges_, src, dst, w);
    if constexpr (!Directed) {
      edge_trait::desc_trait::add_edge(edges_, dst, src, w);
    }
  }
  
  void add_edge(index_t src, index_t dst) requires (!Weighted) {
    index_check(src, dst);
    edge_trait::desc_trait::add_edge(edges_, src, dst);
    if constexpr (!Directed) {
      edge_trait::desc_trait::add_edge(edges_, dst, src);
    }
  }

  auto edges(index_t src) {
    if (vertex_invalid(src)) {
      throw std::invalid_argument("vertex does not exist");
    }
    return edge_trait::get_edges(edges_, src);
  }

  auto edges(index_t src) const {
    if (vertex_invalid(src)) {
      throw std::invalid_argument("vertex does not exist");
    }
    return edge_trait::get_edges(edges_, src);
  }

  [[nodiscard]] index_t size() const noexcept {
    return edge_trait::curr_size(edges_);
  }
};

} // namespace detail

template <typename EdgeTraitTag = detail::AdjListTraitTag>
using Graph = detail::GraphBase<false, false, void, EdgeTraitTag>;

template <typename EdgeTraitTag = detail::AdjListTraitTag>
using DiGraph = detail::GraphBase<true, false, void, EdgeTraitTag>;

template <typename W = float, typename EdgeTraitTag = detail::AdjListTraitTag>
using WeightedGraph = detail::GraphBase<false, true, W, EdgeTraitTag>;

template <typename W = float, typename EdgeTraitTag = detail::AdjListTraitTag>
using WeightedDiGraph = detail::GraphBase<true, true, W, EdgeTraitTag>;

} // namespace frozenca::hard

Simple function that does topological sort for directed (acyclic, but not checked) graph:

void topological_sort_helper(const hard::WeightedDiGraph<> &g, std::vector<int> &visited,
                             std::vector<index_t> &top_sort, index_t i) {
  visited[i] = true;

  for (const auto &[dst, w] : g.edges(i)) {
    if (!visited[dst]) {
      topological_sort_helper(g, visited, top_sort, dst);
    }
  }
  top_sort.push_back(i);
}

void top_sort(const hard::WeightedDiGraph<>& g) {
  std::vector<index_t> top_sort;
  auto V = g.size();
  std::vector<int> visited(V);
  assert(src < V);

  for (index_t i = 0; i < V; ++i) {
    if (!visited[i]) {
      topological_sort_helper(g, visited, top_sort, i);
    }
  }
}

index_t is just std::ptrdiff_t.

It worked correctly for both adj_list/adj_matrix implementations.

I'm very new to trait-based class design, so I need your advice!

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Compile errors

I had some issues compiling your code. I had to define index_t, but I guess that is expected. One case of max() which should be std::max(). And then there is the assert(src < V) inside top_sort(), but there is no src variable.

Header file location

I noticed you did #include <common.h>. If you include something with angle brackets (<>), then the compiler will search for the file in the standard system directories for header files, and optionally any directories specified using the -I option (for GCC and Clang). If common.h is a local file, you should instead includ using quotes, like so:

#include "common.h"

This will look for common.h in the same directory as the source file it's compiling. If indeed common.h is a local file, and only needed to compile your graph library (and not needed by an application that wants to link with your graph library), prefer quotes, as this avoids any ambiguity with a potential common.h file in the header file search path.

If you plan to have common.h be installed such that it's in the standard system header file locations, then consider that a name like common.h is too generic. What if another library also has a common.h? To solve this, make sure the header file is in a directory with a unique name for your library, for example such that you can do:

#include <frozenca/graph/common.h>

Don't be afraid of std::vector<bool>

Yes, it's a specialization which has a few issues, but for your use cases (visited and edges_type for adjacency matrices), it's perfectly fine, and much more efficient than std::vector<int>.

Don't use floating point math unnecessarily

For AdjMatDescTrait::add_edge(), you want to know the size of one dimension of the matrix. You store all elements in a 1D vector, so you take the square root of the size. However, this is very inefficient and dangerous: apart from conversion to float and back, floating point operations might not be as precise as you want. In particular, for double precision floating point numbers, integers above \$2^{53}\$ can not be accurately represented. I recommend just storing the width of the matrix as a separate member variable.

Consider allowing zero weights

In the case of an adjacency matrix, you treat a weight of zero is not having an edge. However, that is not always desirable. There are situations where a zero or negative weight can be assigned to existing edges. See also this question.

About the design

It's nice to have 8 different graph types that share the same interface. However, there are a lot of templated trait classes to support having a generic GraphBase, and then you have 4 aliases for specific graph types (and it would have been 8 if you didn't use the EdgeTraitTag template parameter). Adding other traits is going to be a lot of work.

There is also no room for data associated with vertices and edges, apart from their index and weight. What if you want to color your graph? What if vertices are identified by something other than a numerical index? Or maybe the indexing is sparse?

There are much more ways a graph can be stored than your class allows. I would therefore not create a class that stores the graph itself, but rather one that provides a mixin that is useful for providing a standard set of functions for concrete matrix classes. A very simplified example:

template<typename T>
class GraphBase {
    void add_edge(typename T::vertex_type src, typename T::vertex_type dst) {
        T::edges[src].push_back(dst);
        if constexpr (!T::directed) {
            T::edges[dst].push_back(src);
        }
    }
};

struct DiGraphData {
    using vertex_type = int;
    static constexpr bool directed = true;
    std::map<vertex_type, std::deque<vertex_type>> edges;
};

using DiGraph = GraphBase<DiGraphData>;

In this example, all the traits are in DiGraphData, they are no longer scattered among multiple structs. There is a lot of freedom here, for example edges are now stored in a std::map of std::deques, but you can easily change those types. And GraphBase now only has a single template parameter. It can use SFINAE or concepts to determine what properties the data type has. In the example, a static constexpr bool is used as a tag to indicate whether it is a directed or undirected graph. But you can also check in GraphBase whether edges is a container of containers, or a single, flat container, and use that to determine if it's an adjacency list or matrix type graph, and thus how to correctly add a new edge to the graph.

\$\endgroup\$
6
  • \$\begingroup\$ Thanks as always, but for "You should only use <> for libraries that are in the standard library search path, for libraries that are installed system-wide.", could you elaborate why? The book I'm recently reading (Large Scale C++, John Lakos) says "if there's choice, prefer <header.h> over "header.h"", and I'm seeing many practices using <header.h> (example: github.com/pytorch/pytorch/blob/master/torch/csrc/jit/…) \$\endgroup\$
    – frozenca
    Commented Jul 10, 2022 at 6:49
  • \$\begingroup\$ I updated my answer. I haven't read "Large Scale C++", but either the quote seems out of context or just plain wrong. \$\endgroup\$
    – G. Sliepen
    Commented Jul 10, 2022 at 11:37
  • \$\begingroup\$ using "header.h" over <header.h> for user defined header files is only a convention apparently, but a very widely used one: Try this link to S O \$\endgroup\$
    – Lozminda
    Commented Jul 14, 2022 at 1:06
  • \$\begingroup\$ @Lozminda It's not just a convention, there are clear differences in semantics. But a lot of projects add -I. to the compile flags to make those differences go away, and this usually works fine, but it can actually be problematic if you have local headers named the same as some system headers. \$\endgroup\$
    – G. Sliepen
    Commented Jul 14, 2022 at 9:25
  • 1
    \$\begingroup\$ The C++ standard section 6.10.2. Interestingly it says (and I'm going off topic) of "a_header": If this search is not supported, or if the search fails, the directive is reprocessed as if it read <a_header>. But I'm going off piste \$\endgroup\$
    – Lozminda
    Commented Jul 14, 2022 at 13:11

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.