[[433885]]

大家好，我是程序員幽鬼。

最近，我在思考在軟件工程中遇到的許多重要問題可以歸結為幾個簡單的問題。只要看看任何關于算法的書，其中的大部分都會是排序或搜索集合的一些變體。谷歌的存在是因為“哪些文檔包含這些短語?”是一個真正難以解決的問題(好吧，這極大地簡化了 Google 產品的龐大范圍，但基本思想仍然成立)。

01 什么是拓撲排序?

在我的職業生涯中，我一次又一次遇到的常見問題之一就是對依賴圖的節點進行拓撲排序。換句話說，給定一些有向無環圖 — 想想可以依賴于其他軟件包或大型公司項目中的任務的軟件包 — 對它們進行排序，以便列表中的任何項目都不會依賴于列表中后面出現的任何內容。假設我們正在制作蛋糕，在開始之前，我們需要一些原料。讓我們來簡化一下，說我們只需要雞蛋和面粉。嗯，要吃雞蛋，我們需要雞(相信我，我在這里不是開玩笑)，要吃面粉，我們需要谷物。雞也需要谷物作為飼料，谷物需要土壤和水才能生長。我們考慮表達所有這些依賴關系的圖表：

The dependency graph of cake

該圖的一種可能的拓撲順序是：

[]string{"soil", "water", "grain", "chickens", "flour", "eggs", "cake"} 

但是，還有其他可能的拓撲順序：

[]string{"water", "soil", "grain", "flour", "chickens", "eggs", "cake"} 

我們也可以把面粉放在雞蛋后面，因為唯一依賴雞蛋的就是蛋糕。由于我們可以重新排列項目，我們還可以并行完成其中一些項目，同時保持任何項目都不會出現在依賴于它的任何東西之前。例如，通過添加一層嵌套，我們可以表明內部切片中的所有內容都獨立于該切片中的其他任何內容：

[][]string{ 
    {"soil", "water"}, 
    {"grain"}, 
    {"chickens", "flour"}, 
    {"eggs"}, 
    {"cake"}, 
} 

從這個圖中，我們得到了一個很好的“執行計劃”，用于為蛋糕準備依賴項。首先，我們需要找到一些土壤和水。接下來，我們種植谷物。然后，我們同時養一些雞和做面粉，收集雞蛋。最后，我們可以做蛋糕了!對于小于四歲的人來說，這似乎是一項艱巨的工作，但好的事情需要時間。

02 構建依賴圖

現在我們了解了要做什么，讓我們考慮如何編寫一些能夠構建這種依賴項列表的代碼。我們當然需要跟蹤元素本身，我們需要跟蹤什么取決于什么。為了使兩者都“取決于什么X?” 和“X取決于什么?” 高效，我們將跟蹤兩個方向的依賴關系。

我們已經足夠了解開始編寫代碼所需的內容：

// A node in this graph is just a string, so a nodeset is a map whose 
// keys are the nodes that are present. 
type nodeset map[string]struct{} 
 
// depmap tracks the nodes that have some dependency relationship to 
// some other node, represented by the key of the map. 
type depmap map[string]nodeset 
 
type Graph struct { 
 nodes nodeset 
 
 // Maintain dependency relationships in both directions. These 
 // data structures are the edges of the graph. 
 
 // `dependencies` tracks child -> parents. 
 dependencies depmap 
 // `dependents` tracks parent -> children. 
 dependents depmap 
 // Keep track of the nodes of the graph themselves. 
} 
 
func New() *Graph { 
 return &Graph{ 
  dependencies: make(depmap), 
  dependents:   make(depmap), 
  nodes:        make(nodeset), 
 } 
} 

這種數據結構應該適合我們的目的，因為它包含我們需要的所有信息：節點、“依賴”邊和“依賴于”邊。現在讓我們考慮創建用于向圖形添加新依賴關系的 API。所有我們需要的是一個聲明的方法，一些節點依賴于另一個，就像這樣：graph.DependOn("flour", "grain")。有幾種情況我們要明確禁止。首先，一個節點不能依賴于自己，其次，如果flour依賴于grain，那么grain一定不能依賴于flour，否則我們會創建一個無限的依賴循環。有了這個，讓我們編寫Graph.DependOn()方法。

