/**
 * @file travels.c
 * @brief 网络算法模块实现 — 所有核心算法
 *
 * 包含功能：
 *   1. locate     — 设备定位
 *   2. DFS        — 深度优先遍历（全网巡检）
 *   3. isEdge     — 链路检测
 *   4. loopTest   — 路由环路检测（Kahn拓扑排序）
 *   5. shortPath  — Floyd全源最短路径（全网路由表计算）
 *   6. printShortPath  — 递归输出最短路径
 *   7. minDistance     — 两设备最优路径查询（交互）
 *   8. floydAllDistance — 全网路由表展示
 *   9. dijkstraQuery   — Dijkstra单源最短路径（OSPF核心）
 *  10. primMST         — Prim最小生成树（光纤布线）
 *  11. kruskalMST      — Kruskal最小生成树（光纤布线）
 *  12. showDeviceInfo  — 设备详情查询
 *
 * 第1轮实现：locate（graph.c编译依赖此函数）
 */

#define _CRT_SECURE_NO_WARNINGS 1
#include "travels.h"

/* ==================== 外部全局变量 ==================== */
extern int visited[];            /* 访问标记数组，定义在graph.c中 */
extern int **parray;             /* 邻接矩阵（权值矩阵），定义在graph.c中 */

/* ==================== 模块内部全局变量 ==================== */
char path[MAX_DEVICE][20];       /* DFS遍历序列 */
int pathIdx = 0;                 /* DFS路径写入索引 */
CNode *p;                        /* DFS遍历邻接表用的边节点指针 */

/* ==================== 1. locate ==================== */

int locate(ALGraph graph, char *name)
{
    int i;
    for (i = 0; i < graph.deviceNum; i++)
    {
        if (strcmp(name, graph.devices[i].name) == 0)
        {
            return i;
        }
    }
    return -1;  /* 未找到返回 -1 */
}

/* ==================== 2. DFSTraverse / DFS ==================== */

void DFSTraverse(ALGraph graph)
{
    int i;
    pathIdx = 0;
    for (i = 0; i < graph.deviceNum; i++)
        visited[i] = 0;
    for (i = 0; i < graph.deviceNum; i++)
        if (!visited[i])
            DFS(graph, i);
}

void DFS(ALGraph graph, int i)
{
    visited[i] = 1;
    strcpy(path[pathIdx++], graph.devices[i].name);
    for (p = graph.devices[i].first; p != NULL; p = p->next)
    {
        if (!visited[p->index])
        {
            DFS(graph, p->index);
            p = graph.devices[i].first;
        }
    }
}

/* ==================== 3. isEdge ==================== */

int isEdge(ALGraph graph, char *e1, char *e2)
{
    int i = locate(graph, e1);
    int j = locate(graph, e2);
    if (i == -1 || j == -1)
        return 0;
    if (parray != NULL && parray[i][j] < INF)
        return 1;
    return 0;
}

/* ==================== 4. loopTest (Kahn) ==================== */

