英文:
JGraphT Good Performance/Storage with Millions of Dynamic Nodes/Edges
问题
以下是翻译好的内容:
我正在尝试在一个拥有一百万个节点的图中寻找最短路径。平均而言,每个节点可能有大约 20 条有向边,因此规模相当大。
除此之外,是否有一种可以实时调整边权重(动态调整)的方法呢?
我的意思是我想能够通过时间参数来规划图。根据该时间参数,它将会将边权重乘以某个数量。
你可能拥有这些数据:
- 节点 A
- 节点 B
- 边 1(从 A 到 B),权重为 5
- 边 2(同样也是从 A 到 B),权重为 3
我可以调用一个函数:
graph.getShortestPath(A, B, 8) // 从节点 A 到 B,时间为早上 8 点
graph.getShortestPath(A, B, 16) // 从节点 A 到 B,时间为下午 4 点
时间参数将会影响边权重。例如,当遍历一条边时,我希望能够识别该边的位置,并将其权重乘以与时间参数相关的因子。
是否有一个简单的 JGraphT 的 Java 示例(甚至更好的话,是 Kotlin 示例),可以说明这一点?
英文:
I'm trying to find the shortest path in a graph with a million nodes. On average, there are likely 20 directed edges per node, so it's quite sizeable.
In addition to this, is there a way to adjust the edge weights in real-time (dynamically)?
What I mean is I want to be able to route the graph by a time parameter. Depending on that time parameter, it will multiply edge weights by some amount.
You may have this data:
- Node A
- Node B
- Edge 1 (A to B) having weight 5
- Edge 2 (also from A to B) having weight 3
I may call a function:
graph.getShortestPath(A, B, 8) // From node A to B at 8am
graph.getShortestPath(A, B, 16) // From node A to B at 4pm
The time parameter would influence the edge weights. Eg. when an edge is traversed, I would like to identify the location of that edge and multiply its weight by a factor dependent on the time parameter.
Is there a simple JGraphT example in Java (or even better, Kotlin) that would illustrate this?
答案1
得分: 3
在如此庞大的图上进行时间相关的路径规划并非易事,特别是如果你需要动态更新。这将需要高度复杂的算法和存储方法。毫不奇怪,关于这个主题有大量的学术文献可供参考。
对于 jgrapht,首先阅读用户指南。接下来,浏览目前包含在 jgrapht 中的各种最短路径算法。关于如何使用它们的示例,请参阅测试类。你可能想要使用其中一种 Contraction Hierarchy 算法。你需要为执行算法的初始化支付初始成本,但是对大型图进行的后续最短路径查询非常快速。
为了更快地存储图表,你可以尝试 jgrapht-opt 包中优化的稀疏图表示。
目前,这些算法都没有提供一些增量机制来处理动态的权重变化。此外,目前也没有包含时间相关的算法。你可以做的是创建图表的多个时间快照,例如每15分钟记录一次旅行速度的快照。当计算从某个时间(比如9:05)开始的最短路径时,你可以使用9:15的快照来近似旅行时间。对于快照,请使用AsWeightedGraph视图,通过它可以为同一底层图表提供不同加权的视图。
英文:
Time dependent routing on such a large graph is no easy task, especially not if you are looking for dynamic updates. This would require highly sophisticated algorithms and storage approaches. Not surprisingly, there's a whole range of academic literature on this topic.
For jgrapht, first read the user guide. Next, have a look at the various Shortest Path Algorithms that are currently included in jgrapht. For examples on how to use them, see the test classes. You probably want to use one of the Contraction Hierarchy algorithms. You pay an initial cost to perform the initialization of the algorithm, but subsequent shortest path queries on large graphs are really fast.
For faster storage of your graph, you might want to try the optimized sparse graph representation in the jgrapht-opt package.
Currently none of the algorithms provide some incremental mechanism to deal with dynamic weight changes. Moreover, time-dependent algorithms are currently not included. What you could do is create several time snapshots of your graph, e.g. a snapshot of the travel speeds every 15 minutes. When computing a shortest path for a route that starts at say 9.05, you would use the 9.15 snapshot to approximate the travel time. For snapshots, use the AsWeightedGraph view through which you can provide different weighted views of the same underlying graph.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论