c++ - 使用openmp实现同构图并行代码

Question

我正在尝试使用openmp实现图同构的并行代码（检查2个图是否同构）。我有下面的顺序代码，用 C++ 编写，仅适用于常规图形。我从一个文本文件 (input.txt) 中获取输入，该文件包含节点数和代表 2 个图的 2 个邻接矩阵。output.txt 文件指示图是同构的还是非同构的以及执行时间。我使用 is_regular() 函数来检查一个图是否是正则图。

有人可以帮我使用openmp并行化这段代码吗？

#include <time.h>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <string>
using namespace std;

bool is_regular(vector<string> &adj) {
    int nv = adj.size();
    int cnt = 0;
    for (int j = 0; j < nv; ++j)
        if (adj[0][j] == '1') ++cnt;
    for (int i = 1; i < nv; ++i) {
        int sch = 0;
        for (int j = 0; j < nv; ++j)
            if (adj[i][j] == '1') ++sch;
        if (sch != cnt) return false;
    }
    return true;
}

vector<vector<int> > foo1(vector<string> &adj, char R) {
    int nv = adj.size();
    vector<vector<int> > res;

    for (int v1 = 0; v1 < nv; ++v1) {
        vector<int> tmp;
        vector<bool> b(nv);
        vector<int> p, q;
        p.push_back(v1);
        b[v1] = true;
        while (!p.empty()) {
            q.clear();

            for (size_t i = 0; i < p.size(); ++i) {
                for (int j = 0; j < nv; ++j)
                {
                    if (!b[j] && adj[p[i]][j] == R) {
                        b[j] = true;
                        q.push_back(j);
                    }
                }
            }
            if (q.empty()) break;
            vector<int> d(p.size());
            vector<int> e(q.size());

            for (size_t i = 0; i < p.size(); ++i) {
                for (size_t j = 0; j < q.size(); ++j) {
                    if (adj[p[i]][q[j]] == R) {++d[i]; --e[j];}
                }
            }
            sort(d.begin(), d.end());
            sort(e.begin(), e.end());
            copy(d.begin(), d.end(), back_inserter(tmp));
            copy(e.begin(), e.end(), back_inserter(tmp));
            p.swap(q);
        }
        res.push_back(tmp);
    }
    sort(res.begin(), res.end());
    return res;
}

vector<vector<int> > foo2(vector<string> &adj, char R) {
    int nv = adj.size();
    vector<vector<int> > res;
    for (int v1 = 0; v1 < nv; ++v1) {
    for (int v2 = v1 + 1; v2 < nv; ++v2) {
        vector<int> tmp;
        vector<bool> b(nv);
        vector<int> p, q;
        p.push_back(v1);
        p.push_back(v2);
        b[v1] = true;
        b[v2] = true;
        while (!p.empty()) {
            q.clear();
            for (size_t i = 0; i < p.size(); ++i) {
                for (int j = 0; j < nv; ++j) {
                    if (!b[j] && adj[p[i]][j] == R) {
                        b[j] = true;
                        q.push_back(j);
                    }
                }
            }
            if (q.empty()) break;
            vector<int> d(p.size());
            vector<int> e(q.size());
            for (size_t i = 0; i < p.size(); ++i) {
                for (size_t j = 0; j < q.size(); ++j) {
                    if (adj[p[i]][q[j]] == R) {++d[i]; --e[j];}
                }
            }
            sort(d.begin(), d.end());
            sort(e.begin(), e.end());
            copy(d.begin(), d.end(), back_inserter(tmp));
            copy(e.begin(), e.end(), back_inserter(tmp));
            p.swap(q);
        }
        res.push_back(tmp);
    }
    }
    sort(res.begin(), res.end());
    return res;
}

vector<vector<int> > foo3(vector<string> &adj, char R) {
    int nv = adj.size();
    vector<vector<int> > res;
    for (int v1 = 0; v1 < nv; ++v1) {
    for (int v2 = v1 + 1; v2 < nv; ++v2) {
    for (int v3 = v2 + 1; v3 < nv; ++v3) {
        vector<int> tmp;
        vector<bool> b(nv);
        vector<int> p, q;
        p.push_back(v1);
        p.push_back(v2);
        p.push_back(v3);
        b[v1] = true;
        b[v2] = true;
        b[v3] = true;
        while (!p.empty()) {
            q.clear();
            for (size_t i = 0; i < p.size(); ++i) {
                for (int j = 0; j < nv; ++j) {
                    if (!b[j] && adj[p[i]][j] == R) {
                        b[j] = true;
                        q.push_back(j);
                    }
                }
            }
            if (q.empty()) break;
            vector<int> d(p.size());
            vector<int> e(q.size());
            for (size_t i = 0; i < p.size(); ++i) {
                for (size_t j = 0; j < q.size(); ++j) {
                    if (adj[p[i]][q[j]] == R) {++d[i]; --e[j];}
                }
            }
            sort(d.begin(), d.end());
            sort(e.begin(), e.end());
            copy(d.begin(), d.end(), back_inserter(tmp));
            copy(e.begin(), e.end(), back_inserter(tmp));
            p.swap(q);
        }
        res.push_back(tmp);
    }
    }
    }
    sort(res.begin(), res.end());
    return res;
}

int main() {
    int nt = 1;
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int n;
    int tc = 0;

    while (cin >> n) {
        vector<string> adj1(n);
        vector<string> adj2(n);
        for (int i = 0; i < n; ++i) cin >> adj1[i];
        for (int i = 0; i < n; ++i) cin >> adj2[i];
        clock_t start = clock();
        string answer = "NON-isomorphic";
        if (!is_regular(adj1) || !is_regular(adj2)) {
            answer = "Non regular graph";
            goto mmm;
        }
        if (foo1(adj1,'1') != foo1(adj2,'1') || foo1(adj1,'0') != foo1(adj2,'0')) {
            answer += "  *  ";
            goto mmm;
        }
        if (foo2(adj1,'1') != foo2(adj2,'1') || foo2(adj1,'0') != foo2(adj2,'0')) {
            answer += "  ** ";
            goto mmm;
        }
        if (foo3(adj1,'1') != foo3(adj2,'1') || foo3(adj1,'0') != foo3(adj2,'0')) {
            answer += "  ***";
            goto mmm;
        }
        answer = "isomorphic";
        mmm:
        ++tc;
        printf("%d) n = %d  %s", tc, n, answer.c_str());
        printf(" %f\n", (double)(clock() - start) / CLOCKS_PER_SEC);
    }
return 0;
}