int loopTest(ALGraph graph)
{
    typedef char str[20];
    str *pnodes = (str *)malloc(sizeof(str) * graph.deviceNum);
    int *indegree = (int *)malloc(sizeof(int) * graph.deviceNum);
    int *queue = (int *)malloc(sizeof(int) * graph.deviceNum);
    int count = 0;
    CNode *pNode;
    int i, j, front = 0, rear = 0;

    /* 初始化入度 */
    for (i = 0; i < graph.deviceNum; i++)
        indegree[i] = 0;

    /* 统计入度 */
    for (i = 0; i < graph.deviceNum; i++)
    {
        for (pNode = graph.devices[i].first; pNode != NULL; pNode = pNode->next)
        {
            indegree[pNode->index]++;
        }
    }

    /* 入度为0的顶点入队 */
    for (i = 0; i < graph.deviceNum; i++)
    {
        if (!indegree[i])
            queue[rear++] = i;
    }

    /* Kahn拓扑排序主循环 */
    while (front != rear)
    {
        j = queue[front++];
        strcpy(pnodes[count++], graph.devices[j].name);
        for (pNode = graph.devices[j].first; pNode != NULL; pNode = pNode->next)
        {
            if (!(--indegree[pNode->index]))
            {
                queue[rear++] = pNode->index;
            }
        }
    }

    free(indegree);
    free(queue);

    /* 判断是否存在回路 */
    if (count < graph.deviceNum)
    {
        printf("\n========== 环路检测结果 ==========\n");
        printf("❌ 图中存在路由环路！\n");
        printf("未排入拓扑序列的设备（形成环路的设备）：\n");
        for (i = 0; i < graph.deviceNum; i++)
        {
            for (j = 0; j < count; j++)
                if (strcmp(graph.devices[i].name, pnodes[j]) == 0)
                    break;
            if (j >= count)
                printf("  - %s\n", graph.devices[i].name);
        }
        printf("提示：环路会导致广播风暴，需重新规划巡检路线！\n");
        printf("==================================\n\n");
        free(pnodes);
        return 0;  /* 有回路 */
    }
    else
    {
        printf("\n========== 环路检测结果 ==========\n");
        printf("✅ 图中没有回路，巡检路线合法！\n");
        printf("拓扑排序序列：\n");
        for (i = 0; i < count; i++)
        {
            printf("  %s", pnodes[i]);
            if (i < count - 1) printf(" →");
        }
        printf("\n==================================\n\n");
        free(pnodes);
        return 1;  /* 无回路 */
    }
}

/* ==================== 5. shortPath (Floyd) ==================== */

