从依赖图中查找并拓扑排序所有树，包括给定的一组节点

Question

假设我有以下依赖关系图（A => [B] 表示 A depends/requires B 在更新 A 的值之前更新其值）。我正在使用 Ruby 散列和 TSort 模块进行拓扑操作。

graph = {
  a: OpenStruct.new(dependencies: []),
  b: OpenStruct.new(dependencies: [:a]),
  c: OpenStruct.new(dependencies: [:b]),
  d: OpenStruct.new(dependencies: []),
  e: OpenStruct.new(dependencies: [:d]),
  f: OpenStruct.new(dependencies: []),
}
# Which gives 3 dependency trees
:c => :b => :a, :e => :d, :f

给定任意一组节点，我需要查找并拓扑排序需要更新的节点，包括（递归地）这组节点的父节点和子节点。也就是说，包括这些节点的所有依赖关系树，而不仅仅是树中那些节点的依赖关系。

这里有一些例子（关于输出，我可以处理一组 TSorted 图，或者只是一个扁平化的版本，我不在乎，参见示例 3）但是数组如下所示，经过排序的图表更易于规范。

desired_function(:a) == [:c,:b,:a] # or [[:c,:b,:a]]
desired_function(:b) == [:c,:b,:a] # or [[:c,:b,:a]]
desired_function(:c) == [:c,:b,:a] # or [[:c,:b,:a]]
desired_function(:c,:d) == [:c,:b,:a,:d,:e] # or [:d,:e,:c,:b,:a] or [[:d,:e], [:c,:b,:a]], or [[:c,:b,:a], [:d,:e]]
desired_function(:f) == [:f] # or [[:f]]

我已经尝试实现 TSort 算法，但我不确定如何指定我还需要包括我从中请求 tsort 的节点的父节点

我当前的实现（在上面给出的 graph 上）

def incomplete_function_to_get_tsorted_subgraphs(graph, node_names) 
  each_node = lambda { |&b| graph.slice(*node_names).each_key(&b) }
  each_child = lambda do |node_name, &b|
    graph[node_name].dependencies.each(&b)
  end
  TSort.tsort(each_node, each_child)
end

它是不完整的，因为目前它只会获得请求节点的依赖关系 incomplete_function_to_get_tsorted_subgraphs(graph, :b) # returns [:a, :b] instead of [:a,:b,:c] 如果我删除 slice 那么它只会变成完整图表上的 tsort 这不是我想要的想要（我需要以某种方式修剪它）

我想要实现的规范（假设我们返回经过排序的依赖图数组）

expect(complete_function_to_get_tsorted_subgraphs(:b)).to include([:a,:b,:c])

expect(complete_function_to_get_tsorted_subgraphs(:b,:d).to 
  include([:a,:b,:c], [:d, :e])

我使用 TSort 算法的方式是否正确，你能帮我修复我的功能吗，还是我必须走完全不同的道路才能得到我想要的东西？

Answer 1

我最后做了什么：

从我需要计算的统计数据中，始终使用这样的函数（实现很可能会得到改进）

def find_leaf_nodes(node_name)
  parents = all_nodes.select { |_,node| node.dependencies.include?(name) }
  if parents.any?
    parents.flat_map { |parent_name, _| find_leaf_nodes(parent_name) }
  else
    name
  end
end

然后使用我在问题中提到的代码从这里构建 TSorted 依赖项列表

从依赖图中查找并拓扑排序所有树，包括给定的一组节点

Find and sort topologically all trees including a given group of nodes from a dependency graph

ruby

topological-sort