graphprogram/main.cpp

#include "graph.hpp"
#include "matrix.hpp"
#include <cstdint>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>


void benchmark_gemm() {
    const uint64_t vertex_count1 = 1024;
    std::vector<std::vector<uint64_t>> matrix1;

    const uint64_t vertex_count2 = 1024;
    std::vector<std::vector<uint64_t>> matrix2;

    std::vector<std::vector<uint64_t>> new_matrix;

    const uint64_t iterations = 10;
    double elapsed_time = 0.0;
    // clock_t start_time;

    for (uint64_t i = 0; i < iterations; i++) {
        matrix1 = random_adjacency(vertex_count1);
        matrix2 = random_adjacency(vertex_count2);

        // start_time = clock();

        new_matrix = gemm_basic(matrix1, matrix2);

        // elapsed_time += (double)(clock() - start_time) / CLOCKS_PER_SEC;
    }

    printf("%lu iterations of gemm_basic took roughly %f seconds\n", iterations, elapsed_time);
    printf("An iteration of gemm_basic took on average roughly %f seconds\n", elapsed_time/iterations);
}



void benchmark_find_components() {
    const uint64_t vertex_count = 100;
    std::vector<std::vector<uint64_t>> adjacency_matrix;
    std::vector<std::vector<uint64_t>> components;
    std::vector<std::vector<uint64_t>> path_matrix;

    const uint64_t iterations = 100;
    double elapsed_time = 0.0;
    // clock_t start_time;

    for (uint64_t i = 0; i < iterations; i++) {
        adjacency_matrix = random_adjacency(vertex_count);

        // start_time = clock();

        path_matrix = calculate_path_matrix(adjacency_matrix);
        components = find_components_basic(path_matrix);

        // elapsed_time += (double)(clock() - start_time) / CLOCKS_PER_SEC;
    }

    printf("%lu iterations of find_components_basic took roughly %f seconds\n", iterations, elapsed_time);
    printf("An iteration of find_components_basic took on average roughly %f seconds\n", elapsed_time/iterations);

    elapsed_time = 0.0;

    for (uint64_t i = 0; i < iterations; i++) {
        adjacency_matrix = random_adjacency(vertex_count);

        // start_time = clock();

        components = find_components_dfs(adjacency_matrix);

        // elapsed_time += (double)(clock() - start_time) / CLOCKS_PER_SEC;
    }

    printf("%lu iterations of find_components_dfs took roughly %f seconds\n", iterations, elapsed_time);
    printf("An iteration of find_components_dfs took on average roughly %f seconds\n", elapsed_time/iterations);
}


void test_with_basic() {
    std::vector<std::vector<uint64_t>> adjacency_matrix = read_csv("csv/24n.csv");
    std::vector<std::vector<uint64_t>> distance_matrix = calculate_distance_matrix(adjacency_matrix);
    std::vector<std::vector<uint64_t>> path_matrix = calculate_path_matrix(adjacency_matrix);
    std::vector<uint64_t> eccentricities = get_eccentricities(distance_matrix);
    uint64_t radius = get_radius(eccentricities);
    uint64_t diameter = get_diameter(eccentricities);
    std::vector<uint64_t> centre = get_centre(eccentricities);
    std::vector<std::vector<uint64_t>> components = find_components_basic(path_matrix);
    std::vector<std::vector<uint64_t>> bridges = find_bridges_basic(adjacency_matrix);
    std::vector<uint64_t> articulations = find_articulations_basic(adjacency_matrix);

    std::cout << "\nadjacency_matrix:\n";
    print_matrix(adjacency_matrix);

    std::cout << "\ndistance_matrix:\n";
    print_matrix(distance_matrix);

    std::cout << "\neccentricities: {";
    for (uint64_t index = 0; index < eccentricities.size(); index++) {
        std::cout << eccentricities[index];

        if (index < eccentricities.size() - 1) {
            std::cout << ", ";
        }
    }
    std::cout << "}";

    std::cout << "\nradius: " << radius;
    std::cout << "\ndiameter: " << diameter;
    std::cout << "\ncentre: {";
    for (uint64_t index = 0; index < centre.size(); index++) {
        std::cout << centre[index];

        if (index < centre.size() - 1) {
            std::cout << ", ";
        }
    }
    std::cout << "}";

    std::cout << "\ncomponents:";
    for (uint64_t component_index = 0; component_index < components.size(); component_index++) {
        std::cout << "\ncomponent " << component_index + 1 << ": {";

        for (uint64_t index = 0; index < components[component_index].size(); index++) {
            std::cout << components[component_index][index];

            if (index < components[component_index].size() - 1) {
                std::cout << ", ";
            }
        }
        std::cout << "}";
    }

    std::cout << "\nbridges:";
    for (uint64_t bridge_index = 0; bridge_index < bridges.size(); bridge_index++) {
        std::cout << "\nbridge " << bridge_index + 1 << ": {";

        for (uint64_t index = 0; index < bridges[bridge_index].size(); index++) {
            std::cout << bridges[bridge_index][index];

            if (index < bridges[bridge_index].size() - 1) {
                std::cout << ", ";
            }
        }
        std::cout << "}";
    }

    std::cout << "\narticulations: {";
    for (uint64_t index = 0; index < articulations.size(); index++) {
        std::cout << articulations[index];

        if (index < articulations.size() - 1) {
            std::cout << ", ";
        }
    }
    std::cout << "}\n";
}

