![]() |
1
1
我认为您在这里考虑的“宽度”并不是您真正想要的-宽度取决于您如何将级别分配给每个节点,在每个节点上您有一些选择。在决定是将所有源分配给级别0还是将所有汇分配给最大级别时,您注意到了这一点。 相反,您只需要计算节点数,然后除以“关键路径长度”,这是DAG中最长的路径。这给出了图形的平均并行度。它只取决于图形本身,并且它仍然可以指示图形的宽度。 要计算关键路径长度,只需做你正在做的事情-关键路径长度是你最终分配的最大级别。 |
![]() |
2
1
在我看来,当你在进行这种最后一分钟的开发时,最好将新的结构与你已经使用的结构分开。在这一点上,如果时间紧迫,我会寻求一个更简单的解决方案。
问题是,正如基思·兰德尔所问,这是你需要的正确测量方法吗? |
![]() |
3
1
这是我(白金天青,原作者)迄今为止所拥有的。 准备/扩充:
算法:
所以到目前为止我就是这么想的。有办法改进吗?一路上都是线性时间,但有五六次线性扫描,可能会有很多缓存未命中等等。我想知道是否没有一种方法可以利用具有更好数据结构的某个局部性,而不必实际更改节点扩展以外的底层代码。 有什么想法吗? |
![]() |
Rosie Lomas · 在ggplot中设置数字刻度 2 年前 |
![]() |
nedlaback · 在O(V+E)图中寻找瓶颈边 7 年前 |
|
Skampak · R visNetwork:创建新类型的边 7 年前 |
![]() |
Anuja · 长度l在R中的最短路径 7 年前 |
![]() |
Cbhihe · 优化Neo4j查询,有条件地创建新关系 7 年前 |
![]() |
fghjk · 绘制轨迹(python) 7 年前 |
![]() |
LBerger · 计算图形图像中的名称使用(TensorBoard) 7 年前 |