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
#pragma once


#include <vector><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <queue><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.

#include "snippet/iterations.hpp"
#include "internal/dev_env.hpp"
#include "structure/graph.hpp"


template<class Graph>
template<class comparer>
bool uni::internal::graph_impl::mixin<Graph>::sort_topologically_with_priority(uni::vector<node_type> *const sorted) const noexcept(NO_EXCEPT) {
    sorted->clear();

    std::vector<size_type> in_degs(this->size());
    ITR(v, *this) ITR(e, v)  ++in_degs[e.to];

    std::priority_queue<node_type,std::vector<node_type>,comparer> que;
    REP(i, this->size()) if(in_degs[i] == 0) que.push(i);

    while(not que.empty()) {
        const node_type v = que.top(); que.pop();
        ITR(u, (*this)[v]) if(!(--in_degs[u.to])) que.push(u.to);
        sorted->push_back(v);
    }

    return std::ranges::ssize(*sorted) == std::ranges::ssize(*this);
}

template<class Graph>
template<class comparer>
bool uni::internal::graph_impl::mixin<Graph>::sort_topologically_with_priority() const noexcept(NO_EXCEPT) {
    uni::vector<node_type> vs;
    return this->sort_topologically_with_priority<comparer>(&vs);
}


template<class Graph>
bool uni::internal::graph_impl::mixin<Graph>::sort_topologically(uni::vector<node_type> *const sorted) const noexcept(NO_EXCEPT) {
    sorted->clear();

    std::vector<size_type> in_degs(this->size());
    ITR(v, *this) ITR(e, v)  ++in_degs[e.to];

    std::queue<node_type> que;
    REP(i, this->size()) if(in_degs[i] == 0) que.push(i);

    while(not que.empty()) {
        const node_type v = que.front(); que.pop();
        ITR(u, (*this)[v]) if(!(--in_degs[u.to])) que.push(u.to);
        sorted->push_back(v);
    }

    return std::ranges::ssize(*sorted) == std::ranges::ssize(*this);
}

template<class Graph>
bool uni::internal::graph_impl::mixin<Graph>::sort_topologically() const noexcept(NO_EXCEPT) {
    std::vector<node_type> vs;
    return this->sort_topologically(&vs);
}