cpp-gl/include/gl/algorithm/templates/pfs.hpp at 8b2245c2bc9dcd84cae6f00b194699f03fc49e94 · SpectraL519/cpp-gl · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// Copyright (c) 2024-2026 Jakub Musiał
// This file is part of the CPP-GL project (https://github.com/SpectraL519/cpp-gl).
// Licensed under the MIT License. See the LICENSE file in the project root for full license information.

#pragma once

#include "gl/algorithm/core.hpp"
#include "gl/algorithm/traits.hpp"
#include "gl/algorithm/util.hpp"

#include <queue>

namespace gl::algorithm {

template <
    traits::c_graph G,
    traits::c_predicate<search_node<G>, search_node<G>> PQCompare,
    traits::c_forward_range_of<search_node<G>> InitQueueRangeType = std::vector<search_node<G>>,
    traits::c_optional_predicate<typename G::id_type> VisitVertexPredicate = empty_callback,
    traits::c_optional_predicate<typename G::id_type, typename G::id_type> VisitCallback =
        empty_callback,
    traits::c_decision_predicate<typename G::id_type, const typename G::edge_type&>
        EnqueueVertexPred = empty_callback,
    traits::c_optional_callback<void, typename G::id_type> PreVisitCallback = empty_callback,
    traits::c_optional_callback<void, typename G::id_type> PostVisitCallback = empty_callback>
bool pfs(
    const G& graph,
    const PQCompare& pq_compare,
    const InitQueueRangeType& initial_queue_content,
    VisitVertexPredicate visit_vertex_pred = {},
    VisitCallback visit = {},
    EnqueueVertexPred enqueue_vertex_pred = {},
    PreVisitCallback pre_visit = {},
    PostVisitCallback post_visit = {}
) {
    if (std::ranges::empty(initial_queue_content))
        return false;

    // prepare the node queue
    using queue_type = std::priority_queue<search_node<G>, std::vector<search_node<G>>, PQCompare>;
    queue_type q(pq_compare);

    for (const auto& node : initial_queue_content)
        q.push(node);

    // search the graph
    while (not q.empty()) {
        const auto node = q.top();
        q.pop();

        if constexpr (not traits::c_empty_callback<VisitVertexPredicate>)
            if (not visit_vertex_pred(node.vertex_id))
                continue;

        if constexpr (not traits::c_empty_callback<PreVisitCallback>)
            pre_visit(node.vertex_id);

        if constexpr (not traits::c_empty_callback<VisitCallback>)
            if (not visit(node.vertex_id, node.pred_id))
                return false;

        for (const auto& edge : graph.out_edges(node.vertex_id)) {
            const auto target_vertex_id = edge.other(node.vertex_id);
            const auto enqueue = enqueue_vertex_pred(target_vertex_id, edge);
            if (enqueue == decision::abort)
                return false;
            if (enqueue)
                q.emplace(target_vertex_id, node.vertex_id);
        }
        if constexpr (not traits::c_empty_callback<PostVisitCallback>)
            post_visit(node.vertex_id);
    }

    return true;
}

} // namespace gl::algorithm