Abstract Graphs
Like abstract datasets, the graph concepts svs::graphs::ImmutableMemoryGraph and svs::graphs::MemoryGraph are used to model the expected behavior of graphs.
Concrete implementations can be found here.
Main Concepts
-
template<typename T>
concept ImmutableMemoryGraph - #include <svs/concepts/graph.h>
Main concept modeling immutable in-memory graphs.
template <typename T> concept ImmutableMemoryGraph = requires(const T& const_g) { // The encoding of vertices in the graph. // At the time of writing, this is expected to be an integer. // This may be relaxed in the future. typename T::index_type; std::integral<typename T::index_type>; // Has `reference` and `const_reference` type aliases. // These types should be at least forward ranges, but preferably random access // ranges. // // Items yieled by the iterators for these ranges should ``index_type``. typename T::reference; typename T::const_reference; // Return the maximum degree that this particular implementation of the graph is // capable of supporting. // // If the graph supports unbounded adjacency lists, may return `Dynamic`. { const_g.max_degree() } -> std::convertible_to<size_t>; // Return the number of vertices contained in traph. { const_g.n_nodes() } -> std::convertible_to<size_t>; // Adjacency list operations. requires requires(typename T::index_type i) { // Return a range over the adjacency list for node ``i``. { const_g.get_node(i) } -> std::same_as<typename T::const_reference>; // Return the number of out neighbors for node ``i``. { const_g.get_node_degree(i) } -> std::convertible_to<size_t>; // Prefetch the adjacency list for node ``i``. // This is a performance optimization only and may be implemented as a no-op // without affecting correctness. const_g.prefetch_node(i); }; };
-
template<typename T>
concept MemoryGraph - #include <svs/concepts/graph.h>
Concept modeling mutable in-memory graphs.
template <typename T> concept MemoryGraph = requires(T& g, const T& const_g) { // Add an edge to the graph. // Must return the out degree of `src` after adding the edge `src -> dst`. // If adding the edge would result in the graph exceeding its maximum degree, // implementations are free to not add this edge. requires requires(index_type_t<T> src, index_type_t<T> dst) { { g.add_edge(src, dst) } -> std::convertible_to<size_t>; }; // Completely clear the adjacency list for vertex ``i``. requires requires(index_type_t<T> i) { g.clear_node(i); }; // Overwrite the adjacency list for `src`. requires requires( index_type_t<T> src, const std::vector<index_type_t<T>>& neighbors_vector, std::span<const index_type_t<T>> neighbors_span ) { g.replace_node(src, neighbors_vector); g.replace_node(src, neighbors_span); }; };