void shortPath(ALGraph graph, int path[][MAX_DEVICE], int shortpath[][MAX_DEVICE])
{
    int i, j, k;

    /* 初始化距离矩阵和路径矩阵 */
    for (i = 0; i < graph.deviceNum; i++)
    {
        for (j = 0; j < graph.deviceNum; j++)
        {
            shortpath[i][j] = parray[i][j];
            if (i == j)
                path[i][j] = i;
            else if (parray[i][j] < INF)
                path[i][j] = i;   /* 有直连链路 */
            else
                path[i][j] = -1;  /* 不可达 */
        }
    }

    /* Floyd 三重循环（k在最外层） */
    for (k = 0; k < graph.deviceNum; k++)
    {
        for (i = 0; i < graph.deviceNum; i++)
        {
            for (j = 0; j < graph.deviceNum; j++)
            {
                if (shortpath[i][k] < INF && shortpath[k][j] < INF &&
                    shortpath[i][k] + shortpath[k][j] < shortpath[i][j])
                {
                    shortpath[i][j] = shortpath[i][k] + shortpath[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}

/* ==================== 6. printShortPath ==================== */

void printShortPath(ALGraph graph, int path[][MAX_DEVICE],
                    int shortpath[][MAX_DEVICE], int i, int j)
{
    if (path[i][j] == -1)
    {
        printf("(不可达)\n");
        return;
    }
    if (path[i][j] == i)
    {
        printf("  %s ── %s\n", graph.devices[i].name, graph.devices[j].name);
    }
    else
    {
        int k = path[i][j];
        printShortPath(graph, path, shortpath, i, k);
        printShortPath(graph, path, shortpath, k, j);
    }
}

/* ==================== 7. minDistance (Floyd查询) ==================== */

void minDistance(ALGraph graph, int path[][MAX_DEVICE], int shortpath[][MAX_DEVICE])
{
    char start[20], end[20];
    int i, j;

    if (parray == NULL)
    {
        printf("✘ 请先选择选项2查看邻接矩阵后再查询最短路径！\n");
        return;
    }

    shortPath(graph, path, shortpath);

    printf("请输入起点设备代号：");
    scanf("%s", start);
    printf("请输入终点设备代号：");
    scanf("%s", end);

    i = locate(graph, start);
    j = locate(graph, end);

    if (i == -1 || j == -1)
    {
        printf("✘ 设备不存在！请检查输入。\n");
        return;
    }
    if (i == j)
    {
        printf("起点和终点相同，延迟为0。\n");
        return;
    }
    if (shortpath[i][j] >= INF)
    {
        printf("从 %s 到 %s 不可达（无连通路径）！\n", start, end);
        return;
    }

    printf("\n========== 最优路径计算结果 ==========\n");
    printf("起点：%s\n", start);
    printf("终点：%s\n", end);
    printf("最优路径：\n");
    printShortPath(graph, path, shortpath, i, j);

    /* 如果 AR-D→SV，展示"绕路更快"的亮点 */
    if (strcmp(start, "AR-D") == 0 && strcmp(end, "SV") == 0)
    {
        printf("\n⭐ 有趣的现象：\n");
        printf("   直连路径：AR-D ── SV = 25ms\n");
        printf("   最优路径：AR-D → DR-B → CR → DR-A → AR-T → SV = %dms\n", shortpath[i][j]);
        printf("   \"绕路\"反而比直连快%dms！这是因为宿舍直连服务器线路质量较差。\n", 25 - shortpath[i][j]);
    }

    printf("最短延迟：%dms\n", shortpath[i][j]);

    /* 如果 AR-D→SV，展示"绕路更快"的亮点 — 动态从邻接矩阵读取直连值 */
    if (strcmp(start, "AR-D") == 0 && strcmp(end, "SV") == 0)
    {
        int directly = (parray[i][j] < INF) ? parray[i][j] : 25;
        printf("\n⭐ 有趣的现象：\n");
        printf("   直连路径：AR-D ── SV = %dms\n", directly);
        printf("   最优路径：总延迟 = %dms\n", shortpath[i][j]);
        printf("   \"绕路\"反而比直连快%dms！这是因为宿舍直连服务器线路质量较差。\n",
               directly - shortpath[i][j]);
    }

    printf("=====================================\n\n");
}

/* ==================== 8. floydAllDistance ==================== */

void floydAllDistance(ALGraph graph, int path[][MAX_DEVICE], int shortpath[][MAX_DEVICE])
{
    int i, j;

    if (parray == NULL)
    {
        printf("✘ 请先选择选项2查看邻接矩阵后再查看全网路由表！\n");
        return;
    }

    shortPath(graph, path, shortpath);

    printf("\n========== 全网路由表（Floyd全源最短距离，单位：ms）==========\n");
    printf("\t");
    for (j = 0; j < graph.deviceNum; j++)
    {
        printf("%s\t", graph.devices[j].name);
    }
    printf("\n");

    for (i = 0; i < graph.deviceNum; i++)
    {
        printf("%s\t", graph.devices[i].name);
        for (j = 0; j < graph.deviceNum; j++)
        {
            if (shortpath[i][j] >= INF)
                printf("INF\t");
            else
                printf("%d\t", shortpath[i][j]);
        }
        printf("\n");
    }
    printf("===============================================================\n\n");
}

/* ==================== 9. dijkstraQuery ==================== */

void dijkstraQuery(ALGraph graph)
{
    char start[20], end[20];
    int s, t, i, j, u, min;
    int dist[MAX_DEVICE];
    int visit[MAX_DEVICE];
    int prev[MAX_DEVICE];
    char stack[MAX_DEVICE][20];
    int top;

    if (parray == NULL)
    {
        printf("✘ 请先选择选项2查看邻接矩阵后再查询！\n");
        return;
    }

    printf("请输入起点设备代号：");
    scanf("%s", start);
    printf("请输入终点设备代号：");
    scanf("%s", end);

    s = locate(graph, start);
    t = locate(graph, end);
    if (s == -1 || t == -1)
    {
        printf("✘ 设备不存在！\n");
        return;
    }

    /* 初始化 */
    for (i = 0; i < graph.deviceNum; i++)
    {
        dist[i] = parray[s][i];
        visit[i] = 0;
        prev[i] = (parray[s][i] < INF) ? s : -1;
    }
    visit[s] = 1;
    dist[s] = 0;

    /* 主循环：每次选距离最小的未确认顶点 */
    for (i = 1; i < graph.deviceNum; i++)
    {
        min = INF;
        u = -1;
        for (j = 0; j < graph.deviceNum; j++)
        {
            if (!visit[j] && dist[j] < min)
            {
                min = dist[j];
                u = j;
            }
        }
        if (u == -1) break;    /* 剩余顶点不可达 */
        visit[u] = 1;           /* 盖章确认 */
        for (j = 0; j < graph.deviceNum; j++)
        {
            if (!visit[j] && parray[u][j] < INF &&
                dist[u] + parray[u][j] < dist[j])
            {
                dist[j] = dist[u] + parray[u][j];
                prev[j] = u;
            }
        }
    }

    if (dist[t] >= INF)
    {
        printf("从 %s 到 %s 不可达！\n", start, end);
        return;
    }

    /* 回溯路径并输出 */
    printf("\n========== Dijkstra最短路径（OSPF算法）==========\n");
    printf("从 %s 到 %s 的最短延迟：%dms\n", start, end, dist[t]);
    printf("最短路径为：");
    top = 0;
    for (j = t; j != -1; j = prev[j])
    {
        strcpy(stack[top++], graph.devices[j].name);
        if (j == s) break;
    }
    for (j = top - 1; j >= 0; j--)
    {
        printf("%s", stack[j]);
        if (j > 0) printf(" → ");
    }
    printf("\n================================================\n\n");
}

/* ==================== 10. primMST ==================== */

void primMST(ALGraph graph)
{
    int lowcost[MAX_DEVICE];
    int closest[MAX_DEVICE];
    int i, j, k, min, total = 0;
    int n = graph.deviceNum;
    int count = 0;

    if (parray == NULL)
    {
        printf("✘ 请先选择选项2查看邻接矩阵后再计算！\n");
        return;
    }

    /* 初始化：以顶点0(CR)为起点 */
    for (i = 0; i < n; i++)
    {
        lowcost[i] = parray[0][i];
        closest[i] = 0;
    }
    lowcost[0] = 0;    /* 标记CR已加入MST */

    printf("\n========== 光纤骨干网布线方案（Prim算法）==========\n");
    printf("从 %s 出发，按顶点扩张：\n\n", graph.devices[0].name);

    for (i = 1; i < n; i++)
    {
        min = INF;
        k = -1;
        for (j = 0; j < n; j++)
        {
            if (lowcost[j] != 0 && lowcost[j] < min)
            {
                min = lowcost[j];
                k = j;
            }
        }
        if (k == -1) break;   /* 图不连通 */

        printf("  选中  %s ── %s  (延迟:%dms)\n",
               graph.devices[closest[k]].name,
               graph.devices[k].name, lowcost[k]);
        total += lowcost[k];
        count++;
        lowcost[k] = 0;       /* k加入MST */

        for (j = 0; j < n; j++)
        {
            if (lowcost[j] != 0 && parray[k][j] < lowcost[j])
            {
                lowcost[j] = parray[k][j];
                closest[j] = k;
            }
        }
    }

    printf("\nMST总延迟：%dms\n", total);
    if (count < n - 1)
        printf("(图不连通，布线无法覆盖所有设备)\n");
    printf("==================================================\n\n");
}

/* ==================== 11. kruskalMST ==================== */

/* 并查集查找（路径减半） */
static int kruskalFind(int parent[], int x)
{
    while (parent[x] != x)
    {
        parent[x] = parent[parent[x]];   /* 路径减半 */
        x = parent[x];
    }
    return x;
}

void kruskalMST(ALGraph graph)
{
    Edge edges[MAX_DEVICE * MAX_DEVICE];
    int parent[MAX_DEVICE];
    int i, j, n = graph.deviceNum;
    int edgeCount = 0, total = 0, mstEdges = 0;
    CNode *q;

    if (parray == NULL)
    {
        printf("✘ 请先选择选项2查看邻接矩阵后再计算！\n");
        return;
    }

    /* 收集所有边（i < q->index 避免重复） */
    for (i = 0; i < n; i++)
    {
        for (q = graph.devices[i].first; q != NULL; q = q->next)
        {
            if (i < q->index)
            {
                edges[edgeCount].u = i;
                edges[edgeCount].v = q->index;
                edges[edgeCount].w = q->delay;
                edgeCount++;
            }
        }
    }

    /* 冒泡排序：按权值从小到大 */
    for (i = 0; i < edgeCount - 1; i++)
    {
        for (j = 0; j < edgeCount - 1 - i; j++)
        {
            if (edges[j].w > edges[j + 1].w)
            {
                Edge tmp = edges[j];
                edges[j] = edges[j + 1];
                edges[j + 1] = tmp;
            }
        }
    }

    /* 初始化并查集 */
    for (i = 0; i < n; i++)
        parent[i] = i;

    printf("\n========== 光纤骨干网布线方案（Kruskal算法）==========\n");
    printf("按延迟从小到大排序，并查集判环：\n\n");

    for (i = 0; i < edgeCount && mstEdges < n - 1; i++)
    {
        int ru = kruskalFind(parent, edges[i].u);
        int rv = kruskalFind(parent, edges[i].v);
        if (ru != rv)
        {
            printf("  ✅ 选中  %s ── %s  (延迟:%dms)\n",
                   graph.devices[edges[i].u].name,
                   graph.devices[edges[i].v].name, edges[i].w);
            total += edges[i].w;
            parent[ru] = rv;
            mstEdges++;
        }
        else
        {
            printf("  ❌ 跳过  %s ── %s  (延迟:%dms)   ← 避免环路\n",
                   graph.devices[edges[i].u].name,
                   graph.devices[edges[i].v].name, edges[i].w);
        }
    }

    printf("\nMST总延迟：%dms\n", total);
    if (mstEdges < n - 1)
        printf("(图不连通，布线无法覆盖所有设备)\n");
    printf("======================================================\n\n");
}

/* ==================== 12. showDeviceInfo ==================== */

void showDeviceInfo(ALGraph graph)
{
    char name[20];
    int i, idx;

    printf("请输入要查询的设备代号：");
    scanf("%s", name);

    idx = -1;
    for (i = 0; i < graph.deviceNum; i++)
    {
        if (strcmp(graph.devices[i].name, name) == 0)
        {
            idx = i;
            break;
        }
    }

    if (idx == -1)
    {
        printf("✘ 未找到设备：%s\n", name);
        return;
    }

    /* 判断设备层级 */
    const char *level;
    if (strcmp(graph.devices[idx].name, "CR") == 0)
        level = "核心层";
    else if (strcmp(graph.devices[idx].name, "FW") == 0)
        level = "安全层";
    else if (graph.devices[idx].name[0] == 'D' && graph.devices[idx].name[1] == 'R')
        level = "汇聚层";
    else if (graph.devices[idx].name[0] == 'A' && graph.devices[idx].name[1] == 'R')
        level = "接入层";
    else if (strcmp(graph.devices[idx].name, "SV") == 0)
        level = "数据中心";
    else
        level = "其他";

    printf("\n========== 设备详情 ==========\n");
    printf("  设备名称：%s\n", graph.devices[idx].name);
    printf("  设备描述：%s\n", graph.devices[idx].desc);
    printf("  所属层级：%s\n", level);
    printf("  端口数量：%d\n", graph.devices[idx].portCount);
    printf("  运行时间：%s\n", graph.devices[idx].note);
    printf("  相邻设备：");
    {
        CNode *q = graph.devices[idx].first;
        if (q == NULL)
        {
            printf("无");
        }
        else
        {
            while (q != NULL)
            {
                printf("%s(%dms)  ", graph.devices[q->index].name, q->delay);
                q = q->next;
            }
        }
    }
    printf("\n==============================\n\n");
}
