Graphs

template<std::unsigned_integral Idx, typename Alloc = HugepageAllocator<Idx>>
class SimpleGraph : public svs::graphs::SimpleGraphBase<Idx, data::SimpleData<Idx, Dynamic, HugepageAllocator<Idx>>>

Simple graph representation.

This data structure represents a graph using a single large allocation and a set maximum degree. Accessing adjacency lists takes O(1) time. Only out-bound edges are stored.

Template Parameters:

Idx – The integer type used to encode vertices in this graph.

Public Types

using index_type = Idx

The integer representation used to represent vertices in this graph.

using reference = std::span<Idx>

Type used to represent mutable adjacency lists externally.

using const_reference = std::span<const Idx>

Type used to represent constant adjacency lists externally.

Public Functions

inline explicit SimpleGraph(size_t num_nodes, size_t max_degree)

Consturct a new empty graph.

Parameters:

  • num_nodes – The number of nodes in the graph.

  • max_degree – The maximum allowable degree in the graph.

inline const_reference get_node(Idx i) const

Return the outward adjacency list for vertex i.

Parameters:

i – The vertex to get the ID for.

inline bool has_edge(Idx src, Idx dst) const

Return whether or not the adjacency list has an edge from src to dst.

Complexity: Linear in the maximum degree.

inline size_t get_node_degree(Idx i) const

Return the current out degree of vertex i.

inline void prefetch_node(Idx i) const

Prefetch the adjacency list for node i into the L1 cache.

inline void clear_node(Idx i)

Remove all outgoing neighbors from node i.

Note: As an implementation detail, this method doesn’t mutate the actual adjacency list. Instead, it simply sets the number of neighbors to zero.

The complexity of this operation is O(1).

inline void reset()

Remove all edges from the graph.

inline void replace_node(Idx i, const std::vector<Idx> &new_neighbors)

Replace the adjacency list for vertex i.

Takes at most max_degree() elements from new_neighbors. May silently drop any excess neighbors.

Preconditions:

  • All elements of new_neighbors must be between 0 and n_nodes()

  • All elements of new_neighbors must be unique.

Parameters:

  • i – The vertex whose adjacency list is being modified.

  • new_neighbors – The new adjacency list for vertex i.

inline void replace_node(Idx i, std::span<const Idx> new_neighbors)

Replace the adjacency list for vertex i.

Takes at most max_degree() elements from new_neighbors. May silently drop any excess neighbors.

Preconditions:

  • All elements of new_neighbors must be between 0 and n_nodes()

  • All elements of new_neighbors must be unique.

Parameters:

  • i – The vertex whose adjacency list is being modified.

  • new_neighbors – The new adjacency list for vertex i.

inline size_t add_edge(Idx src, Idx dst)

Add an edge from vertex src to vertex dst.

The adjacency list of src will be left unchanged if:

  • src == dst (no self assignment)

  • get_node_degree(src) == max_degree() (adjacency list is already full)

  • dst is already an out-neighbor of src.

Parameters:

  • src – The source vertex.

  • dst – The destination vertex.

Returns:

The number of out neighbors of src after dst is inserted.

inline size_t max_degree() const

Return the maximum out-degree this graph is capable of containing.

inline size_t n_nodes() const

Return the number of vertices currently in the graph.

Graph Loading

template<typename Idx = uint32_t>
struct GraphLoader

Loader for SVS graphs.

Template Parameters:

Idx – The type used to encode nodes in the graph.

Public Functions

inline GraphLoader(const std::filesystem::path &path)

Construct a new GraphLoader.

The saved graph directory will generally be created when saving a graph based index. The path argument should be this directory.

Parameters:

path – The file path to the graph directory on disk.

inline return_type load() const

Load the graph into memory.

Note

The various graph implementations given above are all instances of the more general concept svs::graphs::ImmutableMemoryGraph. Where possible, this concept is use to constrain template arguments, allowing for future custom implementations.