背景
旅行本应是一件令人愉快的事情，但是，为了每次旅行选择路线，却要花费大量的时间进行对比。将城市通过交通路线进行连接，就会构建出一张庞大的网状图。那是否可以构建一张图，通过图的算法，来解决旅行的问题呢？有了这样的想法，我决定尝试一下使用 TuGraph 图数据库来解决旅行的问题。但受限于数据的来源，开发的难度等等，所以先用一些公开的历史航班数据来进行 Demo 模拟，验证此方法的可行性。
图模型构建
首先开始构建模型，定义了一类点（city）和一类边（flight），通过航班将城市进行连接，本次Demo只考虑时间消耗和金额消耗的维度。用于计算的点类型：
用于计算的边类型及重要属性：
详细的模型说明可查看Demo说明文档：https://github.com/TuGraph-family/tugraph-db-demo/blob/main/round_the_world/README.md
数据来源
模型定义完成后，就要考虑数据的来源。目前航班最新数据要通过购买的方式获取，考虑到当前处于实验阶段，所以我拉取了公开的航班历史数据进行模拟。
公开数据集地址：https://zenodo.org/records/7923702
数据处理
将数据进行清洗，构建成符合TuGraph标准的数据格式。数据清洗是一件复杂的事情，具体的处理流程可以参考文档：https://github.com/TuGraph-family/tugraph-db-demo/blob/main/round_the_world/README.md
数据导入
数据处理完成后，以城市为顶点，以航班为边进行数据导入。数据导入后，我通过简单 cypher 进行查询测试，并检查返回结果是否符合预期。根据返回结果来看，查询结果符合我的期望。
查询结果一：
查询结果二：通过图数据库进行路径分析，我们可以在画布中通过拖拽的方式快速的找出相关路径。
可视化路径筛选：
算法实现
从可拓展性和性能的角度考虑，存储过程是优于查询语句的。同时TuGraph图数据库是支持存储过程的，因此，我开始通过存储过程来实现相应的图算法。
输入
• cities：给定城市列表
• interval：航班间隔，乘客在每个城市停留时间，单位为小时
• start_day：开始时间，所选航班时间需要大于该时间
• end_day：结束时间，所选航班时间需要小于该时间
输出
• num_flights：航班总数
• num_paths：计算出的路径数量
• total_time：计算时间
• time_first_data：按照时间开销从小到大排序的前十条路径
• cost_first_data：按照机票开销从小到大排序的前十条路径
计算流程
• 根据给定城市列表筛选这些城市之间的航班数据；
• 根据所有筛选航班数据，每条航班对应初始化一条路线，将所有路线压入栈S
• 从S中出栈路线path，若path已包含所有城市，将path写入到结果result
• 若path未包含所有城市，根据path遍历的最后一个城市，选择合适航班，将path+新航班作为new_path压入栈S
• 重复步骤3、4，直到S为空
• 返回result
源码地址：https://github.com/TuGraph-family/tugraph-db-demo/blob/main/round_the_world/plugin/demo.cpp
通过界面进行验证：
可视化应用
以上的操作已经完成了路径规划的基本能力，但是通过一堆字符串，让人看起来还是比较难以理解。因此，我通过前端可视化的方式将Demo进行优化。这样不但可以提高数据的展示效果，也可以让用户操作起来更便捷。当前Demo的可视化功能只支持用户选择城市，然后后端自动返回推荐路径。
用户选择目标城市后，点击查询按钮。TuGraph服务就可以快速的进行路径规划和推荐，并且会统计出本次的计算结果和计算时间。
一起共建
本次只是一个可行性的实验，所以只考虑城市、航班、经济、时间，整体复杂度并不高。希望通过这个Demo可以给图数据库的使用者带来一些启发。也希望更多的小伙伴可以参与进来，和我们一起共建图相关的应用生态。
TuGraph-DB Demo仓库地址：https://github.com/TuGraph-family/tugraph-db-demo
总结
用图和图算法解决路径规划问题，整体思路比较清晰，可以将复杂的关系数据更形象的表现，同时利用图数据库的天然优势，可以高效的进行多跳的关联路径查询。让我们期待未来图数据库在路径规划上可以带来更多的便捷应用。
✨ 欢迎关注TuGraph代码仓库~
