v2.0.0

Release v2.0.0

The v2.0.0 release marks a major milestone for the library. It introduces the brand-new HGL (Hypergraph Library) module for modeling higher-order connections, alongside a comprehensive architectural refactor of the core GL (Graph Library) module to significantly improve performance, memory locality, and API ergonomics.

Below is a detailed breakdown of the new features, structural changes, and enhancements included in this release.

1. Introduction of the HGL Module

The library is now strictly partitioned into two modules. The new HGL module is built seamlessly on top of the GL infrastructure, providing native, first-class support for hypergraphs where a single hyperedge can connect an arbitrary number of vertices.

• Dual Directionality Models: Provides full support for standard undirected hypergraphs (hgl::undirected_t) and Backward-Forward directed hypergraphs (hgl::bf_directed_t), making it possible to model complex multi-way flows like chemical reactions or logic gates.
• Incidence-Based Representations: Introduces highly configurable memory models to handle hypergraph incidence.
  • Standard Models: Dynamic, 2D Incidence Lists (list_t) and Incidence Matrices (matrix_t).
  • Flat Models: Cache-optimized, contiguous 1D memory array layouts (flat_list_t, flat_matrix_t).
• Layout Orientations: The memory structures can be explicitly oriented to optimize generalized incidence queries using representation layout tags (bidirectional_t, vertex_major_t, and hyperedge_major_t).
• Hypergraph Traversals & Reachability: Introduces generic search engines adapted for the two-step expansion required by hypergraphs. Includes standard unrestricted traversals (BFS, DFS) as well as strict directional reachability algorithms for BF-directed topologies:
  • Backward Searches (B-Reachability): Blocks hyperedge traversal until all tail (source) vertices are satisfied (backward_bfs, backward_dfs).
  • Forward Searches (F-Reachability): Blocks hyperedge traversal until all head (destination) vertices are satisfied (forward_bfs, forward_dfs).
• Hypergraph Properties & Utilities: A suite of functional utilities to evaluate global structural properties, including maximum/minimum degrees, rank, corank, regularity, and uniformity checks.
• Topology Projections: Includes built-in conversion utilities to project hypergraphs down into standard graphs (e.g., Undirected Clique Expansion, BF-Directed Projection, and Incidence Graph Conversion).

2. Major GL Module Refactor

The core GL module has undergone significant internal refactoring to maximize cache locality, eliminate unnecessary overhead, and streamline the API.

• Contiguous Property Storage: The storage mechanism for custom element properties has been completely overhauled. The library no longer relies on std::vector<std::unique_ptr<T>> for property payloads. Properties are now packed directly into contiguous std::vector<T> arrays, drastically improving cache locality and iteration speeds.
• Configurable ID Types: The rigid, hardcoded id_type has been replaced. The IdType is now a configurable template parameter injected via the graph_traits and hypergraph_traits structures (defaulting to std::uint32_t). This allows the memory footprint to be strictly tailored to the size of the topology.
• Flat Graph Models: Introduced new flat_list_t and flat_matrix_t representation tags for standard graphs, mapping the 2D adjacency matrix into a highly optimized, flat 1D memory layout.
• API Ergonomics & "Least Astonishment":
  • Standardized graph size query naming: n_vertices() and n_edges().
  • Stripped all redundant get_ prefixes from the API.
  • Introduced direct element accessors, including vertex_unchecked, operator[], and at() methods on the topology classes.
  • Extended descriptors with direct operator* and operator-> overloads to effortlessly access property payloads.

3. Algorithmic Architecture Enhancements

The algorithm engines and return structures have been refined to guarantee zero-cost abstractions.

• Return Discriminators: Removed the overhead of std::optional in algorithm outputs. Algorithms now utilize a compile-time result_discriminator (ret or noret). When executed strictly for side-effects (noret), all internal state-tracking allocations for the result are entirely optimized away.
• PFS Engine Upgrades: The Priority-First Search (pfs) generic template was modified to accept arbitrary, user-defined search nodes. This allows for complex state tracking directly within the priority queue, which properly resolved custom distance comparisons in the underlying dijkstra_shortest_paths implementation.
• Predecessor Maps: Basic search algorithms were aligned to return flat predecessors_map structures rather than bloated search trees for standard graphs.

4. I/O and Serialization Improvements

The input/output utilities were expanded to robustly support both graph and hypergraph topologies.

• Stream Options Manipulator: Refactored the options_manip structure to utilize bitmasks for setting and clearing states, ensuring reliable formatting persistence across both modules.
• Formatters: Defined generic range_formatter and implicit_range_formatter utilities to standardize the textual output of inner structures.
• HGSF Integration: Implemented full serialization and deserialization support for the hypergraphs through the Hypergraph Specification Format (HGSF).

5. Documentation and Tooling

• Documentation Suite: Deployed a complete, versioned documentation site using MkDocs and mike.
• Automated Extraction: Added custom Python scripts to parse C++20 concepts from a doxygen-generated XML, generating perfectly formatted markdown documentation for the library's traits system.
• Workflow Alignment: CMake targets and GitHub Actions workflows were cleanly split to independently target, build, and test the GL and HGL modules.

v1.0.8

• Added the in_degree_map, out_degree_map and degree_map functions to the graph class
• Replaced per vertex in-degree calculating in the topological_sort algorithm with the in_degree_map function

v1.0.7

• Renamed the prim_mst function to edge_heap_prim_mst
• Added the vertex_heap_prim_mst function for finding the MST of a graph
• Added the edge_descriptor::incident_vertex_id method

v1.0.6

• Replaced the search tree type utility with a generic algorithm return type utility
• Added the predecessors_descriptor structure
• Modified the basic search algorithms to return a predecessors descriptor instead of a search tree
• Aligned tests and documentation

v1.0.5

• Renamed the perfect binary tree generator to use regular so that the naming is not confused with it being a perfect graph
• Renamed the pq_bfs template to pfs (priority-first search) so that it is not confused with a level by level search
• Aligned the corresponding documentation pages

v1.0.4

Added the GL_CONFIG_FORCE_INLINE configuration macro which enables the force inlining functionality

v1.0.3

• Renamed
  • The algorithm::detail namespace to algorithm::impl
  • The {bds/dfs}_impl functions to {bfs/dfs}
  • destination to target in the context of vertices
• Aligned the documentation

v1.0.2

• Goal: performance boost (std::function has a lot of overhead)
• Modified:
  • The c_<element>_callback to check if the type is callable with the given arguments instead of being convertible to std::function
  • The algorithms to use template types instead of std::function explicitly
• Added the c_optional_callback and c_optional_{vertex/edge}_callback concepts

v1.0.1

• Added the final keyword to the following classes:
  • {vertex/edge}_descriptor
  • adjacency_{list/matrix}
  • graph
• Marked the destructors of the property classes and the iterator_range class as virtual (if they are explicitly configured not to be final)

v1.0.0

Initial library release

Overview:

• Concept-based template header-only graph library for C++20 and newer standards
• Highly customizable and extensive core graph class which allows for the representation of directed and undirected graphs with vertex and edge properties using an adjacency list or an adjacency matrix implementation
• Compatibility with C++ standard library tools, e.g.: range-based loops, std algorithms, the ranges library, stream operations, etc.
• Predefined property types, topology generators and graph algorithms
• CMake integration
• No exteranal dependencies in the implementation
• MIT licence