#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;
    int differenceSum = 0;
    for (auto &keyvalue : optimalTriangles) {
        auto ds = keyvalue.first;
        auto optimalTris = keyvalue.second;
        g.createFromDegreeSequence(ds);
        auto EGtris = g.countTriangles();
        if (EGtris < optimalTris) {
            int difference = optimalTris - EGtris;
            std::cout << "Erdos-Gallai triangles: " << EGtris
                      << "; Optimal triangles: " << optimalTris
                      << "; Difference: " << difference
                      << "; ds = " << ds << std::endl;
            unequal++;
            differenceSum += difference;
        }
        total++;
    }
    std::cout << "Done." << std::endl;
    std::cout << unequal << " out of " << total << " degree sequences gave non-optimal triangles.\n";
    std::cout << "Average difference of those: " << float(differenceSum) / float(unequal) << std::endl;
}