Home Original page

GitHub - rxdu/libgraph: C++ class templates for graph construction and search

libgraph: a C++ Graph Library

GitHub Workflow Status codecov

A modern, header-only C++11 library for graph construction and pathfinding algorithms. Designed for high performance with thread-safe concurrent searches and generic cost types.

Key Features

  • High Performance: O(m+n) space complexity, optimized priority queues, 35% faster search contexts
  • Thread-Safe: Concurrent searches using external SearchContext, no race conditions
  • Generic: Custom cost types, comparators, and state indexing - works with any data structure
  • Complete Algorithm Suite: A*, Dijkstra, BFS, DFS with unified framework
  • Robust: Comprehensive exception handling, structure validation, memory safety via RAII
  • Well-Documented: Extensive API reference, tutorials, and working examples

Generic State Types

struct GameState {
    int x, y, health, ammo;
    int64_t GetId() const { return y*1000 + x; }  // Auto-detected by DefaultIndexer
};
Graph<GameState> game_world;

Custom Cost Types

struct TravelCost {
    double time, distance, comfort;
    bool operator<(const TravelCost& other) const { /* lexicographic comparison */ }
};
Graph<Location, TravelCost> multi_criteria_graph;

Performance Optimization

graph.reserve(10000);           // Pre-allocate vertices
context.PreAllocate(10000);     // Pre-allocate search state
graph.AddVertices(state_list);  // Batch operations

Architecture Highlights

Modern C++ Design Patterns

  • CRTP Strategy Pattern: Zero-overhead polymorphism for search algorithms
  • RAII Memory Management: Automatic cleanup with std::unique_ptr, no memory leaks
  • Template Metaprogramming: Compile-time optimization and type safety
  • STL Compatibility: Full iterator support, range-based for loops

Template System

template<typename State, typename Transition = double, typename StateIndexer = DefaultIndexer<State>>
class Graph;
  • State: Your vertex data (locations, game states, etc.)
  • Transition: Edge weights (distance, time, cost, custom types)
  • StateIndexer: Automatic ID generation from states

Performance Characteristics

Optimal space complexity O(m+n) using adjacency lists:

Operation Time Complexity Space
Add/Find Vertex O(1) average O(1)
Add Edge O(1) O(1)
Search Algorithms O((m+n) log n) O(n)
Thread-Safe Search O((m+n) log n) O(n) per context

Thread Safety

Concurrent read-only searches are fully supported:

// Each thread gets independent search context
void worker_thread(const Graph<Location>* graph) {
    SearchContext<Location> context;  // Thread-local state
    auto path = Dijkstra::Search(graph, context, start, goal);  // Thread-safe
}

Thread-Safety Model:

  • Graph: Read-only access only during concurrent searches (const pointer accepted)
  • SearchContext: Each concurrent search requires its own instance
  • Strategy objects: Stateless, can be safely shared across threads
  • Legacy API: Overloads without SearchContext parameter are NOT thread-safe

Graph modifications require external synchronization (by design for performance).

Production Features (v3.1.0)

Rich search results with cost and diagnostics:

auto result = SearchAlgorithm<...>::SearchWithResult(graph, context, start, goal, strategy);
if (result.found) {
    std::cout << "Cost: " << result.total_cost << ", Expanded: " << result.nodes_expanded;
}

Bounded search for real-time systems:

auto limits = SearchLimits::MaxExpansions(1000);  // or SearchLimits::Timeout(50)
auto result = SearchAlgorithm<...>::SearchWithLimits(graph, context, start, goal, strategy, limits);

Multi-goal search (find nearest goal):

std::vector<Location> goals = {charging_station1, charging_station2, charging_station3};
auto result = Dijkstra::SearchMultiGoal(graph, context, robot_position, goals);
// result.goal_index tells which goal was reached

Build & Integration

Requirements

  • C++11 compatible compiler (GCC 4.8+, Clang 3.4+, MSVC 2015+)
  • CMake 3.10+ (for build system and examples)
  • Optional: Doxygen for API documentation

Integration Options

1. Header-Only

git clone https://github.com/rxdu/libgraph.git
cp -r libgraph/include/graph /your/project/include/
#include "graph/graph.hpp"
#include "graph/search/dijkstra.hpp"  // Ready to use!

2. CMake Submodule

# Add to your CMakeLists.txt
add_subdirectory(third_party/libgraph)
target_link_libraries(your_target PRIVATE xmotion::graph)

3. System Installation

mkdir build && cd build
cmake ..
sudo make install

# Use in your project
find_package(graph REQUIRED)
target_link_libraries(your_app PRIVATE xmotion::graph)

4. Debian Package Installation

mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release .. && make -j4 && cpack
sudo dpkg -i graph_3.1.0_amd64.deb  # Adjust version as needed

Build Examples and Tests

git clone --recursive https://github.com/rxdu/libgraph.git
mkdir build && cd build
cmake -DBUILD_TESTING=ON ..
cmake --build .

# Run examples
./bin/simple_graph_demo
./bin/thread_safe_search_demo

# Run comprehensive tests (317 tests, 100% pass rate)
./bin/utests

Your First Graph

#include "graph/graph.hpp"
#include "graph/search/dijkstra.hpp"

struct Location { int id; std::string name; };

// Create graph and add vertices
Graph<Location> map;
map.AddVertex({0, "Home"});
map.AddVertex({1, "Work"}); 
map.AddVertex({2, "Store"});

// Add weighted edges (distances)
map.AddEdge({0, "Home"}, {1, "Work"}, 5.0);
map.AddEdge({0, "Home"}, {2, "Store"}, 3.0);
map.AddEdge({2, "Store"}, {1, "Work"}, 4.0);

// Find optimal path
auto path = Dijkstra::Search(map, {0, "Home"}, {1, "Work"});
// Result: Home -> Store -> Work (7km total, shorter than direct 5km route)

Complete Getting Started Guide →

Documentation

For New Users

For Advanced Users

For Contributors

Contributing & Support

Getting Help

Contributing

  • Fork & Pull Request workflow for contributions
  • Follow existing code style and patterns
  • Add tests for new functionality
  • Update documentation for public API changes

License & Citation

This library is distributed under MIT License.

@misc{libgraph2025,
  title={libgraph: High-Performance C++ Graph Library},
  author={Ruixiang Du and contributors},
  year={2025},
  url={https://github.com/rxdu/libgraph}
}

→ Complete Roadmap & TODO List

Built for the C++ community