# road

**Repository Path**: flowerbacket/road

## Basic Information

- **Project Name**: road
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-10-25
- **Last Updated**: 2025-10-25

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README




          
**README**

- 管线铺设辅助系统（MST）Web 应用，支持从 CSV 读取数据、选择 Prim/Kruskal 算法、展示最优方案与生成过程，并提供动画可视化。
- 后端 `Flask + Python`，算法模块复用并扩展 `PipelineSystem`；前端 `HTML + CSS + 原生 JS + SVG`。
- 运行在本地浏览器，支持上传 CSV、加载示例、执行算法、播放动画、导出文本方案。

**目录结构**
- `e:\code\road\road.py`：后端入口与算法实现、接口路由。
- `e:\code\road\templates\index.html`：前端页面骨架。
- `e:\code\road\static\js\app.js`：前端逻辑、动画渲染。
- `e:\code\road\static\css\styles.css`：前端样式。
- `e:\code\road\campus_distances1.csv`、`e:\code\road\campus_distances.csv`：示例数据。
- `e:\code\road\pipeline_solution.txt`：CLI 模式生成的文本（Web 模式在浏览器端下载）。

**功能总览**
- 数据读取：上传 CSV 或加载示例数据，自动解析名称与距离矩阵。
- 算法选择：Prim 或 Kruskal，两者都支持动画可视化生成过程。
- 结果展示：总铺设距离、最优边集合（MST）、生成过程步骤日志。
- 动画控制：播放、暂停、下一步、重置、速度调整。
- 文本导出：导出当前方案与生成过程为 `pipeline_solution.txt`。

**运行环境**
- 依赖：`flask`、`numpy`、`networkx`、`matplotlib`
- 安装依赖（Windows，单条命令）：
```bash
python -m pip install flask numpy networkx matplotlib
```
- 启动服务（Windows，单条命令）：
```bash
python e:\code\road\road.py
```
- 访问地址：`http://127.0.0.1:5000/`

**系统架构**
- 后端（Flask）
  - 路由提供数据加载与算法计算接口（JSON 或 CSV 表单）。
  - 复用 `PipelineSystem` 并新增「带步骤」的算法方法用于动画。
  - 模板与静态资源提供前端页面与脚本。
- 前端（原生 JS + SVG）
  - 管理应用状态（数据、结果、步骤、播放状态、速度等）。
  - 绘制节点与边，按步骤事件模型驱动动画。
  - 提供交互控件与文本导出功能。

**数据规范（CSV）**
- 第一行：建筑名称（逗号分隔）。
- 第 2 行起：距离矩阵（逗号分隔、与名称数量一致）。
- 建议规则：
  - 矩阵对称：`matrix[i][j] == matrix[j][i]`
  - 自身距离为 `0`
  - 权重为正数且 `>0` 表示存在边，`0` 表示无边

**后端说明**
- `PipelineSystem`（核心算法与数据）
  - `read_data_from_file(filename)`：读取 CSV 文件内容。
  - `read_data_from_text(text)`：从文本字符串读取，支持上传。
  - `build_graph()`：根据矩阵构建无向图邻接表（权重>0）。
  - `prim_algorithm()` / `kruskal_algorithm()`：传统版本（兼容 CLI）。
  - `prim_with_steps()` / `kruskal_with_steps()`：输出 MST 与步骤事件，用于动画。
- 路由
  - `GET /`：返回首页页面。
  - `GET /api/sample`：返回示例数据 `{ names, matrix }`。
  - `POST /api/compute`：
    - JSON：`{ algorithm, names, matrix }`
    - 表单：`file: CSV` 与 `algorithm`
    - 响应：`{ algorithm, total_cost, mst_edges, steps, buildings }`

**API 说明**
- `GET /api/sample`
  - 响应：
```json
{
  "names": ["里仁学院教学楼", "学生公寓", "..."],
  "matrix": [[0, 500, ...], [500, 0, ...], ...]
}
```
- `POST /api/compute`（JSON）
  - 请求：
```json
{
  "algorithm": "prim",
  "names": ["里仁学院教学楼", "学生公寓", "..."],
  "matrix": [[0, 500, ...], [500, 0, ...], ...]
}
```
  - 响应：
