图表 - 如何建模依赖资源？ [英] Graphs - How to model dependent resources?
问题描述
没有库，我正在尝试学习数据结构。
With out libraries, I'm trying to learn data structures.
我有这些依赖关系
jquery.js->jqueryui.js
(underscores.js, jquery.js) -> backbone.js
基本上，jqueryui依赖于jquery。 Bacbkone依赖于下划线和jquery。 Jquery和下划线没有关联。
Bascially, jqueryui depends upon jquery. Bacbkone depends on both underscore and jquery. Jquery and underscore are not related.
我想创建一个依赖树，让你揭开这些关系。
I want to create a dependency tree have you to "shed light" on these relations.
我被告知这是如何在这个发布的问题上完成的。特别是这个评论。
I was told this is how it is done on this posted question. Particularly this comment.
只要您没有循环依赖关系，您就可以构建
依赖关系林，仅由有向树和/或唯一的
节点组成。在树上你可以简单地使用DFS。然后，首先将
所有根或单个节点添加到队列中，并在加载其依赖项时将其他资源添加到
队列。 （请注意，如果资源
有多个依赖项，则无法将依赖项建模为
林，但它保持非循环，您可以使用类似的方法）。 -
Zeta
As long as you don't have a circular dependency you can always build a dependency forest, which consists only of directed trees and/or sole nodes. On the trees you can simply use DFS. You then start by adding all roots or single nodes into a queue and add other resources to the queue when their dependency has been loaded. (note that if a resource has several dependencies you cannot model your dependencies as a forest, but it stays acyclic and you can use a similar approach). – Zeta
...所以我确实有多个依赖项的资源，所以我不能使用依赖项林。
... so I do have resources with multiple dependencies, so I can't use a dependency forest.
......进一步的讨论提出了有向无环图。
...further discussion has suggested a directed acyclic graph.
有向无环图。从起点开始的每条路径都可以并行完成
，但是如果一个节点有多个事件边缘
，则必须等待所有依赖项加载。顺便说一句，我
代表例子3为P：[U-underscore，U-jquery]
S：[U-underscore，U-backbone-js] S：[U-jquery，U -backbone.js]，显示
原始依赖项，但它们是等价的
A directed acyclic graph. Every path from the starting point can be done in parallel, however if a node has more than one incident edges you have to wait for all dependencies being loaded. By the way, I would represent example 3 as P:[U-underscore, U-jquery] S:[U-underscore, U-backbone-js] S:[U-jquery, U-backbone.js], showing the original dependency, but they are equivalent
我可以使用依赖树吗？如果没有建议建立复杂依赖关系的数据结构......最后我该如何实现它？
Can I use a dependency tree? If not what data structure is suggested to model complex dependencies...and and finally how do I implement it?
推荐答案
我相信我已经解决了这个问题，尽管很久以前。让依赖关系描述如下：
I believe that I have solved this problem, albeit its a long time ago. Let the dependencies be described like this:
- 模块A
- 模块X
- 模块Y
- 模块X
- 模块A
- 模块A
- 模块B
这意味着模块A依赖于模块X和模块Y - 依此类推。
Which means that Module A depends on Module X and Module Y - and so forth.
迭代此林中的叶子以及没有依赖关系的每个叶子（查看基础），将叶子放入加载队列并将其从森林中移除，因此首先通过收益率：
Iterate over the leaves in this forest and for each leaf with no dependencies (look that up at the base), put the leaf in the load queue and remove it from the forest, so first pass yields:
- 模块A
- 模块B
- 模块A
- 模块A
- 模块B
队列：模块X，模块Y.
Queue: Module X, Module Y.
第二遍：
- 模块B
- 模块C
- 模块B
队列：模块X，模块Y，模块A。
Queue: Module X, Module Y, Module A.
......等等。在同一个传递中找到的模块可以并行加载，因此表示这个模块的方法可能是：
...and so forth. Modules found in the same pass can be loaded in parallel, so a way to represent this could be:
[[Module X, Module Y], [Module A], [Module B], [Module C]]这意味着什么应首先加载模块X和模块Y，并且可以并行加载它们。其余的必须按顺序加载。
Which means that Module X and Module Y should be loaded first and that they can be loaded in parallel. The rest must be loaded sequentially.
我对上述方法的最大顾虑是它具有复杂度O（n ^ 2）。应该可以改进。使用查找映射可以轻松完成检测周期。
My biggest concern with the approach above is that it has complexity O(n^2). It should be possible to improve. Detecting cycles can easily be done with a lookup map.
这篇关于图表 - 如何建模依赖资源？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