func (g *Graph) DependOn(child, parent string) error { 
 if child == parent { 
  return errors.New("self-referential dependencies not allowed") 
 } 
 
 // The Graph.DependsOn() method doesn't exist yet. 
 // We'll write it next. 
 if g.DependsOn(parent, child) { 
  return errors.New("circular dependencies not allowed") 
 } 
 
 // Add nodes. 
 g.nodes[parent] = struct{}{} 
 g.nodes[child] = struct{}{} 
 
 // Add edges. 
 addNodeToNodeset(g.dependents, parent, child) 
 addNodeToNodeset(g.dependencies, child, parent) 
 
 return nil 
} 
 
func addNodeToNodeset(dm depmap, key, node string) { 
 nodes, ok := dm[key] 
 if !ok { 
  nodes = make(nodeset) 
  dm[key] = nodes 
 } 
 nodes[node] = struct{}{} 
} 

一旦我們實現，這將有效地為我們的圖表添加依賴關系Graph.DependsOn()。我們可以很容易地判斷一個節點是否直接依賴于其他某個節點，但我們也想知道是否存在傳遞依賴。例如，由于flour依賴于grain并且grain依賴于soil，因此也flour依賴于soil。這將要求我們獲取節點的直接依賴項，然后對于這些依賴項中的每一個，獲取其依賴項等等，直到我們停止發現新的依賴項。用計算機科學術語來說，我們正在計算一個固定點，以在我們的圖上找到“DependsOn”關系的傳遞閉包。

func (g *Graph) DependsOn(child, parent string) bool { 
 deps := g.Dependencies(child) 
 _, ok := deps[parent] 
 return ok 
} 
 
func (g *Graph) Dependencies(child string) nodeset { 
 if _, ok := g.nodes[root]; !ok { 
  return nil 
 } 
  
 out := make(nodeset) 
 searchNext := []string{root} 
 for len(searchNext) > 0 { 
  // List of new nodes from this layer of the dependency graph. This is 
  // assigned to `searchNext` at the end of the outer "discovery" loop. 
  discovered := []string{} 
  for _, node := range searchNext { 
   // For each node to discover, find the next nodes. 
   for nextNode := range nextFn(node) { 
    // If we have not seen the node before, add it to the output as well 
    // as the list of nodes to traverse in the next iteration. 
    if _, ok := out[nextNode]; !ok { 
     out[nextNode] = struct{}{} 
     discovered = append(discovered, nextNode) 
    } 
   } 
  } 
  searchNext = discovered 
 } 
  
 return out 
} 

03 對圖表進行排序

現在我們有了一個圖數據結構，可以考慮如何按照拓撲順序將節點取出。如果我們可以發現葉節點—即，節點本身對其他節點沒有依賴關系—那么我們可以重復獲取葉子并將它們從圖中移除，直到圖為空。在第一次迭代中，我們將找到獨立的元素，然后在隨后的每次迭代中，我們將找到僅依賴于已刪除元素的節點。最終結果將是一個按拓撲排序的獨立“層”節點的切片。

獲取圖的葉子很簡單。我們只需要找到在 dependencies 中沒有條目的節點。這意味著它們不依賴于任何其他節點。

func (g *Graph) Leaves() []string { 
 leaves := make([]string, 0) 
 
 for node := range g.nodes { 
  if _, ok := g.dependencies[node]; !ok { 
   leaves = append(leaves, node) 
  } 
 } 
 
 return leaves 
} 

最后一塊拼圖實際上是計算圖的拓撲排序層。這也是最復雜的一塊。我們將遵循的一般策略是迭代地收集葉子并將它們從圖中刪除，直到圖為空。由于我們將對圖進行變異，因此我們希望對其進行克隆，以便在執行排序后原始圖仍然完好無損，因此我們將繼續實施該克隆：

func copyNodeset(s nodeset) nodeset { 
 out := make(nodeset, len(s)) 
 for k, v := range s { 
  out[k] = v 
 } 
 return out 
} 
 
func copyDepmap(m depmap) depmap { 
 out := make(depmap, len(m)) 
 for k, v := range m { 
  out[k] = copyNodeset(v) 
 } 
 return out 
} 
 
func (g *Graph) clone() *Graph { 
 return &Graph{ 
  dependencies: copyDepmap(g.dependencies), 
  dependents:   copyDepmap(g.dependents), 
  nodes:        copyNodeset(g.nodes), 
 } 
} 

