algos

Комбинаторные алгоритмы (combinatorics.h):

• генерация подмножеств данного множества
• генерация перестановок

Строковые алгоритмы (string.h):

• префикс функция
• алгоритм Кнута-Морриса-Пратта

Графовые алгоритмы (graph.h):

• поиск в ширину (bfs)
• поиск в ширину с посетителем (bfs)
• поиск в глубину (dfs)
• поиск в глубину с посетителем (dfs)

Генерация подмножеств данного множества

#include "combinatorics.h"
#include <iostream>

int main() {
    std::string s = "abc";
    Subset<char> subset(s.begin(), s.end());
    do {
        for (const auto &item : subset) {
            if (item) {
                std::cout << item.value() << " ";

            } else {
                std::cout << "x "; // отсутствие элемента в подмножестве
            }
        }
        std::cout << std::endl;
    } while (subset.next());
    return 0;
}

Output:

x x x 
a x x 
x b x 
a b x 
x x c 
a x c 
x b c 
a b c 

Генерация перестановок

#include "combinatorics.h"
#include <iostream>

int main() {
    std::string str = "abc";
    Permutations<char> permutations(str.cbegin(), str.cend());
    do {
        auto it = permutations.begin();
        while (it != permutations.end()) {
            std::cout << *it << " ";
            ++it;
        }
        std::cout << std::endl;
    } while ((permutations.next()));
    return 0;
}

Output:

a b c 
a c b 
b a c 
b c a 
c a b 
c b a

Префикс функция

#include "string.h"
#include <iostream>

int main() {
    auto pf = prefix_function("abacaba");
    for (auto value : pf) {
        std::cout << value << " ";
    }
    std::cout << std::endl;
    return 0;
}

Output:

0 0 1 0 1 2 3 

Алгоритм Кнута-Морриса-Пратта

#include "string.h"
#include <iostream>

int main() {
    auto res = kmp("ababcxabdabcxabcxabcde", "abcxabcde");
    for (auto pos : res) {
        std::cout << pos << std::endl;
    }
    return 0;
}

Output:

13

Поиск в ширину, bfs

#include "graph.h"
#include <iostream>

using namespace algos;

int main() {
    Graph<std::string, int> g;
    g.add_edge("A", "B", 1);
    g.add_edge("A", "C", 1);
    g.add_edge("B", "D", 1);
    g.add_edge("D", "E", 1);
    auto res = g.bfs("A");
    for (auto &item : {"A", "B", "C", "D", "E"}) {
        auto value = res.find(item);
        std::cout << "id = " << item << ", depth = " << value->second.depth << std::endl;
    }
    return 0;
}

Output:

id = A, depth = 0
id = B, depth = 1
id = C, depth = 1
id = D, depth = 2
id = E, depth = 3

Поиск в ширину с посетителем, bfs

#include "graph.h"
#include <iostream>

using namespace algos;

int main() {
    Graph<std::string, int> g;
    g.add_edge("A", "B", 1);
    g.add_edge("A", "C", 1);
    g.add_edge("B", "D", 1);
    g.add_edge("D", "E", 1);
    g.bfs_visitor("A", [](auto type, auto &&event) {
        switch (type) {
        // Событие вызывается, когда алгоритм впервые встречает вершину в обходе
        case BfsEventType::DiscoverVertex:
            std::cout << "DiscoverVertex " << event.curr << std::endl;
            break;
        // Событие вызывается до того, как вы начнете исследовать вершину (извлекая ее из очереди)
        case BfsEventType::ExamineVertex:
            std::cout << "ExamineVertex = " << event.curr << std::endl;
            break;
        // Событие срабатывает, когда исследуемое ребро является ребром дерева после обхода
        case BfsEventType::IsTreeEdge:
            std::cout << "IsTreeEdge = " << event.curr << " " << event.to.value() << std::endl;
            break;
        // Событие срабатывает, когда исследуемое ребро не является ребром дерева после обхода
        case BfsEventType::IsNotTreeEdge:
            std::cout << "IsNotTreeEdge = " << event.curr << " " << event.to.value() << std::endl;
            break;
        // Событие вызывается, если в момент исследования целевая вершина выделена серым цветом.
        // Серый цвет означает, что вершина в данный момент находится в очереди
        case BfsEventType::GrayTarget:
            std::cout << "GrayTarget = " << event.curr << std::endl;
            break;
        // Событие вызывается, если в момент исследования целевой узел окрашен в черный цвет.
        // Черный цвет означает, что вершина больше не находится в очереди
        case BfsEventType::BlackTarget:
            std::cout << "BlackTarget = " << event.curr << std::endl;
            break;
        // Событие вызывается после изучения всех исходящих ребер и всех соседних вершин
        case BfsEventType::FinishVertex:
            std::cout << "FinishVertex = " << event.curr << std::endl;
            break;
        default:
            break;
        }
    });

    return 0;
}

