test_case_generator.cpp

// Author: Sander de Beet

#include <bits/stdc++.h>  // This will work only for g++ compiler.

#define int long long

#define f0r(i, n) for (int i = 0; i < (int)(n); ++i) // 0 based indexing
#define f1r(i, n) for (int i = 1; i <= (int)(n); ++i) // 1 based indexing
#define f0rr(i, n) for (int i = (int)(n) - 1; i >= 0; --i) // reverse 0 based.
#define f1rr(i, n) for (int i = (int)(n); i >= 1; --i) // reverse 1 based

// short hand for usual tokens
#define pb push_back
#define fi first
#define se second

// to be used with algorithms that processes a container Eg: find(all(c),42)
#define all(x) (x).begin(), (x).end() //Forward traversal
#define rall(x) (x).rbegin, (x).rend() //reverse traversal

// find if a given value is present in a container. Container version. Runs in log(n) for set and map
#define present(c,x) ((c).find(x) != (c).end())

// find version works for all containers. This is present in std namespace.
#define cpresent(c,x) (find(all(c),x) != (c).end())

#define uni(x) (x).erase(unique(all(x)), (x).end())
#define debug(x) cout<<#x<<" -> "<<x<<'\n'


using namespace std;

// Shorthand for commonly used types
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef long double ld;

const ld  pi   = 4.0*atanl(1.0);
const int iinf = 1e9 + 10;
const ll  inf  = 1e18 + 10;
const int mod  = 1000000007;
const ld  prec = .00000000001;

void fast_IO() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

void file() {
    auto a = freopen("a.in",  "r", stdin);
    auto b = freopen("a.out", "w", stdout);
    if(!a || !b) cout << "uh oh" << endl;
}


void sparse() {
    int iterations = 16;

    for (int i = 0; i <= iterations; ++i) {
        std::ofstream outfile ("./sparse/sparsetest" + to_string(i) + ".txt");
        int vertices = pow(2, i);
        int edges = vertices - 1;
        outfile << vertices << " " << edges << "\n";

        int root = rand() % vertices;
        vector<int> tree = {root};
        vector<int> graph(vertices);
        iota(all(graph), 0);
        auto it = find(all(graph), root);
        graph.erase(it);

        for (int j = 0; j < edges; ++j) {
            int from_idx = rand() % tree.size();
            int to_idx = rand() % graph.size();
            int from = tree[from_idx];
            int to = graph[to_idx];
            int cost = rand() % 100;

            outfile << from << " " << to << " " << cost << "\n";
            tree.pb(to);
            graph.erase(begin(graph) + to_idx);
        }

        outfile.close();
    }
}


void dense() {
    int iterations = 20;

    for (int i = 0; i <= iterations; ++i) {
        std::ofstream outfile ("./dense/densetest" + to_string(i) + ".txt");
        int vertices = pow(2, i);
        int edges = vertices * 20;
        outfile << vertices << " " << edges << "\n";

        int root = rand() % vertices;
        vector<int> tree = {root};
        vector<int> graph(vertices);
        iota(all(graph), 0);
        auto it = find(all(graph), root);
        graph.erase(it);

        for (int j = 0; j < vertices - 1; ++j) {
            int from_idx = rand() % tree.size();
            int to_idx = rand() % graph.size();
            int from = tree[from_idx];
            int to = graph[to_idx];
            int cost = rand() % 100;
            outfile << from << " " << to << " " << cost << "\n";
            tree.pb(to);
            graph.erase(begin(graph) + to_idx);
        }

        if (vertices != 1) {
            for (int j = 0; j < edges - (vertices + 1); ++j) {
                while (1) {
                    int from_idx = rand() % vertices;
                    int to_idx = rand() % vertices;
                    if (from_idx == to_idx) continue;
                    int cost = rand() % 100;
                    outfile << from_idx << " " << to_idx << " " << cost << "\n";
                    break;
                }
            }
        }

        outfile.close();
    }
}


void sparse_to_dense() {
    int iterations = 16;

    for (int i = 1; i <= iterations; ++i) {
        std::ofstream outfile ("./sparse_to_dense/densetest" + to_string(i) + ".txt");
        int vertices = pow(2, 16);
        int edges = vertices * i;
        outfile << vertices << " " << edges << "\n";

        int root = rand() % vertices;
        vector<int> tree = {root};
        vector<int> graph(vertices);
        iota(all(graph), 0);
        auto it = find(all(graph), root);
        graph.erase(it);

        for (int j = 0; j < vertices - 1; ++j) {
            int from_idx = rand() % tree.size();
            int to_idx = rand() % graph.size();
            int from = tree[from_idx];
            int to = graph[to_idx];
            int cost = rand() % 100;
            outfile << from << " " << to << " " << cost << "\n";
            tree.pb(to);
            graph.erase(begin(graph) + to_idx);
        }

        if (vertices != 1) {
            for (int j = 0; j < edges - (vertices + 1); ++j) {
                while (1) {
                    int from_idx = rand() % vertices;
                    int to_idx = rand() % vertices;
                    if (from_idx == to_idx) continue;
                    int cost = rand() % 100;
                    outfile << from_idx << " " << to_idx << " " << cost << "\n";
                    break;
                }

            }
        }

        outfile.close();
    }
}


signed main() {
    fast_IO();
    // file();
    cout.precision(10);
    cout << fixed;

    /* Choose what scenario of test cases you want to generate. */
    // sparse();
    // dense();
    sparse_to_dense();

    return 0;
}