我們還需要能夠從圖中刪除一個節點和所有邊。刪除節點很簡單，就像從每個節點刪除出站邊一樣。然而，我們跟蹤兩個方向的每條邊的事實意味著我們必須做一些額外的工作來刪除入站記錄。我們將用于刪除所有邊的策略如下：

在 dependents 中查找節點 A 的條目。這為我們提供了依賴于 A 的節點集 。

對于這些節點中的每一個，在 dependencies 中找到條目。從 nodeset 中刪除A。

在 dependents 中刪除節點 A 的條目。

執行逆操作，在 dependencies 中查找節點 A 等。

借助一個允許我們從 depmap 條目中刪除節點的小實用程序，我們可以編寫從圖中完全刪除節點的方法。

func removeFromDepmap(dm depmap, key, node string) { 
 nodes := dm[key] 
 if len(nodes) == 1 { 
  // The only element in the nodeset must be `node`, so we 
  // can delete the entry entirely. 
  delete(dm, key) 
 } else { 
  // Otherwise, remove the single node from the nodeset. 
  delete(nodes, node) 
 } 
} 
 
func (g *Graph) remove(node string) { 
 // Remove edges from things that depend on `node`. 
 for dependent := range g.dependents[node] { 
  removeFromDepmap(g.dependencies, dependent, node) 
 } 
 delete(g.dependents, node) 
 
 // Remove all edges from node to the things it depends on. 
 for dependency := range g.dependencies[node] { 
  removeFromDepmap(g.dependents, dependency, node) 
 } 
 delete(g.dependencies, node) 
 
 // Finally, remove the node itself. 
 delete(g.nodes, node) 
} 

最后，我們可以實現 Graph.TopoSortedLayers()：

func (g *Graph) TopoSortedLayers() [][]string { 
 layers := [][]string{} 
 
 // Copy the graph 
 shrinkingGraph := g.clone() 
 for { 
  leaves := shrinkingGraph.Leaves() 
  if len(leaves) == 0 { 
   break 
  } 
 
  layers = append(layers, leaves) 
  for _, leafNode := range leaves { 
   shrinkingGraph.remove(leafNode) 
  } 
 } 
 
 return layers 
} 

這種方法清楚地概述了我們對圖進行拓撲排序的策略：

• 克隆圖，以便我們可以對其進行轉變。
• 反復將圖的葉子收集到輸出的“層”中。
• 收集后刪除每一層。
• 當圖為空時，返回收集的圖層。

現在我們可以回到最初的蛋糕制作問題，以確保我們的圖為我們解決了這個問題：

package main 
 
import ( 
 "fmt" 
 "strings" 
 
 "github.com/kendru/darwin/go/depgraph" 
) 
 
func main() { 
 g := depgraph.New() 
 g.DependOn("cake", "eggs") 
 g.DependOn("cake", "flour") 
 g.DependOn("eggs", "chickens") 
 g.DependOn("flour", "grain") 
 g.DependOn("chickens", "grain") 
 g.DependOn("grain", "soil") 
 g.DependOn("grain", "water") 
 g.DependOn("chickens", "water") 
 
 for i, layer := range g.TopoSortedLayers() { 
  fmt.Printf("%d: %s\n", i, strings.Join(layer, ", ")) 
 } 
 // Output: 
 // 0: soil, water 
 // 1: grain 
 // 2: flour, chickens 
 // 3: eggs 
 // 4: cake 
} 

所有這些工作都不是小菜一碟，但現在我們有了一個依賴圖，可以用來對幾乎任何東西進行拓撲排序。您可以在 GitHub 上找到[1]這篇文章的完整代碼。這個實現有一些明顯的限制，我想挑戰你改進它，以便它可以：

• 存儲不是簡單字符串的節點
• 允許單獨添加節點和邊/依賴信息
• 產生用于調試的字符串輸出

原文鏈接：https://kendru.github.io/go/2021/10/26/sorting-a-dependency-graph-in-go/

參考資料

[1]在 GitHub 上找到: https://github.com/kendru/darwin/tree/main/go/depgraph

本文轉載自微信公眾號「幽鬼」，可以通過以下二維碼關注。轉載本文請聯系幽鬼公眾號。