void test_with_dfs() {
    // const uint64_t vertex_count = 100;
    // std::vector<std::vector<uint64_t>> adjacency_matrix = random_adjacency(vertex_count);
    std::vector<std::vector<uint64_t>> adjacency_matrix = read_csv("csv/24n.csv");
    std::vector<std::vector<uint64_t>> distance_matrix = calculate_distance_matrix(adjacency_matrix);
    std::vector<std::vector<uint64_t>> path_matrix = calculate_path_matrix(adjacency_matrix);
    std::vector<uint64_t> eccentricities = get_eccentricities(distance_matrix);
    uint64_t radius = get_radius(eccentricities);
    uint64_t diameter = get_diameter(eccentricities);
    std::vector<uint64_t> centre = get_centre(eccentricities);
    std::vector<std::vector<uint64_t>> components = find_components_dfs(adjacency_matrix);
    std::vector<std::vector<uint64_t>> bridges = find_bridges_dfs_v2(adjacency_matrix);
    std::vector<uint64_t> articulations = find_articulations_dfs_v2(adjacency_matrix);

    std::cout << "\nadjacency_matrix:\n";
    print_matrix(adjacency_matrix);

    std::cout << "\ndistance_matrix:\n";
    print_matrix(distance_matrix);

    std::cout << "\neccentricities: {";
    for (uint64_t index = 0; index < eccentricities.size(); index++) {
        std::cout << eccentricities[index];

        if (index < eccentricities.size() - 1) {
            std::cout << ", ";
        }
    }
    std::cout << "}";

    std::cout << "\nradius: " << radius;
    std::cout << "\ndiameter: " << diameter;
    std::cout << "\ncentre: {";
    for (uint64_t index = 0; index < centre.size(); index++) {
        std::cout << centre[index];

        if (index < centre.size() - 1) {
            std::cout << ", ";
        }
    }
    std::cout << "}";

    std::cout << "\ncomponents: ";
    for (uint64_t component_index = 0; component_index < components.size(); component_index++) {
        std::cout << "\n\tcomponent " << component_index + 1 << ": {";

        for (uint64_t index = 0; index < components[component_index].size(); index++) {
            std::cout << components[component_index][index];

            if (index < components[component_index].size() - 1) {
                std::cout << ", ";
            }
        }
        std::cout << "}";
    }

    std::cout << "\nbridges:";
    for (uint64_t bridge_index = 0; bridge_index < bridges.size(); bridge_index++) {
        std::cout << "\n\tbridge " << bridge_index + 1 << ": {";

        for (uint64_t index = 0; index < bridges[bridge_index].size(); index++) {
            std::cout << bridges[bridge_index][index];

            if (index < bridges[bridge_index].size() - 1) {
                std::cout << ", ";
            }
        }
        std::cout << "}";
    }

    std::cout << "\narticulations: {";
    for (uint64_t index = 0; index < articulations.size(); index++) {
        std::cout << articulations[index];

        if (index < articulations.size() - 1) {
            std::cout << ", ";
        }
    }
    std::cout << "}\n";
}

int main(void) {
    // test_with_basic();
    test_with_dfs();
    // benchmark_gemm();
    // benchmark_find_components();
}