bobluppes / bobluppes/graaf

Document thread-safety guarantees for graph and algorithm APIs

Open
#323 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
413
Forks
67
Avg merge
7h 24m
Merged PRs (30d)
53

Description

## Summary

Neither the API docs nor the header comments state whether any `graph`, `tree`, or algorithm APIs are safe to use concurrently from multiple threads (e.g. concurrent reads, or reads during writes).

## Current state

- A repo-wide search for "thread" across `include/` and `docs/docs/` returns no results — there is no thread-safety documentation anywhere.
- `graph` ([include/graaflib/graph.h](../blob/main/include/graaflib/graph.h)) stores vertices/edges in plain `std::unordered_map`/`std::unordered_set` members with no internal synchronization, which is expected for a low-level container, but this contract is never made explicit to users.
- The [architecture doc](../blob/main/docs/docs/quickstart/basics/architecture.md) and other quickstart pages describe the object model but say nothing about concurrent access.

## Why this matters

Many production systems that would use a graph library do so from multi-threaded services (e.g. building/querying a graph concurrently, or running independent algorithms over a shared read-only graph from a thread pool). Without an explicit contract, users are left to either assume safety (risking data races) or over-synchronize defensively (losing performance) — both bad outcomes. Even a minimal, explicit statement of the current guarantees ("not thread-safe for concurrent mutation; concurrent const reads from multiple threads are safe") resolves this ambiguity and is standard practice for STL-adjacent containers, which Graaf's `graph` class closely resembles.

## Suggested resolution

- Document the thread-safety contract for `graph`/`tree` mutation methods (`add_vertex`, `add_edge`, `remove_vertex`, `remove_edge`, etc.) and for read-only methods (`get_vertices`, `get_edges`, algorithm entry points).
- Follow the standard-library convention (const methods on a shared instance are safe to call concurrently from multiple threads; non-const methods require external synchronization) if that's what the current implementation already provides, and verify this with a targeted concurrency test (e.g. under TSan, see the related sanitizer-CI issue).
- Add this as a dedicated section in the architecture docs.

## Acceptance criteria

- [ ] Thread-safety guarantees (or lack thereof) are documented for the public `graph`/`tree` API and for algorithm entry points.
- [ ] The stated guarantees are verified (e.g. via a ThreadSanitizer test exercising concurrent const access).

Contributor guide

Open the contributing guide

Research direction

The issue points to include/graaflib/graph.h and docs/docs/quickstart/basics/architecture.md. Start by examining the graph class's public methods to understand which are const. Write a small test using ThreadSanitizer to verify concurrent const reads are safe. The acceptance criteria require updating the architecture docs with a new thread-safety section and adding a test.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
documentation
Issue type
Documentation
Difficulty
3/5
Estimated time
1-2 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
65/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.