Output:

DiscoverVertex A
ExamineVertex = A
IsTreeEdge = A C
DiscoverVertex C
GrayTarget = A
IsTreeEdge = A B
DiscoverVertex B
GrayTarget = A
FinishVertex = A
ExamineVertex = C
IsNotTreeEdge = C A
BlackTarget = C
FinishVertex = C
ExamineVertex = B
IsTreeEdge = B D
DiscoverVertex D
GrayTarget = B
IsNotTreeEdge = B A
BlackTarget = B
FinishVertex = B
ExamineVertex = D
IsTreeEdge = D E
DiscoverVertex E
GrayTarget = D
IsNotTreeEdge = D B
BlackTarget = D
FinishVertex = D
ExamineVertex = E
IsNotTreeEdge = E D
BlackTarget = E
FinishVertex = E

Поиск в глубину, dfs

#include "graph.h"
#include <iostream>

using namespace algos;

int main() {
    Graph<std::string, int> g;
    g.add_edge("A", "B", 1);
    g.add_edge("A", "C", 1);
    g.add_edge("B", "D", 1);
    g.add_edge("D", "E", 1);
    auto res = g.dfs("A");
    for (auto &item : {"A", "B", "C", "D", "E"}) {
        auto value = res.find(item);
        std::cout << "id = " << item << ", depth = " << value->second.depth << std::endl;
    }
    return 0;
}

Output:

id = A, depth = 0
id = B, depth = 1
id = C, depth = 1
id = D, depth = 2
id = E, depth = 3

Поиск в глубину с посетителем, dfs

#include "graph.h"
#include <iostream>

using namespace algos;

int main() {
    Graph<std::string, int> g;
    g.add_edge("A", "B", 1);
    g.add_edge("A", "C", 1);
    g.add_edge("B", "D", 1);
    g.add_edge("D", "E", 1);
    g.dfs_visitor("A", [](auto type, auto &&event) {
        switch (type) {
        // Событие вызывается, когда алгоритм впервые встречает вершину в обходе
        case DfsEventType::DiscoverVertex:
            std::cout << "DiscoverVertex " << event.curr << std::endl;
            break;
        // Событие вызывается до того, как вы начнете исследовать вершину
        case DfsEventType::ExamineVertex:
            std::cout << "ExamineVertex = " << event.curr << std::endl;
            break;
        // Событие срабатывает, когда исследуемое ребро является ребром дерева после обхода
        case DfsEventType::IsTreeEdge:
            std::cout << "IsTreeEdge = " << event.curr << " " << event.to.value() << std::endl;
            break;
        // // Событие срабатывает, когда мы возвращаемся к предку, из которого мы исследовали вершину
        case DfsEventType::ReturnParent:
            std::cout << "ReturnParent = " << event.curr << " " << event.to.value() << std::endl;
            break;
        // Событие срабатывает, когда мы пытаемся пойти по обратному ребру
        case DfsEventType::BackEdge:
            std::cout << "BackEdge = " << event.curr << std::endl;
            break;
        // Событие срабатывает, когда мы пытаемся пройти по прямому или поперечному ребру (только для ориентированного
        // графа)
        case DfsEventType::ForwardOrCrossEdge:
            std::cout << "ForwardOrCrossEdge = " << event.curr << std::endl;
            break;
        // Событие вызывается после изучения всех исходящих ребер и всех соседних вершин
        case DfsEventType::FinishVertex:
            std::cout << "FinishVertex = " << event.curr << std::endl;
            break;
        default:
            break;
        }
    });
    return 0;
}

Output:

DiscoverVertex A
ExamineVertex = A
IsTreeEdge = A C
DiscoverVertex C
ExamineVertex = C
FinishVertex = C
ReturnParent = A C
ExamineVertex = A
IsTreeEdge = A B
DiscoverVertex B
ExamineVertex = B
IsTreeEdge = B D
DiscoverVertex D
ExamineVertex = D
IsTreeEdge = D E
DiscoverVertex E
ExamineVertex = E
FinishVertex = E
ReturnParent = D E
ExamineVertex = D
FinishVertex = D
ReturnParent = B D
ExamineVertex = B
FinishVertex = B
ReturnParent = A B
FinishVertex = A