libgraph

C++ class templates for graph construction and search

Project maintained by rxdu Hosted on GitHub Pages — Theme by mattgraham

Search Framework Migration Guide

Overview

The libgraph search algorithms have been consolidated using a modern strategy pattern approach, eliminating code duplication and providing a unified framework for all search algorithms.

What Changed

Before (Multiple Implementations)

After (Unified Framework)

API Compatibility

✅ No Code Changes Required

Existing code continues to work without changes:

// All these continue to work exactly as before
auto path = Dijkstra::Search(graph, start, goal);
auto path = AStar::Search(graph, start, goal, heuristic);
auto path = DijkstraThreadSafe::Search(graph, context, start, goal);
auto path = AStarThreadSafe::Search(graph, context, start, goal, heuristic);

Thread Safety

The new implementation provides thread safety when using SearchContext:

// Thread-safe (recommended for concurrent usage)
SearchContext<State, Transition, StateIndexer> context;
auto path = Dijkstra::Search(graph, context, start, goal);

// Legacy mode (backward compatible, but not thread-safe)
auto path = Dijkstra::Search(graph, start, goal);

Benefits of the New Framework

1. Code Reduction

2. Easy Algorithm Addition

Adding a new search algorithm now requires only a strategy implementation:

// Example: BFS strategy (see bfs_strategy.hpp)
template<typename State, typename Transition, typename StateIndexer>
class BfsStrategy : public SearchStrategy<BfsStrategy<...>, State, Transition, StateIndexer> {
    CostType GetPriorityImpl(const SearchInfo& info) const noexcept {
        return info.g_cost;  // FIFO behavior
    }
    
    bool RelaxVertexImpl(...) const {
        // BFS-specific logic
    }
};

3. Performance

4. Thread Safety by Default

Architecture Overview

Strategy Pattern Implementation

SearchAlgorithm<Strategy>  (search_algorithm.hpp)
    ├── Common search loop logic
    ├── Priority queue management  
    ├── Path reconstruction
    └── Uses Strategy for:
        ├── Priority calculation
        ├── Vertex initialization
        ├── Edge relaxation
        └── Goal checking

Concrete Strategies:
├── DijkstraStrategy  (dijkstra_strategy.hpp)
├── AStarStrategy     (astar_strategy.hpp)
└── BfsStrategy       (bfs_strategy.hpp)

Files Structure

include/graph/search/
├── search_strategy.hpp      # Base strategy interface (CRTP)
├── search_algorithm.hpp     # Unified search template
├── search_context.hpp       # Thread-safe search state + Path type alias
├── dijkstra.hpp            # Dijkstra strategy + public API (consolidated)
├── astar.hpp               # A* strategy + public API (consolidated)
└── bfs.hpp                 # BFS strategy + public API (consolidated)

Note: Each algorithm file now contains both the strategy implementation and public API in a single consolidated file, eliminating the previous dual-file approach.

Migration for Advanced Users

Custom Search Algorithms

If you want to implement custom search algorithms, use the strategy pattern:

template<typename State, typename Transition, typename StateIndexer>
class CustomStrategy : public SearchStrategy<CustomStrategy<...>, State, Transition, StateIndexer> {
public:
    CostType GetPriorityImpl(const SearchInfo& info) const noexcept {
        // Return priority for open list ordering
        return info.f_cost;
    }
    
    void InitializeVertexImpl(SearchInfo& info, vertex_iterator vertex, 
                             vertex_iterator goal_vertex) const {
        // Initialize search information for starting vertex
        info.g_cost = 0.0;
        info.h_cost = CalculateHeuristic(vertex, goal_vertex);
        info.f_cost = info.g_cost + info.h_cost;
    }
    
    bool RelaxVertexImpl(SearchInfo& current_info, SearchInfo& successor_info,
                        vertex_iterator successor_vertex, vertex_iterator goal_vertex,
                        CostType edge_cost) const {
        // Return true if successor was improved
        CostType new_cost = current_info.g_cost + edge_cost;
        if (new_cost < successor_info.g_cost) {
            successor_info.g_cost = new_cost;
            successor_info.h_cost = CalculateHeuristic(successor_vertex, goal_vertex);
            successor_info.f_cost = successor_info.g_cost + successor_info.h_cost;
            return true;
        }
        return false;
    }
};

Thread-Safe Usage Patterns

// Pattern 1: Single search
SearchContext<State, Transition, StateIndexer> context;
auto path = Dijkstra::Search(graph, context, start, goal);

// Pattern 2: Multiple searches on same graph
std::thread t1([&]() {
    SearchContext<State, Transition, StateIndexer> context1;
    auto path1 = Dijkstra::Search(graph, context1, start1, goal1);
});

std::thread t2([&]() {
    SearchContext<State, Transition, StateIndexer> context2;  
    auto path2 = AStar::Search(graph, context2, start2, goal2, heuristic);
});

Future Roadmap

The new framework enables easy addition of:

Troubleshooting

Build Issues

If you encounter build issues, ensure you’re including the correct headers:

// New consolidated headers
#include "graph/search/dijkstra.hpp"
#include "graph/search/astar.hpp" 
#include "graph/search/bfs.hpp"

// Not needed anymore (aliased automatically)
// #include "graph/search/dijkstra_threadsafe.hpp"
// #include "graph/search/astar_threadsafe.hpp"

Type Deduction Issues

If you encounter template deduction issues, use explicit template parameters:

auto path = Dijkstra::Search<MyState, double, MyIndexer>(graph, context, start, goal);

Summary

The new search framework provides:

The consolidation is complete and all existing functionality is preserved while providing a much cleaner, more maintainable architecture.