```json
{
  "algorithm": "Prim",
  "total_cost": 2870,
  "mst_edges": [
    { "u": 0, "v": 7, "weight": 140 },
    { "u": 2, "v": 1, "weight": 160 }
  ],
  "steps": [
    { "type": "consider", "u": 0, "v": 7, "weight": 140, "description": "..." },
    { "type": "select", "u": 0, "v": 7, "weight": 140, "description": "..." },
    { "type": "reject", "u": 0, "v": 1, "weight": 500, "reason": "..." }
  ],
  "buildings": ["里仁学院教学楼", "学生公寓", "..."]
}
```
- `POST /api/compute`（文件上传）
  - 表单字段：`file`（CSV）、`algorithm`（`prim` 或 `kruskal`）
  - 响应同上

**前端说明**
- 状态管理（`state`）
  - 关键字段：`names`、`matrix`、`result`、`steps`、`stepIdx`、`playing`、`speedMs`、`positions`、`mstCost`
  - 通过事件绑定更新状态并驱动渲染与动画
- 布局与绘制
  - `computePositions(names)`：圆形自动布局生成节点坐标
  - `drawNodes(names, positions)`：绘制建筑节点与标签，初始化图层
  - 图层：
    - `mstEdges`：永久选中 MST 边（红色、加粗）
    - `considerEdges`：当前考虑/拒绝的临时边（灰色、虚线）
- 动画流程
  - 步骤事件模型驱动：`applyStep(step)` 根据 `type` 绘制高亮与日志
  - 控制函数：`nextStep()`、`play()`、`pause()`、`reset()`、`speedRange` 调速
  - 日志：`stepsList` 逐条滚动展示生成过程说明
- 文本导出
  - `downloadSummary()`：将当前 MST 与步骤导出为文本，自动下载为 `pipeline_solution.txt`

**步骤事件模型**
- 事件类型
  - `consider`：正在考虑的边（显示灰色虚线）
  - `select`：被选中的边（加入 MST，红色加粗）
  - `reject`：被拒绝的边（形成环或不满足条件，浅灰虚线）
- 事件结构
```json
{ "type": "consider", "u": 0, "v": 7, "weight": 140, "description": "考虑边 A ←→ B，距离 140" }
```
```json
{ "type": "select", "u": 0, "v": 7, "weight": 140, "description": "选择边 A ←→ B" }
```
```json
{ "type": "reject", "u": 0, "v": 1, "weight": 500, "reason": "形成环路/目标已在树中" }
```

**使用流程**
- 加载数据：上传 CSV 或点击“加载示例数据”。
- 选择算法：Prim 或 Kruskal。
- 执行计算：点击“执行算法”，等待结果与步骤加载。
- 播放动画：使用播放/暂停/下一步/重置控制流程，调整速度。
- 导出文本：点击“导出文本方案”生成 `pipeline_solution.txt`。

**扩展指南**
- 节点布局
  - 用真实校区坐标替换圆形布局：后端新增接口返回固定坐标或前端支持拖拽保存。
  - 支持叠加底图（校园平面图或在线地图）增强展示效果。
- 算法扩展
  - 添加 Borůvka 等其他 MST 算法：遵循步骤事件模型即可兼容前端动画。
  - 支持多维权重（成本、施工难度），在请求参数中指定权重类型。
- 数据与校验
  - 增加对称性与维度检查，前端错误提示更友好。
  - 支持稀疏图（边列表）输入，后端统一归一化为矩阵。
- 结果持久化
  - 后端保存方案（CSV、MST、步骤、布局），提供历史记录与重现。
  - 导出/导入 JSON，便于共享和备份。
- 性能优化
  - 节点/边规模增大时，改用 Canvas/WebGL 绘制，减少 DOM 操作。
  - 合并渲染批次，使用 requestAnimationFrame 替代 setInterval。

**常见问题**
- CSV 加载失败
  - 第一行必须是名称，矩阵行数与名称数量一致，每项为数字
- 结果异常或总距离不匹配
  - 确认矩阵对称、单位一致、无错误数据或重复项
- 动画无响应
  - 执行算法后才有 `steps`；如已执行，尝试“重置”后重新播放
- 文件上传不生效
  - 确认通过“选择 CSV 文件”选择本地文件，或使用“加载示例数据”

**后续开发建议**
- 抽象可视化主题（颜色、线宽、虚线样式）为配置项，便于统一调整。
- 提供拖拽编辑节点位置并保存布局到本地或后端。
- 增加方案对比与版本管理（不同算法或参数下的差异对比）。
- 支持约束（禁入区域、最大边长）通过调整权重或屏蔽边实现。

如果你需要把 `road.py` 中的固定校区坐标接入前端，我可以帮你新增一个接口返回这些坐标，并在 `app.js` 中替换圆形布局为真实位置，从而让动画更贴近实际场景。