Поиск в ширину (1) СППМиИ

// ConsoleApplication1.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <fstream>
#include <numeric>

using graph = std::vector<std::vector<int>>;
using std::vector;

//базовый поиск в ширину
void BFS(const graph& g, int s, vector<int>& d, vector<int>& p, bool need_init = true)
{
    int infty = g.size();
    if (need_init)
    {
        d.assign(g.size(), infty);
        p.assign(g.size(), -1);
    }
    d[s] = 0;
    std::queue<int> Q;
    Q.push(s);
    while (Q.size())
    {
        auto u = Q.front();
        Q.pop();
        for (auto v : g[u])
        {
            if (d[v] == infty)
            {
                d[v] = d[u] + 1;
                p[v] = u;
                Q.push(v);
            }
        }
    }
}

int count_connected_parts(const graph& g)
{
    int count = 0;
    int infty = g.size();
    vector<int> d(g.size(), infty);
    vector<int> p(g.size(), -1);
    for (size_t s = 0; s < g.size(); s++)
    {
        if (d[s] == infty)
        {
            BFS(g, s, d, p, false);
            ++count;
        }
    }
    return count;
}

vector<int> vertices_from_shortest_path(const graph& g, int a, int b)
{
    int infty = g.size();
    vector<int> da, db, p;
    BFS(g, a, da, p, true);
    BFS(g, b, db, p, true);
    vector<int> res;
    for (size_t u = 0; u < g.size(); u++)
    {
        if (da[u] + db[u] == da[b])
            res.push_back(u);
    }
    return res;
}

graph get_graph_from_stream(std::istream&& inp)
{
    int n;
    inp >> n;
    graph g(n);
    int a, b;
    while (inp >> a >> b)
    {
        g[a].push_back(b);
        g[b].push_back(a);
    }
    return g;
}

//https://pastebin.com/6MDNTGUj

bool is_tree_graph(const graph& G)
{
    int edge_count = std::accumulate(G.begin(), G.end(), 0,
        [](auto s, const auto& list) {return s + list.size(); });
    return edge_count == G.size() - 1 && count_connected_parts(G) == 1;
}

vector<vector<vector<int>>> get_tree_code(const graph& T, int s)
{
    vector<int> d, p;
    BFS(T, s, d, p, true);
    int level_count = *std::max_element(begin(d), end(d)) + 1;
    vector<vector<int>> levels(level_count);
    for (size_t u = 0; u < T.size(); u++)
        levels[d[u]].push_back(u);
    vector<vector<vector<int>>> code(level_count);
    vector<int> mark(T.size());
    for (int lvl = level_count - 1; lvl >= 0; lvl--)
    {
        vector<std::pair<vector<int>, int>> level_code;
        for (auto u : levels[lvl])
        {
            vector<int> vertex_code;
            for (auto v : T[u])
                if (d[v] == lvl + 1)
                    vertex_code.push_back(mark[v]);
            std::sort(vertex_code.begin(), vertex_code.end());
            level_code.emplace_back(std::move(vertex_code), u);
        }
        std::sort(level_code.begin(), level_code.end());
        int cur_mark = 0;
        mark[level_code[0].second] = cur_mark;
        for (size_t i = 1; i < level_code.size(); i++)
        {
            if (level_code[i].first != level_code[i - 1].first)
                ++cur_mark;
            mark[level_code[i].second] = cur_mark;
        }
        for (auto& [vertex_code, vertex] : level_code)
            code[lvl].emplace_back(std::move(vertex_code));
    }
    return code;
}

vector<vector<vector<int>>> get_tree_code_advanced(const graph& T, int s,
    vector<vector<int>> &_levels, vector<int> &_mark)
{
    vector<int> d, p;
    BFS(T, s, d, p, true);
    int level_count = *std::max_element(begin(d), end(d)) + 1;
    vector<vector<int>> levels(level_count);
    for (size_t u = 0; u < T.size(); u++)
        levels[d[u]].push_back(u);
    vector<vector<vector<int>>> code(level_count);
    vector<int> mark(T.size());
    for (int lvl = level_count - 1; lvl >= 0; lvl--)
    {
        vector<std::pair<vector<int>, int>> level_code;
        for (auto u : levels[lvl])
        {
            vector<int> vertex_code;
            for (auto v : T[u])
                if (d[v] == lvl + 1)
                    vertex_code.push_back(mark[v]);
            std::sort(vertex_code.begin(), vertex_code.end());
            level_code.emplace_back(std::move(vertex_code), u);
        }
        std::sort(level_code.begin(), level_code.end());
        int cur_mark = 0;
        mark[level_code[0].second] = cur_mark;
        for (size_t i = 1; i < level_code.size(); i++)
        {
            if (level_code[i].first != level_code[i - 1].first)
                ++cur_mark;
            mark[level_code[i].second] = cur_mark;
        }
        for (auto& [vertex_code, vertex] : level_code)
            code[lvl].emplace_back(std::move(vertex_code));
    }
    _levels = std::move(levels);
    _mark = std::move(mark);
    return code;
}

