如何用替代路径表示依赖关系图 [英] How to represent a dependency graph with alternative paths
问题描述
在这种情况下，尝试表示和操作依赖关系图时遇到了一些麻烦：
我从目标节点开始递归查找它的依赖关系，但必须保留上述属性，特别是第三个属性。 p>
这里只是一个小例子：
我想要一个像下面这样的图：
$ （A）/ \
/ \
/ \
[（B）B
$ b $ $ $ $ $ ），（C），（D）]（E）
/ \
/ \（H）
（F）（G）
$ b
这意味着：
- F，G， C，H，E没有依赖性
- D依赖于H
B取决于F和G - A取决于E 和
- B 或
- C 或
- D
$因此，如果我写下所有可能的拓扑排序路径到AI应该有： - E - > F - > G - > B - > A
- E - > C - > A E - > H - > D - > A
如何建立具有这些属性的图形？哪种数据结构更适合这样做？
您应该使用正常的邻接列表，并附加一个属性，其中一个节点知道其它节点也将满足相同的依赖关系。这意味着B，C，D应该都知道它们属于同一个等价类。
节点：$ b $ b List< Node>你可以通过将它们全部插入到一个集合中来实现这一点。 adjacencyList
Set< Node> equivalentDependencies
要在拓扑排序中使用此数据结构，只要删除源并删除所有它的输出边，也删除其等价类中的节点，它们的输出边，并递归地移除指向它们的节点。
来自wikipedia：
L←将包含已排序元素的空列表
S←全部集合没有传入边的节点
，而S是非空的do
从S
中删除一个节点n在n的等同类中的每个节点o上，删除L
的尾部n < ===消除等价的相关性
从S
中删除j，其中每个节点k的边e从j到k do
从图中删除边e
如果k有没有其他传入边缘然后
将k插入到S
中，对于每个节点m，边缘e从n到m执行
从图形中删除边缘e
如果m没有其他传入然后
将m插入到S
中，如果图有边，则
返回错误（图中至少有一个循环）
else
return L（拓扑排序）
这个算法会给你一个修改后的拓扑图ly-sorted路径。
I'm having some trouble trying to represent and manipulate dependency graphs in this scenario:
- a node has some dependencies that have to be solved
- every path must not have dependencies loops (like in DAG graphs)
- every dependency could be solved by more than one other node
I starts from the target node and recursively look for its dependencies, but have to mantain the above properties, in particular the third one.
Just a little example here:
I would like to have a graph like the following one
(A)
/ \
/ \
/ \
[(B),(C),(D)] (E)
/\ \
/ \ (H)
(F) (G)
which means:
- F,G,C,H,E have no dependencies
- D dependends on H
- B depends on F and G
- A depends on E and
- B or
- C or
- D
So, if I write down all the possible topological-sorted paths to A I should have:
- E -> F -> G -> B -> A
- E -> C -> A
- E -> H -> D -> A
How can I model a graph with these properties? Which kind of data structure is the more suitable to do that?
You should use a normal adjacency list, with an additional property, wherein a node knows its the other nodes that would also satisfy the same dependency. This means that B,C,D should all know that they belong to the same equivalence class. You can achieve this by inserting them all into a set.
Node:
List<Node> adjacencyList
Set<Node> equivalentDependencies
To use this data-structure in a topo-sort, whenever you remove a source, and remove all its outgoing edges, also remove the nodes in its equivalency class, their outgoing edges, and recursively remove the nodes that point to them. From wikipedia:
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
add n to tail of L
for each node o in the equivalency class of n <===removing equivalent dependencies
remove j from S
for each node k with an edge e from j to k do
remove edge e from the graph
if k has no other incoming edges then
insert k into S
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
This algorithm will give you one of the modified topologicaly-sorted paths.
这篇关于如何用替代路径表示依赖关系图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
