TARGETS += bruteforce_triangles

#include "exports.hpp"

#include "graph.hpp"

#include <iostream>

#include <map>

int main() {

    // Bruteforce over all graphs of n nodes

    constexpr int n = 8;

    constexpr int E = n * (n - 1) / 2;

    std::map<DegreeSequence, unsigned int> optimalTriangles;

    std::cout << "Iterating over all graphs with " << n << " vertices." << std::endl;

    Graph g;

    for (int edgeMask = 0; edgeMask < (1 << E); ++edgeMask) {

        g.reset(n);

        int mask = edgeMask;

        for (auto i = 0u; i < n; ++i) {

            for (auto j = i + 1; j < n; ++j) {

                if (mask & 1) {

                    g.addEdge({i, j});

                }

                mask >>= 1;

            }

        }

        auto triangles = g.countTriangles();

        auto ds = g.getDegreeSequence();

        std::sort(ds.begin(), ds.end());

        auto iter = optimalTriangles.find(ds);

        if (iter != optimalTriangles.end()) {

            if (iter->second < triangles)

                iter->second = triangles;

        } else {

            optimalTriangles[ds] = triangles;

        }

    }

    std::cout << "Comparing with Erdos-Gallai triangles." << std::endl;

    int total = 0;

    int unequal = 0;

    for (auto &keyvalue : optimalTriangles) {

        auto ds = keyvalue.first;

        auto optimalTris = keyvalue.second;

        g.createFromDegreeSequence(ds);

        auto EGtris = g.countTriangles();

        if (EGtris < optimalTris) {

            std::cout << "Erdos-Gallai triangles: " << EGtris

                      << "; Optimal triangles: " << optimalTris

                      << "; Difference: " << (optimalTris - EGtris)

                      << "; ds = " << ds << std::endl;

            unequal++;

        }

        total++;

    }

    std::cout << "Done." << std::endl;

    std::cout << unequal << " out of " << total << " degree sequences gave non-optimal triangles.\n";

}

            // Construction will find maximum triangles only if sort is stable

            // and does NOT sort on vertex id

            std::stable_sort(degrees.begin(), degrees.end(),

                             [](const auto &p1, const auto &p2) {

                                 return p1.first < p2.first;

                             });