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
#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 <stack><--- 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>
bool uni::internal::graph_impl::mixin<Graph>::is_bipartite() const noexcept(NO_EXCEPT) {
    valarray<std::int8_t> color(0, this->vertices());
    this->is_bipartite(&color);
    return true;
}


template<class Graph>
template<class Colors>
bool uni::internal::graph_impl::mixin<Graph>::is_bipartite(Colors *const color) const noexcept(NO_EXCEPT) {
    color->assign(this->vertices(), 0);

    REP(s, this->vertices()) {
        if(color->operator[](s) != 0) continue;

        std::stack<size_type> stack;
        stack.push(s);
        color->operator[](s) = 1;

        while(not stack.empty()) {
            auto v = stack.top(); stack.pop();
            auto c = color->operator[](v);

            ITR(nv, this->operator[](v)) {
                if(color->operator[](nv) == c) return false;
                if(color->operator[](nv) == 0) {
                    color->operator[](nv) = -c;
                    stack.push(nv);
                }
            }
        }
    }

    return true;
}