一个有向循环图的数据结构和算法（F#）

Question

5

我正在尝试分析一个应用程序，其中汇编引用应该是有向无环图，但实际上并不是。还有一个相关问题，即子汇编引用了一个子子汇编的不同版本(think Escher...)。

我想要做的是分析每个汇编-子汇编对，并建立一个错误位置的图像。

我需要一些关于这个问题的数据结构建议。我不确定能否构建不可变的数据结构，但我不介意在内部使用可变的数据结构，然后在最后转换为不可变的数据结构。

另一个问题是，我应该使用什么样的算法来填充数据结构，以及之后用于“分析”问题的算法。

- Benjol

3个回答

2

我不介意在内部使用可变数据结构，然后在最后转换为不可变数据结构。

你可能会发现在整个过程中使用不可变数据结构更容易。特别是，你可以将图表示为从源节点到目标节点集合的Map。对于拓扑排序，你需要有效地访问目标节点的源节点，因此你可能需要用另一个Map来增强你的图，使其朝相反的方向进行。

我刚刚在F#中实现了这个功能，拓扑排序只需要12行代码... :-)

- J D

Jon，我需要一个拓扑排序函数。你能分享一下吗？ - Cameron Taggart

1

我在这里写了一篇关于它的文章：http://fsharpnews.blogspot.co.uk/2010/10/graph-algorithms-topological-sort-and.html - J D

1

你想要做的是“拓扑排序”。维基百科有一个很好的概述：

- Dmitry Lomov

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mauricio Scheffer · Accepted Answer

你可以直接使用NDepend，它可以分析您的程序集并检测依赖循环。

如果您真的想自己做，我建议使用QuickGraph来建立依赖图，并包括拓扑排序等图算法。