BreadthFirstSearch.h

#ifndef PBAT_GRAPH_BREADTHFIRSTSEARCH_H
#define PBAT_GRAPH_BREADTHFIRSTSEARCH_H
 
#include "pbat/Aliases.h"
#include "pbat/common/Concepts.h"
#include "pbat/profiling/Profiling.h"
 
#include <queue>
 
namespace pbat::graph {
 
template <common::CIndex TIndex = Index>
struct BreadthFirstSearch
{
    using IndexType = TIndex;                
    using QueueType = std::queue<IndexType>; 
 
    BreadthFirstSearch() = default;
    BreadthFirstSearch(Eigen::Index n);
    void Reserve(Eigen::Index n);
    template <class FVisit, class TDerivedP, class TDerivedAdj>
    void operator()(
        Eigen::DenseBase<TDerivedP> const& ptr,
        Eigen::DenseBase<TDerivedAdj> const& adj,
        TIndex start,
        FVisit fVisit);
    Eigen::Index NumVertices() const { return visited.size(); }
 
    Eigen::Vector<bool, Eigen::Dynamic> visited; 
    QueueType queue;                             
};
 
template <common::CIndex TIndex>
inline BreadthFirstSearch<TIndex>::BreadthFirstSearch(Eigen::Index n)
{
    Reserve(n);
}
 
template <common::CIndex TIndex>
inline void BreadthFirstSearch<TIndex>::Reserve(Eigen::Index n)
{
    PBAT_PROFILE_NAMED_SCOPE("pbat.graph.BreadthFirstSearch.Reserve");
    visited.resize(n);
}
 
template <common::CIndex TIndex>
template <class FVisit, class TDerivedP, class TDerivedAdj>
inline void BreadthFirstSearch<TIndex>::operator()(
    Eigen::DenseBase<TDerivedP> const& ptr,
    Eigen::DenseBase<TDerivedAdj> const& adj,
    TIndex start,
    FVisit fVisit)
{
    PBAT_PROFILE_NAMED_SCOPE("pbat.graph.BreadthFirstSearch");
    visited.setConstant(false);
    queue.push(start);
    while (not queue.empty())
    {
        IndexType u = queue.front();
        queue.pop();
        if (not visited[u])
        {
            fVisit(u);
            visited[u]  = true;
            auto kBegin = ptr[u];
            auto kEnd   = ptr[u + 1];
            for (auto k = kBegin; k < kEnd; ++k)
            {
                IndexType v = static_cast<IndexType>(adj[k]);
                queue.push(v);
            }
        }
    }
}
 
} // namespace pbat::graph
 
#endif // PBAT_GRAPH_BREADTHFIRSTSEARCH_H