overview

Architecture Overview

From a very high level, the project is structured in two parts:

• The graph classes and core data structures
• Algorithms and additional functionality

Graph classes and core data structures

The main class of the library is the abstract graph class:

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:

// N.B. These types are a bit more abstracted in the codebase behind using
// declarations, but for clarity I have left this out.

// Adjacency information is stored in a set for fast existence checks and fast removal
std::unordered_map<vertex_id_t, std::unordered_set<vertex_id_t>> adjacency_list_{};

// Storing these in a separate container has the advantage that
// vertices and edges are only in memory once
std::unordered_map<vertex_id_t, VERTEX_T> vertices_{};
std::unordered_map<std::pair<vertex_id_t, vertex_id_t>, edge_t, edge_id_hash> edges_{};

The graph class is abstract as it contains pure virtual private methods related to the handling of edges (do_has_edge, do_get_edge, do_add_edge, and do_remove_edge).

Directed and undirected graphs

There are two classes which publicly derive from graph:

• directed_graph
• undirected_graph

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V = edge_type::UNWEIGHTED>
class directed_graph final
    : public graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, graph_spec::DIRECTED> 
    {...};

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> 
    {...};

These are the classes which the user instantiates.

They provide implementations for the pure virtual methods related to handling edges. The unweighted_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_weighted_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:

template <typename WEIGHT_T>
class weighted_edge {
 public:
  [[nodiscard]] virtual WEIGHT_T get_weight() const noexcept = 0;
};

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

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_{};
};

This post is hidden. You deleted this post 2 hours ago.

I hope this type of question is allowed.

As a personal side project I started building a graph library in C++. I am now at the point where I have my core data structures set up. I would like to get feedback on the architecture and the choice of data structures.

The code is open source and can be found here, but for the purpose of this question I will try to provide the most relevant details below. I will start with an overview of the library's architecture, and will pose some more specific design questions I have a the end. 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 as possible. Project setup

From a very high level, the project is structured in two parts:

The graph classes and core data structures
Algorithms and additional functionality

The idea here is to keep the graph classes as general-purpose as possible, and to not include use case specific logic (such as dot serialization) as member functions. Therefore, each algorithm/utility function is implemented as a free function. Main 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:

// N.B. These types are a bit more abstracted in the codebase behind using // declarations, but for clarity I have left this out.

// Adjacency information is stored in a set for fast existence checks and fast removal std::unordered_map<vertex_id_t, std::unordered_set<vertex_id_t>> adjacency_list_{};

// Storing these in a separate container has the advantage that // vertices and edges are only in memory once std::unordered_map<vertex_id_t, VERTEX_T> vertices_{}; std::unordered_map<std::pair<vertex_id_t, vertex_id_t>, edge_t, edge_id_hash> edges_{};

The graph class is abstract as it contains pure virtual private methods related to the handling of edges (do_has_edge, do_get_edge, do_add_edge, and do_remove_edge). Directed and undirected graphs

There are two classes which publicly derive from graph:

directed_graph
undirected_graph

template <typename VERTEX_T, typename EDGE_T, edge_type EDGE_TYPE_V = edge_type::UNWEIGHTED> class directed_graph final : public graph<VERTEX_T, EDGE_T, EDGE_TYPE_V, graph_spec::DIRECTED> {...};

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> {...};

These are the classes which the user instantiates.

They provide implementations for the pure virtual methods related to handling edges. The unweighted_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:

template class weighted_edge { public: nodiscard virtual WEIGHT_T get_weight() const noexcept = 0; };

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

template 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_{}; };

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

When adding an edge to the graph, we still accept the original type which was specified. For example, a weighted graph with floats for edges still allows you to pass a float when adding the edge. However, internally it will be wrapped in a shared pointer to primitive_numeric_adapter. When the edge is retrieved from the graph the user gets a shared pointer to weighted_edge returned.

Algorithms and additional functionality

The idea here is to keep the graph classes as general-purpose as possible, and to not include use case specific logic (such as dot serialization) as member functions. Therefore, each algorithm/utility function is implemented as a free function.