main.cpp

#include "binaryheap.h"
#include "fibonacciheap.h"
#include <stdio.h>
#include <time.h>
#include <dirent.h>
#include <unistd.h>
#include <string.h>
#include <errno.h>
#include <err.h>

#pragma warning(disable:6031)
Graph* read_file(const char* filename) {
    FILE* file = fopen(filename, "r");
    if (!file) {
        printf("Error: Unable to open file %s\n", filename);
        return NULL;
    }

    char line[256];
    int num_nodes = 0, num_edges = 0;
    int found_header = 0;

    // Scan the file to get the number of nodes and edges
    while (fgets(line, sizeof(line), file)) {
        if (line[0] == 'p') {
            // Parse problem line: p sp <num_nodes> <num_edges>
            if (sscanf(line, "p sp %d %d", &num_nodes, &num_edges) == 2) {
                found_header = 1;
                break;
            }
        }
    }

    if (!found_header) {
        printf("Error: Valid file header (p sp ...) not found\n");
        fclose(file);
        return NULL;
    }

    if (num_nodes <= 0 || num_edges <= 0) {
        printf("Error: Invalid number of nodes or edges\n");
        fclose(file);
        return NULL;
    }

    printf("Graph info: %d nodes, %d edges\n", num_nodes, num_edges);

    // Create graph
    Graph* graph = create_graph(num_nodes);

    // Rewind file to read edge data again
    rewind(file);

    int edges_read = 0;

    // Read edge data
    while (fgets(line, sizeof(line), file)) {
        if (line[0] == 'a') {
            // Parse edge line: a <from> <to> <weight>
            int u, v, w;
            if (sscanf(line, "a %d %d %d", &u, &v, &w) == 3) {
                // DIMACS format node indices start from 1, convert to 0-based
                add_edge(graph, u - 1, v - 1, w);
                edges_read++;
            }
        }
    }

    fclose(file);
    return graph;
}
void get_files_in_directory(const char* folder_path, char files[][256], int* num_files) {
    DIR* dir = opendir(folder_path);
    if (dir == NULL) {
        printf("Error: Could not open directory %s\n", folder_path);
        return;
    }

    struct dirent* entry;
    *num_files = 0;
    while ((entry = readdir(dir)) != NULL) {
        if (strstr(entry->d_name, ".gr")) {
            strcpy(files[*num_files], entry->d_name);
            (*num_files)++;
        }
    }

    closedir(dir);
}

void generate_random_pairs(int num_nodes, int num_pairs, int pairs[][2]) {
    for (int i = 0; i < num_pairs; i++) {
        pairs[i][0] = rand() % num_nodes;
        pairs[i][1] = rand() % num_nodes;
        while (pairs[i][0] == pairs[i][1]) {  // 确保不同节点对
            pairs[i][1] = rand() % num_nodes;
        }
    }
}

// 执行测试并比较两种算法
void test(const char* folder_path, const char* filename, int* fib_heap_score, int* bin_heap_score, FILE* report_file) {
    // 拼接完整路径
    double totaltime_binary=0,totaltime_fibonacci=0;
    char full_path[512];
    snprintf(full_path, sizeof(full_path), "%s/%s", folder_path, filename);
    printf("Trying to open file: %s\n", full_path);  // 打印完整路径以便调试

    FILE* file = fopen(full_path, "r");
    if (!file) {
        perror("shabi");
    }

    // 读取文件内容并执行测试
    Graph* graph = read_file(full_path);
    if (!graph) {
        printf("Failed to read file\n");
        fclose(file);
        return;
    }

    int num_pairs = 100;
    int pairs[num_pairs][2];
    generate_random_pairs(graph->num_nodes, num_pairs, pairs);
    fprintf(report_file, "Filename: %s\n",filename);
    for (int i = 0; i < num_pairs; i++) {
        int src = pairs[i][0];
        int dest = pairs[i][1];

        clock_t start1 = clock();
        int path1[MAX_NODES];
        int path_length1;
        int distance1 = shortest_path_length_fibonacci(graph, src, dest, path1, &path_length1);
        clock_t end1 = clock();
        double time1 = ((double)(end1 - start1)) / CLOCKS_PER_SEC * 1000;

        clock_t start2 = clock();
        int path2[MAX_NODES];
        int path_length2;
        int distance2 = shortest_path_length(graph, src, dest, path2, &path_length2);
        clock_t end2 = clock();
        double time2 = ((double)(end2 - start2)) / CLOCKS_PER_SEC * 1000;

        // 写入报告文件
        fprintf(report_file, "Pair: %d -> %d | Fibonacci Heap Time: %.3f ms | Binary Heap Time: %.3f ms\n", src, dest, time1, time2);
        totaltime_fibonacci += time1;
        totaltime_binary += time2;
    }
    printf("Filename: %s\nTotal time of Fibonacci Heap: %.3f ms Average time of Fibonacci Heap: %.5f ms\n" ,filename, totaltime_fibonacci, totaltime_fibonacci/100);
    printf("Total time of Fibonacci Heap: %.3f ms Average time of Fibonacci Heap: %.5f ms\n" ,totaltime_binary, totaltime_binary/100);
    free_graph(graph);
    fclose(file);  // 关闭文件
}

int main() {
    printf("=== Fibonacci and Binary Heap Dijkstra's Algorithm Comparison ===\n");
    char folder_path[256];
    printf("Please enter the folder path containing .gr files: ");
    scanf("%255s", folder_path);

    char files[100][256];
    int num_files = 0;
    get_files_in_directory(folder_path, files, &num_files);
    if (num_files == 0) {
        printf("No .gr files found in the directory.\n");
        return 0;
    }

    printf("Found %d .gr files. Starting tests...\n", num_files);

    int fib_heap_score = 0;
    int bin_heap_score = 0;

    // 打开报告文件
    FILE* report_file = fopen("dijkstra_comparison_report.txt", "w");
    if (!report_file) {
        printf("Error: Could not open report file.\n");
        return 0;
    }

    // 对每个文件进行测试
    for (int i = 0; i < num_files; i++) {
        printf("Testing file: %s\n", files[i]);
        test(folder_path, files[i], &fib_heap_score, &bin_heap_score, report_file);
    }

    fclose(report_file);

    // 输出最终结果
    printf("\n=== Final Scores ===\n");
    printf("Fibonacci Heap Score: %d\n", fib_heap_score);
    printf("Binary Heap Score: %d\n", bin_heap_score);

    return 0;
}