/**
 * @file travels.h
 * @brief 网络算法模块头文件
 *
 * 声明所有网络算法函数，包括：
 *   - 设备定位 locate
 *   - 深度优先遍历 DFS（全网巡检）
 *   - 拓扑排序 Kahn（路由环路检测）
 *   - Floyd-Warshall（全源最短路径 / 全网路由表）
 *   - Dijkstra（单源最短路径 / OSPF核心算法）
 *   - Prim / Kruskal（最小生成树 / 光纤骨干网布线）
 *   - 设备详情查询
 */

#ifndef TRAVELS_H
#define TRAVELS_H

#include "global.h"

/* ==================== 基础函数 ==================== */

/**
 * @brief 根据设备代号定位设备在数组中的下标
 * @param graph 网络拓扑图（值传递）
 * @param name  待查找的设备代号（如 "CR"、"DR-A"）
 * @return 设备在 devices 数组中的下标，未找到返回 -1
 */
int locate(ALGraph graph, char *name);

/* ==================== Day3: DFS深度优先遍历 ==================== */

/**
 * @brief 深度优先遍历入口 — 全网设备巡检
 * @param graph 网络拓扑图（值传递）
 *
 * 从 CR(下标0)出发，走遍所有设备，输出巡检路线。
 */
void DFSTraverse(ALGraph graph);

/**
 * @brief 深度优先搜索递归核心函数
 * @param graph 网络拓扑图（值传递）
 * @param i     当前访问的设备下标
 */
void DFS(ALGraph graph, int i);

/**
 * @brief 判断两设备间是否有直连链路
 * @param graph 网络拓扑图
 * @param e1    设备1代号
 * @param e2    设备2代号
 * @return 1=有直连链路，0=无直连链路
 */
int isEdge(ALGraph graph, char *e1, char *e2);

/* ==================== Day5: Kahn拓扑排序 ==================== */

/**
 * @brief 路由环路检测（Kahn拓扑排序算法）
 * @param graph 待检测的图（巡检路线生成的有向图）
 * @return 1=无回路(DAG)，0=有回路
 *
 * 算法：统计入度 → 入度为0的顶点入队 → 依次出队并删除其出边 →
 *       若出队顶点数 < 总顶点数则有回路（存在环路）。
 */
int loopTest(ALGraph graph);

/* ==================== Day5/7: Floyd全源最短路径 ==================== */

/**
 * @brief Floyd-Warshall 全源最短路径计算
 * @param graph     网络拓扑图
 * @param path      输出参数：路径矩阵，path[i][j]=中转点下标
 * @param shortpath 输出参数：距离矩阵，shortpath[i][j]=最短延迟(ms)
 *
 * 三重循环 k-i-j 动态规划，时间复杂度 O(n^3)。
 */
void shortPath(ALGraph graph, int path[][MAX_DEVICE], int shortpath[][MAX_DEVICE]);

/**
 * @brief 递归输出设备i到设备j的最短路径
 * @param graph     网络拓扑图
 * @param path      路径矩阵（由shortPath计算）
 * @param shortpath 距离矩阵
 * @param i         起点设备下标
 * @param j         终点设备下标
 */
void printShortPath(ALGraph graph, int path[][MAX_DEVICE], int shortpath[][MAX_DEVICE], int i, int j);

/**
 * @brief 两设备间最优路径查询（交互式，Floyd算法）
 * @param graph     网络拓扑图
 * @param path      路径矩阵（工作空间）
 * @param shortpath 距离矩阵（工作空间）
 *
 * 用户输入起点和终点设备代号，输出最优路径和最短延迟。
 */
void minDistance(ALGraph graph, int path[][MAX_DEVICE], int shortpath[][MAX_DEVICE]);

/**
 * @brief 全网路由表展示（Floyd全源最短距离矩阵）
 * @param graph     网络拓扑图
 * @param path      路径矩阵（工作空间）
 * @param shortpath 距离矩阵（工作空间）
 *
 * 以表格形式输出所有设备之间的最短延迟，不可达显示为 INF。
 */
void floydAllDistance(ALGraph graph, int path[][MAX_DEVICE], int shortpath[][MAX_DEVICE]);

/* ==================== Day7: Dijkstra单源最短路径 ==================== */

/**
 * @brief Dijkstra单源最短路径查询（OSPF协议核心算法）
 * @param graph 网络拓扑图
 *
 * 用户输入起点和终点，输出最短路径和距离。
 * 基于贪心策略：每轮从未确认顶点中选距离最小的"盖章确认"，然后松弛其邻居。
 */
void dijkstraQuery(ALGraph graph);

/* ==================== Day8: 最小生成树 ==================== */

/**
 * @brief Prim算法求最小生成树（光纤骨干网布线）
 * @param graph 网络拓扑图
 *
 * 从顶点0(CR)出发，维护 lowcost[] 和 closest[]，每次选取连接MST集合和未选集合的最小权边。
 * 适用于稠密图，时间复杂度 O(n^2)。
 */
void primMST(ALGraph graph);

/**
 * @brief Kruskal算法求最小生成树（光纤骨干网布线）
 * @param graph 网络拓扑图
 *
 * 将所有链路按延迟从小到大排序，用并查集判环，依次选取不构成环的最小边。
 * 适用于稀疏图，时间复杂度 O(eloge)（冒泡排序）或 O(eloge)（qsort优化）。
 */
void kruskalMST(ALGraph graph);

/* ==================== Day9: 设备详情查询 ==================== */

/**
 * @brief 设备详情查询
 * @param graph 网络拓扑图（值传递，用.访问成员）
 *
 * 用户输入设备代号，输出该设备的名称、类型、端口数、运行时间、描述和相邻设备。
 */
void showDeviceInfo(ALGraph graph);

#endif /* TRAVELS_H */