bool is_isomorphic_tree(const graph& T1, const graph& T2,
    vector<int> &isomorphism)
{
    if (!is_tree_graph(T1) || !is_tree_graph(T2))
        return false;
    if (T1.size() != T2.size())
        return false;
    vector<vector<int>> levels1, levels2;
    vector<int> mark1, mark2;
    auto codeT1 = get_tree_code_advanced(T1, 0,levels1,mark1);
    for (size_t u = 0; u < T2.size(); u++)
    {
        if (codeT1 == get_tree_code_advanced(T2, u, levels2, mark2))
        {
            isomorphism.resize(T1.size());
            isomorphism[0] = u;
            for (int l = 1; l < levels1.size(); l++)
            {
                vector<std::pair<int, int>> t1level, t2level;
                for (auto u : levels1[l])
                    t1level.push_back({ mark1[u],u });
                for (auto u : levels2[l])
                    t2level.push_back({ mark2[u],u });
                std::sort(begin(t1level), end(t1level));
                std::sort(begin(t2level), end(t2level));
                for (int k = 0; k < t1level.size(); k++)
                    isomorphism[t1level[k].second] = t2level[k].second;
            }
            return true;
        }
    }
    return false;
}

using labyrinth = vector<vector<char>>;

labyrinth get_labyrinth_from_stream(std::istream& inp)
{
    int row, col;
    inp >> row >> col;
    labyrinth lab(row, vector<char>(col));
    for (size_t i = 0; i < row; i++)
    {
        for (size_t j = 0; j < col; j++)
        {
            char c;
            inp >> c;
            lab[row - i - 1][j] = c;
        }
    }
    return lab;
}

struct cell { int r, c; };

template <typename T>
T& operator^(vector<vector<T>>& data, cell c)
{
    return data[c.r][c.c];
}

template <typename T>
T operator^(const vector<vector<T>>& data, cell c)
{
    return data[c.r][c.c];
}

vector<cell> adjoint_cells(const labyrinth& lab, cell c)
{
    vector<cell> res;
    for(int i=-1; i<=1; ++i)
    {
        if (i != 0 && i + c.r >= 0 && i + c.r < lab.size())
            res.push_back({ i + c.r,c.c });
        if (i != 0 && i + c.c >= 0 && i + c.c < lab[0].size())
            res.push_back({ c.r,i+c.c });
    }
    return res;
}

void BFSlab(const labyrinth& lab, cell s, vector<vector<int>>& d,
    vector<vector<cell>>& p)
{
    int infty = lab.size() * lab[0].size();
    d.assign(lab.size(), vector<int>(lab[0].size(),infty));
    p.assign(lab.size(), vector<cell>(lab[0].size(), {-1,-1}));
    d^s = 0;
    std::queue<cell> Q;
    Q.push(s);
    while (Q.size())
    {
        auto c = Q.front();
        Q.pop();
        for (auto v : adjoint_cells(lab, c))
        {
            if ((lab^v) != '#' && (d ^ v) == infty)
            {
                d^v = (d^c) + 1;
                p^v = c;
                Q.push(v);
            }
        }
    }
}


int main()
{
    //auto g = get_graph_from_stream(std::ifstream("g.txt"));
    //auto ab_shortest_path = vertices_from_shortest_path(g, 2, 10);
    //std::cout << count_connected_parts(g) << std::endl;
    //for (auto u : ab_shortest_path)
    //    std::cout << u << " ";
    //std::cout << std::endl;
    //std::cout << "Hello World!\n";

    //auto T = get_graph_from_stream(std::ifstream("tree.txt"));
    //auto code = get_tree_code(T, 1);
    //for (auto& level_code : code)
    //{
    //    for (auto& vertex_code : level_code)
    //    {
    //        std::cout << "{";
    //        for (int i = 0; i < vertex_code.size(); ++i)
    //            std::cout << vertex_code[i] << (i < vertex_code.size() - 1 ? "," : "");
    //        std::cout << "} ";
    //    }
    //    std::cout << std::endl;
    //}
    std::ifstream inp("lab.txt");
    auto lab = get_labyrinth_from_stream(inp);
    vector<vector<int>> d;
    vector<vector<cell>> p;
    BFSlab(lab, { 0,0 }, d, p);
    std::cout << (d ^ cell{ 7,7 }) << std::endl;
}

// Запуск программы: CTRL+F5 или меню "Отладка" > "Запуск без отладки"
// Отладка программы: F5 или меню "Отладка" > "Запустить отладку"

// Советы по началу работы
//   1. В окне обозревателя решений можно добавлять файлы и управлять ими.
//   2. В окне Team Explorer можно подключиться к системе управления версиями.
//   3. В окне "Выходные данные" можно просматривать выходные данные сборки и другие сообщения.
//   4. В окне "Список ошибок" можно просматривать ошибки.
//   5. Последовательно выберите пункты меню "Проект" > "Добавить новый элемент", чтобы создать файлы кода, или "Проект" > "Добавить существующий элемент", чтобы добавить в проект существующие файлы кода.
//   6. Чтобы снова открыть этот проект позже, выберите пункты меню "Файл" > "Открыть" > "Проект" и выберите SLN-файл.