Enumerate Triangles
(lib/graph/enumerate_triangles.hpp)

• View this file on GitHub
• Last update: 2024-10-31 23:51:11+09:00
• Include: #include "lib/graph/enumerate_triangles.hpp"
• Link: https://www.slideshare.net/slideshow/trianguler/38443802

Verified with

• test/library_checker/graph/enumerate_triangles.test.cpp

Code

#pragma once

/**
 * @brief Enumerate Triangles
 * @see https://www.slideshare.net/slideshow/trianguler/38443802
 */

vector<array<int, 3>> enumerateTriangles(vector<vector<int>> &G){
    int n = G.size();
    vector<vector<int>> DAG(n);
    for(int i = 0; i < n; i++){
        for(auto &j : G[i]){
            pair<int, int> p = {(int) G[i].size(), i}, q = {(int) G[j].size(), j};
            if(p < q){
                DAG[i].push_back(j);
            }
        }
    }

    vector<array<int, 3>> res;
    vector<int> edge(n);
    for(int i = 0; i < n; i++){
        for(auto j : DAG[i]){
            for(auto k : DAG[i]){
                edge[k]++;
            }
            for(auto k : DAG[j]){
                if(edge[k]){
                    res.push_back({i, j, k});
                }
            }
            for(auto k : DAG[i]){
                edge[k]--;
            }
        }
    }
    return res;
}

#line 2 "lib/graph/enumerate_triangles.hpp"

/**
 * @brief Enumerate Triangles
 * @see https://www.slideshare.net/slideshow/trianguler/38443802
 */

vector<array<int, 3>> enumerateTriangles(vector<vector<int>> &G){
    int n = G.size();
    vector<vector<int>> DAG(n);
    for(int i = 0; i < n; i++){
        for(auto &j : G[i]){
            pair<int, int> p = {(int) G[i].size(), i}, q = {(int) G[j].size(), j};
            if(p < q){
                DAG[i].push_back(j);
            }
        }
    }

    vector<array<int, 3>> res;
    vector<int> edge(n);
    for(int i = 0; i < n; i++){
        for(auto j : DAG[i]){
            for(auto k : DAG[i]){
                edge[k]++;
            }
            for(auto k : DAG[j]){
                if(edge[k]){
                    res.push_back({i, j, k});
                }
            }
            for(auto k : DAG[i]){
                edge[k]--;
            }
        }
    }
    return res;
}

Back to top page