compile-time dfs

cdfs.cpp

#include <iostream>
#include <cstring>
#include <type_traits>
#include <utility>
#include <tuple>

// graph descriptions
template <int... Next>
using AdjacentList = std::integer_sequence<int, Next...>;

template <int VertexId, int... Next>
struct Vertex {
    static constexpr auto Id = VertexId;
    using NextIds = AdjacentList<Next...>;
};

template <class... VertexT>
struct Graph {
    using vertex_list  = std::tuple<VertexT...>;
};

//------------------

// find Vertex in Vertex list by specified Id
template <int VertexId, class... VertexT>
struct Matcher;

template <int VertexId>
struct Matcher<VertexId> {
    static_assert(VertexId != VertexId, "vertex not found!");
};

template <int VertexId, class Vertex, class ... Rest>
constexpr auto match_first_or_continue() {
    if constexpr (Vertex::Id == VertexId) {
        return Vertex{};
    }else{
        return typename Matcher<VertexId, Rest...>::vertex{};
    }
}

template <int VertexId, class Vertex, class ... Rest>
struct Matcher<VertexId, Vertex, Rest...>{
    using vertex = decltype(match_first_or_continue<VertexId, Vertex, Rest...>());
};




// retrieve list of adjacent vertex ids:
template <int VertexId, class Graph>
struct GetAdjacent;

// helper: transforms tuple to variadic args pack
// result -- returning type
template <int VertexId, class... VertexT>
auto get_adjacent_impl (const std::tuple<VertexT...>& vertexes) {
    using vertex = typename Matcher<VertexId, VertexT...>::vertex;
    using adjucent = typename vertex::NextIds;
    return adjucent{};
}; 

template <int VertexId, class Graph>
struct GetAdjacent {
    using vertex_ids = decltype(get_adjacent_impl<VertexId>(typename Graph::vertex_list{}));
};


template <int x, int ... ids>
constexpr bool contains(const std::integer_sequence<int, ids...>&){
    return ((x == ids) || ... || false );
}

template <int x, int ... ids>
constexpr std::integer_sequence<int, x, ids...> append(const std::integer_sequence<int, ids...>&) {
    return {};
}

//----------------------
// Dfs implementation
template <class Graph, class Visited, int... ids>
struct VisitSequence; // visit each id in ids... and populate Visited list

template <class Graph, class Visited>
struct VisitSequence<Graph, Visited> {
    using visited = Visited; // ids... empty. Terminate recursion
};

// forward declaration for inderect recursion
template <int start, class Graph, class Visited> 
constexpr auto visit();

template <class Graph, class Visited, int x, int... ids>
struct VisitFirstAndThenOthers {
    using NewVisited = decltype(visit<x, Graph, Visited>());
    using visited = typename VisitSequence<Graph, NewVisited, ids...>::visited;
};


template <class Graph, class Visited, int x, int... ids>
struct VisitSequence<Graph, Visited, x, ids...> {
    using visited = typename VisitFirstAndThenOthers<Graph, Visited, x, ids...>::visited;
};

// another helper for pattern-matching
template <class Graph, class Visited, int... ids>
constexpr auto visit_sequence(const std::integer_sequence<int, ids...>&){
    using Visiter = VisitSequence<Graph, Visited, ids...>;
    return typename Visiter::visited{};
}

// Dfs logic
template <int start, class Graph, class Visited> 
constexpr auto visit() {
    if constexpr (contains<start>(Visited{})) {
        return Visited{};
    }else{
        using NewVisited = decltype(append<start>(Visited{}));
        using adj = GetAdjacent<start, Graph>;
        return visit_sequence<Graph, NewVisited>(typename adj::vertex_ids{});
    }
}

template <int start, class Graph>
struct RunDfs {
    using visited = decltype(visit<start, Graph, std::integer_sequence<int>>());
};

// helper to perform pattern-matching with integer sequence
template <int... ids>
void display(const std::integer_sequence<int, ids...>&){
    ((std::cout << ids << " "), ... );
}

int main() {
    using V1 = Vertex<0, 1, 2, 3>;
    using V2 = Vertex<1, 0, 2>;
    using V3 = Vertex<2, 1, 3>;
    using V4 = Vertex<3>;

    using G = Graph<V1, V2, V3, V4>;
    
    using DfsVisiter = RunDfs<1, G>;

    display(DfsVisiter::visited{});

	return 0;
}

ставь лайк если ты пришел сюда из твитора

ставь лайк если ты пришел сюда из твитора

Не нашёл лайки :c

👍
@multiprogramm